扩展欧拉定理（数论）¶
扩展欧拉定理是将 欧拉定理 扩展到 \(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} \]