一道高中数学竞赛题求解

p|n*2^n -1 ....................1式
设n=k*(p-1)+r, 0<=r1式即：p|(r-k)2^r -1
固定r值，改变k值，使r-k=0~p-1(mod p),（r-k)2^r -1两两不同余（mod p）
所以必有(r-i)2^r -1是p的倍数
则k=Z*p+i对应的n=k(p-1)+r都满足要求，显然有无穷多个。

费马小定理在数论中是用欧拉定理证明的，但欧拉定理本身就比较麻烦，不过费马小定理另有个简洁的证明方法。
对于素数p和一个任意n（n不能被p整除），令：
n = c1 mod p
2n = c2 mod p
3n = c3 mod p
...........
in = ci mod p
...........
(p-1)n = c(p-1) mod p
由于n不能被p整除且p为素数，{ci}两两互不相等。因为如果有x,y 再将上面那些式子连乘，得到：(p-1)! * n^(p-1) = Πci mod p
由于ci两两互不相等，它们只是1..(p-1)的一个乱序排列，所以 Πci = (p-1)! 。
用(p-1)! 去除上面那个式子即得：n^(p-1) = 1 mod p