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.
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
.
Eqn()
object
represents an equation of the form c ⋅ x ≡ a (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 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
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
__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:
 ≡ 
 
 ≡ 
 
 ≡ 

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
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.
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:
 ≡ 
 
⋮  
 ≡ 

Eqn()
object where
c = 1, and where a and n are chosen appropriately:
 ≡ 

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.