Assignment #6: Generalizing CRT (back to full lecture notes)

For this assignment, you will submit a single Python source file

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"
                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).
        def __add__(e1, e2):
            # 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
      >>> 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
    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:
      a1 (mod n1)
      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)
      >>> 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:
    a1 (mod n1)
    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.