大家对费马小定理都非常熟悉,它是说如果p为素数,则对于任意的正整数a都有p整除a^p-a。到了1736年,欧拉给出了费马小定理的严格证明。而到了1760年,欧拉又给出了费马小定理的重要推广。他首先考虑了小于给定正整数n且与n互素的正整数个数,高斯为此专门引入了一个记号Φ(n),称之为欧拉函数。
使用这个新的函数,欧拉证明了如果a和n互素,则n整除a^Φ(n)-1。注意到当n为素数p时,每个小于p的正整数都和p互素,即Φ(n)=p-1,此时欧拉推广的定理变成了对每个与p互素的a,均有p整除a^(p-1)-1当然也整除a^p-a。如果a和p不互素,即p整除a,显然有p整除a^p-a。其实这就是费马小定理。
令人惊奇的是,欧拉这个定理的证明非常简单,相比之下他的发现和提出要难的多。接下来我们来看看他的证明过程。
首先假设a和n互素,并且在1,2,3,…,n中和n互素的数为R1,R2,R3,…,Rk,则欧拉函数Φ(n)=k。接着欧拉又考虑k个数aR1,aR2,aR3,…,aRk除以n后所得的余数。一方面a和n互素,Ri也分别和n互素,所以他们的余数也和n互素。
另一方面,如果aRi和aRj除以n所得的余数相同,则n必整除他们之差,即n整除Ri-Rj,而这是不可能的。所以aR1,aR2,aR3,…,aRk除以n所得的余数不仅和n互素且两两不同。因此余数就是R1,R2,R3,…,Rk的某一个排列。所以n整除下面乘积之差:
又因为R1R2R3…Rk也和n互素,因此n整除a^k-1。至此就证明了欧拉对于费马小定理的扩展。返回搜狐,查看更多
