Chinese Remainder Theorem

{{{id=18| @interact def _(a=3, b=5, m=19, n=13): if gcd(m,n) != 1: print "gcd(m,n) = %s is not 1 so not calling CRT"%gcd(m,n) else: print "x = ", CRT(a,b,m,n) /// }}} {{{id=17| /// }}} {{{id=11| CRT? /// }}} {{{id=12| x = CRT(3, 5, 19, 13); x /// -73 }}} {{{id=13| x % 19 /// 3 }}} {{{id=14| x % 13 /// 5 }}} {{{id=15| (x - 174) % (19*13) /// 0 }}} {{{id=16| # it would be nice if this worked; # see http://trac.sagemath.org/sage_trac/ticket/8040 CRT(Mod(3,19), Mod(5, 13)) /// Traceback (most recent call last): # see http://trac.sagemath.org/sage_trac/ticket/8040 File "", line 1, in File "/tmp/tmpE4is5L/___code___.py", line 4, in exec compile(ur'CRT(Mod(_sage_const_3 ,_sage_const_19 ), Mod(_sage_const_5 , _sage_const_13 ))' + '\n', '', 'single') File "", line 1, in File "/home/wstein/sage/local/lib/python2.6/site-packages/sage/rings/arith.py", line 2504, in crt raise ValueError, "arguments a and b must be coprime" ValueError: arguments a and b must be coprime }}} {{{id=32| /// }}} {{{id=21| /// }}}

Extended Euclidean Algorithm (XGCD)

{{{id=30| XGCD(59, 130) /// (1, -11, 5) }}} {{{id=31| XGCD? /// }}} {{{id=26| @interact def _(a=59, b=130): g, x, y = XGCD(a,b) print "%s*(%s) + %s*(%s) = %s"%(a,x,b,y,g) ///

a
b

}}}

XGCD also works for polynomials:

{{{id=20| R. = QQ['x'] XGCD(3*x*(x-1), 15*x^3*(x-1)) /// (x^2 - x, 1/3, 0) }}} {{{id=24| /// }}}

Multiplicative Inverses

{{{id=29| Mod(6, 13)^(-1) /// 11 }}} {{{id=28| 1 / Mod(6,13) /// 11 }}} {{{id=27| @interact def _(a=6, n=13): try: x = Mod(a,n)^(-1) except: print "No inverse" else: print "%s * %s = 1 (mod %s)"%(x, a, n) ///

a
n

}}}

Addition and Multiplication Tables Modulo $n$

{{{id=36| @interact def _(n=(2..100)): A = matrix(ZZ, n, [(i+j)%n for i in [0..n-1] for j in [0..n-1]]) show(plot(A)) ///

}}} {{{id=37| @interact def _(n=(2..100)): A = matrix(ZZ, n, [(i*j)%n for i in [0..n-1] for j in [0..n-1]]) show(plot(A)) ///

}}} {{{id=35| /// }}} {{{id=19| /// }}}