欧拉定理（数论）¶
欧拉定理是一个关于 同余 的性质。若 \(a,n\) 为正整数且互质，则
\[ a^{\varphi(n)}\equiv 1 \pmod{n} \]
其中 \(\varphi(n)\) 是 欧拉函数。
证明¶
设 \(b_1,b_2,\dots,b_{\varphi(n)}\) 为小于等于 \(n\) 的正整数中，所有与 \(n\) 互质的数。因为 \(a,n\) 互质且 \(b_i,n\) 互质，所以 \(ab_i,n\) 互质。由 欧几里得算法
\[ \gcd(ab_i,n)=\gcd(n,ab_i \bmod n) \]
得到 \((ab_i \bmod n)\) 与 \(n\) 互质。如果 \(\exists i \ne j\) 使得
\[ ab_i \equiv ab_j \pmod{n} \]
那么
\[ n \mid a(b_i - b_j) \]
又因为 \(a,n\) 互质，根据 整除 的性质
\[ n \mid (b_i-b_j) \]
与 \(b_i,b_j \le n\) 矛盾，所以 \((ab_i \bmod n)\) 互不相等。所以
\[ \{ b_i \mid 1 \le i \le \varphi(n) \} = \{ ab_i \bmod n \mid 1 \le i \le \varphi(n) \} \]
因此
\[ a^{\varphi(n)} \prod_{i=1}^{\varphi(n)}b_i \equiv \prod_{i=1}^{\varphi(n)}ab_i \equiv \prod_{i=1}^{\varphi(n)}b_i \pmod{n} \]
进而
\[ n \mid \left ( a^{\varphi(n)} - 1 \right ) \prod_{i=1}^{\varphi(n)}b_i \]
因为 \(n\) 与 \(\displaystyle\prod_{i=1}^{\varphi(n)}b_i\) 互质，根据 整除 的性质
\[ n \mid \left ( a^{\varphi(n)} - 1 \right ) \]
即
\[ a^{\varphi(n)}\equiv 1 \pmod{n} \]
相关文章