欧拉定理——数论定理

在数论中，欧拉定理也叫费马-欧拉定理，是一个关于同余的性质，欧拉定理表明，若n,a为整数，且n,a互质，则

• 证明：
• 1~n中与n互质的数按照顺序排布为x1,x2,...xφ(n)，显然有φ(n)个
• 我们考虑这么一些数
• m1=a*x1,m2=a*x2,m3=a*x3......mφ(n)=a*xφ(n)
•  1）这些数中的任意两个都不%n同余
• 设mS≡mR(modn),不妨令mS>mR
• 有mS-mR=a(xS-xR)=qn， 由于（xS-xR）<n，而a和n互质，左边式子不能整除n，则这个等式不存在
• 2）这些数除n的余数都与n互质，设余数与n有公因子r,则a*xi=z*n+y*r=r*(.....)，a*xi就不与n互质了
• 这些数除n的余数都在x1,x2,x3,....xφ(n)中，因为这是1~n中与n互质的所有数，且都小于n

由1）,2)可知，m1,m2,m3....mφ(n)必须和x1,x2,x3.....xφ(n)同余

也就是a^φ(n)*{x1*x2....*xφ(n)}≡x1*x2*x3...xφ(n)(modn)

也即a^φ(n)≡1（modn）

费马定理： a是不能被质数p整数的正整数  a^(p-1)≡1（modp） 因为φ(p)=p-1.