The order (or "period") of an element:
{{{id=7|
a = Mod(3,11)
print a
///
}}}
{{{id=6|
a.multiplicative_order()
///
5
}}}
{{{id=2|
%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]]
///
}}}
{{{id=3|
///
}}}
Euler's Theorem
{{{id=4|
%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))
///
}}}
{{{id=11|
///
}}}
Wilson's Theorem
{{{id=10|
%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 )
///
}}}
According to Wilson's theorem, 2011 is prime:
{{{id=9|
factor(2011)
///
2011
}}}
{{{id=13|
n = factorial(2010)
///
}}}
{{{id=15|
len(n.digits())
///
5769
}}}
{{{id=14|
n % 2011
///
2010
}}}
{{{id=19|
///
}}}
Chinese Remainder Theorem
{{{id=18|
%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)
///
}}}
{{{id=16|
///
}}}