若$(a,n)=1$,则$a^{\varphi(n)}\equiv 1(\mod n)$,其中$\varphi(n)$是$1\sim n$中与$n$互质的自然数的个数。
费马小定理是欧拉定理的特殊情况,当$n$为质数时,就是费马小定理。
举例:
若$(3,10)=1$,$\varphi(10)=10\times \left(1-\dfrac{1}{2} \right)\times \left(1-\dfrac{1}{5} \right)=4$,则$3^4\equiv 1(\mod 10)$
考虑$1$至$10$中与$10$互质的数:$1$、$3$、$7$、$9$,这$4$个数除以$10$的余数互不相同,那么
$1\times 3$、$3\times 3$、$7\times 3$、$9\times 3$这$4$个数除以$10$的余数也是互不相同的,假设这$4$个数中存在两个数$m\times 3$和$n\times 3$模$10$同余,即$m\times 3 \equiv n\times 3 (\mod 10)$,则$10|(m\times 3-n\times 3)=3(m-n)$,因为$(3,10)=1$,所以$10|m-n$,那么$m=n$,矛盾。
所以$1\times 3$、$3\times 3$、$7\times 3$、$9\times 3$这$4$个数除以$10$的余数互不相同,又不可能是$0$、$2$、$4$、$5$、$6$、$8$,所以只能是$1$、$3$、$7$、$9$
所以$(1\times 3)\times (3\times 3)\times (7\times 3)\times (9\times 3)\equiv 1\times 3\times 7\times 9(\mod 10)$
所以$3^4 \equiv 1(\mod 10)$
$1$至$n$中与$n$互质的自然数的个数是$\varphi(n)$个,记这$\varphi(n)$个数为$a_1$、$a_2$、$a_3$、$\cdots$、$a_{\varphi(n)}$,这$\varphi(n)$个数除以$n$的余数互不相同,那么$a\times a_1$、$a\times a_2$、$a\times a_3$、$\cdots$、$a\times a_{\varphi(n)}$除以$n$的余数也是互不相同的,若$a\times a_m$和$a\times a_n$模$n$同余,即$a\times a_m \equiv a\times a_n (\mod n)$,则$n|(a\times a_m-a\times a_n)=a(a_m-a_n)$,因为$(a,n)=1$,所以$n|a_m-a_n$,那么$a_m=a_n$,矛盾。
所以$a\times a_1$、$a\times a_2$、$a\times a_3$、$\cdots$、$a\times a_{\varphi(n)}$除以$n$的余数互不相同,只能为$a_1$、$a_2$、$a_3$、$\cdots$、$a_{\varphi(n)}$
所以$(a\times a_1)\cdot(a\times a_2)\cdots(a\times a_{\varphi(n)})\equiv a_1\cdot a_2\cdots a_{\varphi(n)}$
所以$a^{\varphi(n)}\equiv 1(\mod n)$
暂无评论内容