初等数论--欧拉定理及证明
0. 证明前置知识
同余类（剩余类）
r n ‾ = { x ∣ x = m n + r , m ∈ Z } \overline{r_n} = \{ x| x=mn+r,m \in Z\} rn={x∣x=mn+r,m∈Z}
r n ‾ \overline{r_n} rn表示模 n n n后余 r r r的同余类（剩余类）
比如
2 5 ‾ = { ⋯ , − 3 , 2 , 7 , 12 , ⋯ } \overline{2_5} = \{\cdots, -3,2,7,12,\cdots\} 25={⋯,−3,2,7,12,⋯}
我们从 0 n ‾ 1 n ‾ 2 n ‾ ⋯ n − 1 n ‾ \overline{0_n}\ \overline{1_n}\ \overline{2_n}\cdots \overline{{n-1}_n} 0n 1n 2n⋯n−1n中各挑选一个数，就组成了模 n n n的完全剩余系（简称完系）。
记作
R n = { r 0 , r 1 , ⋯ , r n − 1 } r 0 ∈ 0 n ‾ , ⋯ , r n − 1 ∈ n − 1 n ‾ R_n=\{ r_0,r_1,\cdots,r_{n-1}\}\\ r_0 \in \overline{0_{n}},\cdots,r_{n-1}\in \overline{{n-1}_n} Rn={r0,r1,⋯,rn−1}r0∈0n,⋯,rn−1∈n−1n
R n R_n Rn被叫做 n n n的一个完全剩余系。
如果 R n = { 0 , 1 , 2 , ⋯ , n − 1 } R_n=\{ 0,1,2,\cdots,n-1\} Rn={0,1,2,⋯,n−1}, 那么称 R n R_n Rn为模 n n n的最小非负完全剩
余系。
比如 R 4 = { 0 , 1 , 2 , 3 } R_4=\{\ 0,1,2,3\} R4={ 0,1,2,3}
取模 n n n的一个完全剩余系 R n R_n Rn, 在 R n R_n Rn中取出与 n n n 互质的数，组成的新的集合，叫做模 n n n的缩剩余系（简称缩系），记为 Φ n \Phi_n Φn。
比如
R 4 = { 4 , − 3 , 6 , 3 } Φ 4 = { − 3 , 3 } R_4 =\{ 4,-3,6,3\}\\ \Phi_4 =\{ -3,3\} R4={4,−3,6,3}Φ4={−3,3}
如果 Φ n = { c 1 , c 2 , ⋯ , c ϕ ( n ) } \Phi_n=\{ c_1,c_2,\cdots,c_{\phi(n)}\} Φn={c1,c2,⋯,cϕ(n)}满足 1 ≤ c 1 , c 2 , ⋯ , c ϕ ( n ) ≤ n − 1 1\le c_1,c_2,\cdots,c_{\phi(n)} \le n-1 1≤c1,c2,⋯,cϕ(n)≤n−1,
那么称 Φ n \Phi_n Φn为最小正缩剩余系。
1. 欧拉定理
若 gcd ( a , n ) = 1 \gcd(a,n) =1 gcd(a,n)=1, 那么
a ϕ ( n ) ≡ 1 ( m o d n ) a^{\phi(n)} \equiv1\quad(\ \bmod\ n) aϕ(n)≡1( mod n)
2. 证明
我们令 Φ n \Phi_n Φn为模 n n n的最小正缩系
Φ n = { c 1 , c 2 , ⋯ , c ϕ ( n ) } \Phi_n=\{ c_1,c_2,\cdots,c_{\phi(n)}\} Φn={c1,c2,⋯,cϕ(n)}
我们将 Φ n \Phi_n Φn中每个元素同时乘上 a a a，得到 a Φ n a\Phi_n aΦn
a Φ n = { a c 1 , a c 2 , ⋯ , c a ϕ ( n ) } a\Phi_n=\{ ac_1,ac_2,\cdots,ca_{\phi(n)}\} aΦn={ac1,ac2,⋯,caϕ(n)}
我们证明 a Φ n a\Phi_n aΦn也是模 n n n的一个缩系。
由于 gcd ( a , n ) = 1 , gcd ( c j , n ) = 1 , 1 ≤ j ≤ ϕ ( n ) \gcd(a,n)=1,\gcd(c_j,n)=1, 1\le j\le \phi (n) gcd(a,n)=1,gcd(cj,n)=1,1≤j≤ϕ(n),那么必然有
gcd ( a c j , n ) = 1 \gcd(ac_j, n)=1 gcd(acj,n)=1。
因此我们只需要证明
∀ 1 ≤ i , j ≤ ϕ ( n ) , i ≠ j ; a c i ≢ a c j ( m o d n ) \forall 1 \le i,j \le \phi(n), i \ne j; ac_i \not{\equiv} \ ac_j\quad(\ \bmod \ n) ∀1≤i,j≤ϕ(n),i=j;aci≡ acj( mod n)
就能证明 a Φ n a\Phi_n aΦn是模 n n n的一个缩系。
我们假设
∃ 1 ≤ i , j ≤ ϕ ( n ) , i ≠ j , s . t . a c i ≡ a c j ( m o d n ) \exists 1 \le i,j \le \phi(n), \ i \ne j, \ s.t.\\ ac_i \equiv ac_j \quad (\ \bmod\ n) ∃1≤i,j≤ϕ(n), i=j, s.t.aci≡acj( mod n)
由于 gcd ( a , n ) = 1 \gcd(a,n)=1 gcd(a,n)=1，那么 a − 1 ( m o d n ) a^{-1} \quad(\ \bmod\ n) a−1( mod n)即 a a a在模 n n n下的逆元必定
存在。
a c i ≡ a c j ( m o d n ) a − 1 a c i ≡ a − 1 a c j ( m o d n ) c i ≡ c j ( m o d n ) ac_i \equiv ac_j \quad (\ \bmod\ n)\\ a^{-1}ac_i \equiv a^{-1}ac_j \quad (\ \bmod\ n)\\ c_i \equiv c_j \quad (\ \bmod \ n) aci≡acj( mod n)a−1aci≡a−1acj( mod n)ci≡cj( mod n)
这与 c i ≢ c j ( m o d n ) c_i \not{\equiv} \ c_j \quad (\ \bmod \ n) ci≡ cj( mod n)矛盾，因此
∀ 1 ≤ i , j ≤ ϕ ( n ) , i ≠ j , a c i ≢ a c j ( m o d n ) \forall 1 \le i,j \le \phi(n), i \ne j , ac_i \not{\equiv} ac_j \quad (\ \bmod \ n) ∀1≤i,j≤ϕ(n),i=j,aci≡acj( mod n)
即 a Φ n a\Phi_n aΦn也是模 n n n的一个缩系。
那么必然有
Π i = 1 ϕ ( n ) c i ≡ Π i = 1 ϕ ( n ) a c i ( m o d n ) ≡ a ϕ ( n ) Π i = 1 ϕ ( n ) c i ( m o d n ) \begin{align*} \Pi_{i=1}^{\phi(n)} c_i &\equiv \Pi_{i=1}^{\phi(n)}ac_i \quad (\ \bmod \ n)\\ & \equiv a^{\phi(n)} \Pi_{i=1}^{\phi(n)}c _i \quad (\ \bmod \ n) \end{align*} Πi=1ϕ(n)ci≡Πi=1ϕ(n)aci( mod n)≡aϕ(n)Πi=1ϕ(n)ci( mod n)
显然 gcd ( Π i = 1 ϕ ( n ) c i , n ) = 1 \gcd(\Pi_{i=1}^{\phi(n)}c_i, n)=1 gcd(Πi=1ϕ(n)ci,n)=1, 因此 Π i = 1 ϕ ( n ) c i \Pi_{i=1}^{\phi(n)}c_i Πi=1ϕ(n)ci在模 n n n意义下存在逆元。
因此上面的等式两端可以消去 Π i = 1 ϕ ( n ) c i \Pi_{i=1}^{\phi(n)}c_i Πi=1ϕ(n)ci, 最终得到
a ϕ ( n ≡ 1 ( m o d n ) a^{\phi(n} \equiv 1\quad (\ \bmod \ n) aϕ(n≡1( mod n)
Q . E . D Q.E.D Q.E.D
3. 参考
zhihu
群论的证明就暂时不补了。。。