欧拉定理及其证明

我真的很逊，所以有错也说不定。
这篇很简，所以看不懂也说不定。

总觉得小满哥讲过这个证明，虽然身为老年健忘选手我大概是不记得什么了。。

欧拉定理： $a^{\phi \left(n\right)}\equiv 1\left(modn\right)$aφ(n)≡1 (mod n) ，其中 $(a,n)=1$(a,n)=1
费马小定理： $a^{p-1}\equiv 1\left(modp\right)$ap−1≡1 (mod p) ，其中 $(a,p)=1$(a,p)=1 ，容易发现是欧拉定理的一种特殊情况。

欧拉定理证明：（同余式默认模 $n$n）
设 $X_1,X_2,...,X_{\phi \left(n\right)}$X1​,X2​,...,Xφ(n)​ 是 $1$1 到 $n$n 里与 $n$n 互质的数，容易发现它们模 $n$n 两两不同，且余数都与 $n$n 互质（废话，因为模了之后还是原数嘛）

然后我们发现 $a{X}_1,a{X}_2,...,a{X}_{\phi \left(n\right)}$aX1​,aX2​,...,aXφ(n)​ 好像也有如上两个性质。。

模 $n$n 两两不同：反证，若 $a{X}_i\equiv a{X}_j\left(modn\right)$aXi​≡aXj​ (mod n) ，则 $a{X}_i-a{X}_j\equiv 0$aXi​−aXj​≡0 ，则 $a(X_i-X_j)\equiv 0$a(Xi​−Xj​)≡0 ，由于 $a$a 与 $n$n 互质 ， $X_i-X_j$Xi​−Xj​ 不可能是 $n$n 的倍数，所以模 $n$n 一定不为 $0$0

余数都与 $n$n 互质： $a$a 与 $n$n 互质， $X_i$Xi​ 与 $n$n 互质，所以 $a{X}_i$aXi​ 也 与 $n$n 互质 （这很感性理解orz）

有了这两个性质，我们就可以发现 $a{X}_1,a{X}_2,...,a{X}_{\phi \left(n\right)}$aX1​,aX2​,...,aXφ(n)​ 模 $n$n 后一定是 $\phi \left(n\right)$φ(n) 个不同的与 $n$n 互质的数，那不就肯定是 $X_1,X_2,...,X_{\phi \left(n\right)}$X1​,X2​,...,Xφ(n)​ 这个集合。

所以得到 $X_1\cdot X_2...X_{\phi \left(n\right)}\equiv a{X}_1\cdot a{X}_2...a{X}_{\phi \left(n\right)}\left(modn\right)$X1​⋅X2​...Xφ(n)​≡aX1​⋅aX2​...aXφ(n)​ (mod n)

$\Rightarrow 1\equiv a^{\phi \left(n\right)}\left(modn\right)$⇒1≡aφ(n) (mod n)

$QED.$QED.