细谈欧拉降幂

Sunset_afterglow · 2025-01-13 15:31:11 · 算法·理论

欧拉降幂公式：

证明

• 当 (A ,m) = 1 时，由欧拉定理得 A^{\varphi(m)}\equiv 1\pmod m \therefore A^k \equiv A^{k+\varphi(m)}\pmod m \because A^{\varphi(m)} = 1 \therefore A^k \div A^{\varphi(m)} = A^k = A^{k - \varphi(m)} \therefore A^{k-a\times\varphi(m)} = A^k (a\times\varphi(m) < k) \therefore A^{k \bmod \ \varphi(m)} = A^k \therefore A^k \equiv A^{k \bmod \ \varphi(m) + \varphi(m)}\pmod m
• 当 (A ,m)\ne1 时
  设 k=a\times\varphi(m)+c (a 为正整数，c 为当 a 取最大值时的 k-a\times\varphi(m))，则 A^k \equiv A^{a\times\varphi(m)+c}\equiv A^{\varphi(m)+c}\ \pmod m，即证明 A^{a\times\varphi(m)}\equiv A^{\varphi(m)}\ \pmod m $\therefore$ 不妨将 $a$ 的值取为 $2$，即 $A^{2\times\varphi(m)}\equiv A^{\varphi(m)}\ \pmod m

  由 A^{2\times\varphi(m)}\equiv A^{\varphi(m)}\ \pmod m 移项得 A^{\varphi(m)}(A^{\varphi(m) - 1}) \equiv 0\ \pmod m

  \therefore m\mid A^{\varphi(m)}(A^{\varphi(m)} - 1)

  若有 (\frac{m}{(m ,A^{\varphi(m)})},A) = 1 那么根据欧拉定理可得 A^k \equiv A^{k\times\varphi(\frac{m}{(m ,A^{\varphi(m)})})}\equiv (A^{\varphi(\frac{m}{(m ,A^{\varphi(m)})})})^k\equiv1\ \pmod m
  移项得 \frac{m}{(m ,A^{\varphi(m)})} \mid (A^{\varphi(m)} - 1)
  同乘 \frac{m}{(m ,A^{\varphi(m)})} 得 m \mid A^{\varphi(m)}(A^{\varphi(m)} - 1)
  此时进行质因子分解：

  A = P_1^{c_1}\times P_2^{c_2}\times \cdots \times P_{t1}^{c_{t1}}\times q_1^{b_1}\times q_2^{b_2}\times \cdots \times q_{t2}^{q_{t2}} m = P_1^{r_1}\times P_2^{r_2}\times \cdots \times P_{t1}^{r_{t1}}\times d_1^{r_1}\times d_2^{r_2}\times \cdots \times d_{t3}^{r_{t3}} (A ,m) = P_1^{\min(c_1 ,r_1)}\times P_2^{\min(c_2 ,r_2)}\times \cdots \times P_{t1}^{\min(c_{t1} ,r_{t1})} (A^{\varphi(m) ,m}) = P_1^{\min(c_1 \times \varphi(m) ,r_1)}\times P_2^{\min(c_2\times \varphi(m) ,r_2)}\times \cdots \times P_{t1}^{\min(c_{t1}\times \varphi(m) ,r_{t1})} P_i^{r_i - 1}(P_i - 1) \therefore P_i^{r_i-1} \ge r_i 令 $\operatorname{f}(x) = \frac{ln(x)}{x-1}$，得 $\operatorname{f}(2)=\ln(2) \le2 P_i^{r_i - 1}(P_i - 1) # 证毕（纯证明，无例题）