Assignment #6: Generalizing CRT

For this assignment, you will submit a single Python source file `a6.py`.

Your file may not import any modules or employ any external library functions associated with integers and sets (unless the problem statement explicitly permits this). You will be graded on the correctness, concision, and mathematical legibility of your code. The different problems and problem parts rely on each other; carefully consider whether you can use functions you define in one part within subsequent parts. You may reuse functions that you defined on previous assignments.

1. Implement a function `solve()` that takes three integer arguments `x`, `y`, and `z`. The function should return a tuple containing two integers, `(a,b)`, such that the following always holds:
```(a,b) = solve(x,y,z)

(x * a + y * b) % (x*y) == z % (x*y) # True.
a in range(0,y)                      # True.
b in range(0,x)                      # True.```
If no such pair `(a,b)` exists, your method should return `None`.
2. Include the following class declaration in your file. An `Eqn()` object represents an equation of the form cxa (mod n), where x is a variable.
```class Eqn():
c = 1
a = 0
n = 1
solvable = True

def __init__(self,c,a,n):
self.c = c
self.a = a
self.n = n

def __repr__(self):
return str(self)

def __str__(self):
if not self.solvable:
return "unsolvable"
else:
return str(self.c) + "x = " + str(self.a) + " mod " + str(self.n)

def unsolvable(self):
self.solvable = False
self.c = None
self.a = None
self.n = None

def simplify(self):
# Implement for #2, part (a).
pass

# Modify this method for #2, part (b).
# This method should behave like CRT2(),
# but it should be able to handle all possible
# cases.

# This function should return another Eqn()
# object that represents the solution (or
# lack thereof) to the two equations e1 and e2.

return None```

1. Implement a member method `simplify()` that converts an `Eqn()` object into an equivalent one in which c = 1, if possible (as determined by this fact). If this is not possible, the method should set the object's `self.solvable` field to `False` (use the member method `unsolvable()`). Some test cases are provided below.
```>>> x = Eqn(6,4,8)
>>> x
6x = 4 mod 8
>>> x.simplify()
>>> x
1x = 2 mod 4

>>> Eqn(1,2,7)
1x = 2 mod 7

>>> Eqn(3,4,5)
3x = 4 mod 5

>>> x = Eqn(5,5,100)
>>> x.simplify()
>>> x
1x = 1 mod 20

>>> x = Eqn(7,1,7)
>>> x.simplify()
>>> x
unsolvable

>>> x = Eqn(7,0,7)
>>> x.simplify()
>>> x
1x = 0 mod 1

>>> x = Eqn(15,5,25)
>>> x.simplify()
>>> x
1x = 2 mod 5

>>> x = Eqn(3,5,6)
>>> x.simplify()
>>> x
unsolvable
```
2. Implement a member method `__add__(e1, e2)`. This method should take two `Eqn()` objects as arguments. It should return a new `Eqn()` object that represents a solution to the two equations, if one exists (otherwise, the returned object should have its `self.solvable` field set to `False`). That is, the input represents the following system of equations:
 c1 ⋅ x
 a1 (mod n1)
 c2 ⋅ x
 a2 (mod n2)
The method should return the unique solution if it exists in the form of an equation object where c = 1, and where a and n are chosen appropriately:
 1 ⋅ x
 a (mod n)
If no solution exists, the returned `Eqn()` object should have its `unsolvable` field set to `True`. Your method should be similar to `CRT2()`, but it must handle all possible inputs correctly (i.e., the `n` values of the two equations are not necessarily coprime, and `c` may be any integer). Solutions that use an exhaustive search will receive no credit. Some test cases are provided below.
```>>> Eqn(1,3,15) + Eqn(1,6,21)
1x = 48 mod 105

>>> Eqn(1,3,15) + Eqn(1,6,21) + Eqn(2,12,18)
1x = 258 mod 315

>>> Eqn(1,2,15) + Eqn(1,4,21)
unsolvable

>>> Eqn(1,7,8) + Eqn(1,0,1)
1x = 7 mod 8
```
3. Consider the algebraic structure consisting of all possible equations of the form `Eqn(c,a,n)` where `c`, `a`, and `n` are integers. The operator for this algebraic structure is the `+` operator (defined by `__add__()`). Determine all the algebraic properties of this algebraic structure, and determine which algebraic structure it is. If an identity and/or inverses exist, you must describe which elements they are or how to find them.
4. Define a Python function `GCRTN()` (not a member method of `Eqn()`) that takes one input, which is a list of one or more `Eqn()` objects. This list represents a system of equations of the following form:
 c1 ⋅ x
 a1 (mod n1)
 ck ⋅ x
 ak (mod nk)
The method should return the unique solution in the form of a single `Eqn()` object where c = 1, and where a and n are chosen appropriately:
 1 ⋅ x
 a (mod n)
If there is no solution, the return `Eqn()` object should indicate this. You may not violate the encapsulation of the `Eqn()` objects. You may only use member methods to create, modify, or combine `Eqn()` objects.