""" [TECC prototype ALGEGRA 2 4D SOLUTIONS 2008] School standard: students will gain familiarity with important algebraic properties of finite and infinite sets, including the infinite sets N, Z, Q, R, C and finite sets of permutations, numbers modulo M. Xrefs: polyhedra and symmetry groups; permutation groups; RSA; Cryptonomicon (Stephenson); In Code (Flannery) Note to teachers: with Python's operator overloading, group theory comes alive, providing excellent preparation for future careers in mathematics, particle physics, cryptography and more. Note to students: The M-type below implements the four operations, + - * /, as well as the comparison operators > < ==, among integers modulo M. We will use this class to investigate properties of groups, rings and fields. For example, if M is prime, your math facts will demonstrate closure. If M is composite, but only totatives of M get used, you'll at least have group properties over multiplication (*). Lesson plan: >>> from tecc_alg2_u5 import test >>> test(11) Random Math Facts for M11 [m1, m2, m3, m4, m5, m6, m7, m8, m9, m10] m3 * m9 = m5 m8 * m9 = m6 m4 + m6 = m10 m9 + m3 = m1 m5 * m10 = m6 m3 - m9 = m5 m8 * m5 = m7 m1 / m2 = m6 m10 / m4 = m8 m2 / m3 = m8 >>> test(14) Random Math Facts for M14 [m1, m3, m5, m9, m11, m13] m9 / m13 = m5 m13 + m11 = m10 m3 - m9 = m8 m1 / m11 = m9 m3 * m9 = m13 m1 - m9 = m6 m9 / m3 = m3 m3 - m3 = m0 m3 + m1 = m4 m13 / m3 = m9 See also: Algorithms: A Bit of Math by Andrew Kuchling http://pythonjournal.cognizor.com/pyj1/AMKuchling_algorithms-V1.html Copyright (c) 1998 Andrew Kuchling Background essay: http://mathforum.org/kb/thread.jspa?threadID=1543229&tstart=0 """ from random import choice def ee(a, b): """Euclid extended by Alexandru Scvortov http://snippets.dzone.com/posts/show/4192 """ if b == 0: return a, 1, 0 dd, xx, yy = ee(b, a % b) d, x, y = dd, yy, xx - (a // b) * yy return d, x, y class M: modulus = 7 """ Adds extended Euclidean (ee) for finding multiplicative inverses """ def __init__(self, val): self.val = val % M.modulus self.recip = ee(self.val, M.modulus)[1] % M.modulus def __repr__(self): return "m%s" % (self.val) def __add__(self, other): return M(self.val + other.val) def __sub__(self, other): return self + (-other) def __mul__(self, other): return M(self.val * other.val) def __truediv__(self, other): return self * other**(-1) def __neg__(self): return M(-self.val) def __pow__(self, e): # identity: m**(-e) == (m**(-1))**abs(e) if e < 0: base = self.recip else: base = self.val return M(pow(base, abs(e), M.modulus)) def __lt__(self, other): return self.val < other.val def __gt__(self, other): return self.val > other.val def __eq__(self, other): return self.val == other.val def gcd(a,b): while b: a, b = b, a % b return a def totatives(n): return [i for i in range(1,n) if gcd(i, n) == 1] def mathfact(members, ops=["*"]): while True: elem0 = choice(members) elem1 = choice(members) op = choice(ops) # no divide by zero allowed if not (op=="/" and elem1.val == 0): break if op == "*": r = elem0 * elem1 elif op == "/": r = elem0 / elem1 elif op == "+": r = elem0 + elem1 else: r = elem0 - elem1 expr = "%s %s %s" % (elem0, op, elem1) return "%s = %s" % (expr, r) def makemembers(val): M.modulus = val return [M(i) for i in totatives(val)] def report(n=7): the_members = makemembers(n) print(the_members) while True: yield mathfact(the_members,["*","/","+","-"]) def test(n=7): rg = report(n) print("Random Math Facts for M%s" % n) for i in range(10): print(next(rg))