Euler定理:对于正整数a,p,若(a,p)=1,有aφ(p)mod p=1,其中欧拉函数φ(p)=p(1-1/p_1) (1-1/p_2)......(1-1/p_k),p_1,p_2,....,p_k是p的所有的素数因子.
当p是一个素数时,它的特例如下:
Fermat 小定理:如果p是素数,(a,p)=1,则a(p-1) mod p=1.(这是因为φ(p)=p-1)
它 的应用:
1.求a^n mod(p),其中n是一个较大的数,而p是一个素数
这时就可以用费马小定理了,将a^n拆为a^(p- 1)*a^(p-1)*......*a^(n%(p-1)).这时原式就等于a^(n%(p-1)) mod(p),这样就可以大大减小运算次数,如果p还是很大,可以用反复平方的方法,复杂度在O(log(n%(p-1)))的级别.
2.给定一个正整数n，求一个最小的整数x，使得2^x mod n=1。
当n是偶数时无解。
当n是奇数时，(2,n)=1,根据Euler定理,2^phi(n)mod n=1,但phi(n)未必就是答案，因为有可能存在一个更小的解，但我们可以确信最小解x一定是phi(n)的因子,如果不是phi(n)的因子，则设n mod x=r(0<r<x)，由于2^phi(n)=2^x=1,则2^r=1,这与x是最小的解矛盾，所以命题得证，既然缩小了解的范围，下面就好办了，解法如下:
(1)求解x=phi(n);
(2)找出phi(n)的所有的素因子p_i(1<=i<=nr);
(3)for i=1……nr
让x=x/p_i
直到2^x mod n!=1 或 p_i不能整除x
if 2^x mod n!=1
x=x*p_i
(4)x就是所求解