定理——数论定理"/>
欧拉定理——数论定理
在数论中,欧拉定理也叫费马-欧拉定理,是一个关于同余的性质,欧拉定理表明,若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.
更多推荐
欧拉定理——数论定理
发布评论