欧拉定理（数论）
欧拉定理是一个关于同余的性质。若 \(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} \]
扩展
将欧拉定理扩展到 \(a,n\) 不互质的情况，公式为
\[ a^b \equiv \left\{\begin{array}{l} a^{b \bmod \varphi(n)} & \gcd(a,n)=1 \\ a^{b} & \gcd(a,n) \ne 1 \wedge b < \varphi(n) \\ a^{(b \bmod \varphi(n)) + \varphi(n)} & \gcd(a,n) \ne 1 \wedge b \ge \varphi(n) \end{array}\right. \pmod{n} \]
其中 \(b \in \mathbb{Z}^+\)，在 \(b\) 很大时，可以用这个公式来 降幂。
证明
设 \(b\) 除以 \(\varphi(n)\) 的欧几里得除法为
\[ b = \varphi(n)q + (b \bmod \varphi(n)) \]
则
\[ a^b = a^{\varphi(n)q + (b \bmod \varphi(n))} \]
情况 1：当 \(\gcd(a,n)=1\) 时，由欧拉定理
\[ a^b \equiv \left( a^{\varphi(n)} \right)^q \times a^{b \bmod \varphi(n)} \equiv a^{b \bmod \varphi(n)} \pmod{n} \]
情况 2：当 \(\gcd(a,n) \ne 1 \wedge b < \varphi(n)\) 时，\(b\) 不算很大，直接硬算
\[ a^b \bmod n \]
情况 3：当 \(\gcd(a,n) \ne 1 \wedge b \ge \varphi(n)\) 时，根据算术基本定理将 \(n\) 分解成质因数的乘积
\[ n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \]
然后，对于每个 \(p_i^{k_i}\) 进一步讨论。
情况 3-1：当 \(\gcd(a,p_i^{k_i})=1\) 时，因为欧拉函数是积性函数，所以
\[ \varphi(p_i^{k_i}) \mid \varphi(n) \]
因此
\[ a^{\varphi(n)} \equiv \left( a^{\varphi(p_i^{k_i})} \right)^{\varphi(n)/\varphi(p_i^{k_i})} \equiv 1 \pmod{p_i^{k_i}} \]
故
\[ a^b \equiv \left( a^{\varphi(n)} \right)^q \times a^{b \bmod \varphi(n)} \times a^{\varphi(n)} \equiv a^{(b \bmod \varphi(n)) + \varphi(n)} \pmod{p_i^{k_i}} \]
情况 3-2：当 \(\gcd(a,p_i^{k_i}) \ne 1\) 时，\(p_i \mid a\)，又注意到
\[ b \ge \varphi(n) \ge \varphi(p_i^{k_i}) = p_i^{k_i-1}(p_i - 1) \ge k_i \]
所以
\[ p_i^{k_i} \mid a^b \wedge p_i^{k_i} \mid a^{\varphi(n)} \]
故
\[ a^b \equiv a^{(b \bmod \varphi(n)) + \varphi(n)} \equiv 0 \pmod{p_i^{k_i}} \]
综合情况 3-1 和 3-2：因为
\[ a^b \equiv a^{(b \bmod \varphi(n)) + \varphi(n)} \pmod{p_i^{k_i}} \]
所以 \(\forall i \in \{1,2,\dots,r\}\) 有
\[ p_i^{k_i} \mid \left( a^b - a^{(b \bmod \varphi(n)) + \varphi(n)} \right) \]
根据整除的性质
\[ p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r} \mid \left( a^b - a^{(b \bmod \varphi(n)) + \varphi(n)} \right) \]
即
\[ a^b \equiv a^{(b \bmod \varphi(n)) + \varphi(n)} \pmod{n} \]