再学欧拉之欧拉定理

没错，本文的一切还是为了它 ——\(\varphi\)。

欧拉定理

内容

若 \(a,n\) 互质，则有 \(a^{\varphi(n)} \equiv 1 \pmod n\)。

证明

设小于 \(n\) 且与 \(n\) 互质的自然数集合（即 \(n\) 的剩余系）为：\(X:x_1,x_2,x_3,\dots ,x_{\varphi(n)},P:p_1=a\times x_1,p_2=a\times x_2,\dots,p_{\varphi(n)}=a\times x_{\varphi(n)}\)。

引理一：集合 \(P\) 中的数对 \(m\) 取模的余数两两不同。

反证法

若 \(\exists p_i \mod n=p_j \mod n(i\ne i)(x_i>x_j)\)。

则 \((p_i-p_j)\mod n=0\Longleftrightarrow a(x_i-x_j)\mod n=0\)。

因为 \(a\) 与 \(n\) 互质，\(x_i<n,x_j<n\)。

所以 \(x_i-x_j<n\)。

则 \(a(x_i-x_j)\mod n\ne0\)。

于是引理一成立。

引理二：\(P\mod n\) 的每个余数都与 \(n\) 互质。

反证法

设 \(a\times x_i=k\times n+r\)，则 \(r=a\times x_i-k\times n\)。

因为 \(r\) 与 \(n\) 互质，则 \(c=\gcd(a\times x_i-k\times n,n)>1\)。

因为 \(c\) 是 \(r\) 的约数也是 \(n\) 的约数。

则 \(k\times n,a\times x_i\) 是 \(c\) 的约数。

则 \(\gcd(a\times x_i,n)\ge c\)。

因为 \(a\) 与 \(n\) 互质，\(x_i\) 与 \(n\) 互质。

所以 \(\gcd(a\times x_i,n)=1\)。

则结论相对，所以引理二正确。

the last step

1. \(P\) 的每个数 \(\mod n\) 两两不同（引理一）。

2. \(P\) 的每个数 \(\mod n\) 与 \(n\) 互质。

3. \(P\) 的每个数 \(\mod n\) 的个数是 \(\varphi(n)\)。

4. \(X\) 是 \(varphi(n)\) 个小于 \(n\) 且与 \(n\) 互质两两不同的整数。

则推理得 \(P\) 的每个数 \(\mod n\) 与 \(X\) 所包含的数相同且一一对应。

则 \(\prod_{i=1}^{\varphi(n)}p_i \mod n=\prod_{i=1}^{\varphi(n)}x_i \mod n\)。

\((ax_1\times ax_2\times \dots \times ax_{\varphi(n)})\mod m=\prod_{i=1}^{\varphi(n)}x_i \mod n\)

\(a^{\varphi(n)}\times\prod_{i=1}^{\varphi(n)}x_i \mod n=\prod_{i=1}^{\varphi(n)}x_i \mod n\)

\(a^{\varphi(n)}\mod n=1\)

\(a^{\varphi(n)} \equiv 1\pmod n\)。

证毕。