414: lecture 7 (2010-01-20)

855 days ago by wstein

The order (or "period") of an element:
a = Mod(3,11) print a 
       
a.multiplicative_order() 
        
5
5
%auto @interact def _(a = 3, n = 11): a = Mod(a, n) if gcd(a,n) == 1: print "order = ", a.multiplicative_order() print [a^i for i in [1..2*n]] 
       
a 
n 

Click to the left again to hide and once more to show the dynamic interactive window
 
       

Euler's Theorem
%auto @interact def _(a = 3, n = 11): a = Mod(a, n) if gcd(a,n) == 1: print "order = ", a.multiplicative_order() print "phi(n) = ", euler_phi(n) else: print "gcd(a,n) = %s which isn't 1"%gcd(a,n) print "a^phi(n) = %s"%(a^euler_phi(n)) 
       
a 
n 

Click to the left again to hide and once more to show the dynamic interactive window
 
       

Wilson's Theorem
%auto @interact def _(p=(2..200)): print "is_prime(p) = %s"%is_prime(p) print "(p-1)! = %s"%factorial(p-1) print "(p-1)! mod p = %s"%( factorial(p-1) % p ) 
       
p 

Click to the left again to hide and once more to show the dynamic interactive window

According to Wilson's theorem, 2011 is prime:
factor(2011) 
        
2011
2011
n = factorial(2010) 
       
len(n.digits()) 
        
5769
5769
n % 2011 
        
2010
2010
 
       

Chinese Remainder Theorem
%auto @interact def _(a=2, b=3, m=3, n=5): if gcd(m,n) != 1: print "gcd(m,n) = %s which is not 1"%gcd(m,n) return x = CRT(a,b,m,n) print "x = %s"%x print "x mod %s = %s"%(m, x%m) print "x mod %s = %s"%(n, x%n) 
       
a 
b 
m 
n 

Click to the left again to hide and once more to show the dynamic interactive window