1.3.2　欧拉定理

1.欧拉函数ф（m）

欧拉函数ф（m）指小于m且与m互质的正整数的个数.

ф（m）=m-1（m是素数）；

若，则ф（m）=m（1-1/q1）（1-1/q2）…（1-1/qi）.

例如，m=2×3，ф（m）=ф（6）=6（1-1/2）（1-1/3）=（2-1）（3-1）=2.与6互质的数是1，5.

2.欧拉定理

定理1.3.1（欧拉定理）　设a，n∈N，（a，n）=1，则aф（n）≡1（mod n）.

证　设x1，x2，…，xф（n）是全部ф（n）个与n互素的数，（a，n）=1，考察

a×x1（mod n），a×x2（mod n），…，a×xф（n）（mod n）　　（1.3.1）

式（1.3.1）中各项的乘积等于（aф（n）（x1×x2×…×xф（n）））（mod n）

另一方面，由于a，n互素，xi也与n互素，则axi也一定与n互素.

又因为对于xi和xj，如果xi≠xj，则axi（mod n）≠axj（mod n），这由a，p互素和消去律可以得出，因此axi是x1，x2，…，xф（n）中的某一个.所以

（ax1×ax2×…×axф（n））（mod n）

=（ax1（mod n）×ax2（mod n）×…×axф（n）（mod n））（mod n）

=（x1×x2×…×xф（n））（mod n）

所以，式中各项的乘积等于x1，x2，…，xф（n）的乘积.因此（aф（n）（x1×x2×…×xф（n）））（mod n）=（x1×x2×…×xф（n））（mod n），而x1×x2×…×xф（n）（mod n）和n互质，根据消去律，可以从等式两边约去，得到

aф（n）≡1（mod n）

证毕.

推论1.3.1　对于互素的数a，n，满足aф（n）+1≡a（mod n）.

定理1.3.2（费马定理）　a是不能被素数p整除的正整数，则有a（p-1）≡1（mod p）

证明这个定理非常简单，由于ф（p）=p-1，代入欧拉定理即可证明.

推论1.3.2　对于不能被素数p整除的正整数a，有ap≡a（mod p）.