扩展欧拉定理证明

· · 算法·理论

定理内容

## 定理证明 - 若 $(a,m) = 1$，由欧拉定理知 $$\begin{aligned} a^b &\equiv a^{b \bmod \varphi(m)+\lfloor \frac{b}{\varphi(m)}\rfloor \times \varphi(m)} \\ &\equiv a^{b \bmod \varphi(m)} \times a^{\lfloor \frac{b}{\varphi(m)}\rfloor \times \varphi(m)} \\ & \equiv a^{b \bmod \varphi(m)} \times 1 \\ & \equiv a^{b \bmod \varphi(m)} \times a^{\varphi(m)} \\ & \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod m \end{aligned}$$ 得证。 - 若 $(a,m) \ne 1$，对 $m$ 进行质因数分解： $$m = {p_1}^{\alpha_1} {p_2}^{\alpha_2} \cdots {p_k}^{\alpha_k}$$ 先给出一个引理：若 $x \equiv y \pmod p $ 且 $x \equiv y \pmod q$，以及 $(p,q) = 1$，那么有 $x \equiv y \pmod {pq}$。这一引理由 $x \equiv y \pmod p \Leftrightarrow p \mid (x-y)$ 易证。 所以我们由引理知道，只要证明对于任意的 $1 \le i \le k$，都有 $a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod {p_i^{\alpha_i}}$ 即可证明扩展欧拉定理。 接着，我们对任意的 $1 \le i \le k$ 进行分类讨论。 性质 1：$\varphi({p_i}^{\alpha_i}) \mid \varphi(m)$，由欧拉函数是积性函数得到。 性质 2：$若 (a,{p_i}^{\alpha_i}) = 1$，那么 $a^{\varphi(m)} \equiv 1 \pmod {{p_i}^{\alpha_i}}$。证明只需把 $a^{\varphi(m)}$ 转换成 $a^{\varphi({p_i}^{\alpha_i})}$ 的若干次幂就好了。 - 若 $(a,{p_i}^{\alpha_i}) = 1$，根据性质 1 和性质 2，有 $$\begin{aligned} a^b & \equiv a^{b \bmod \varphi(m)} \times a^{\lfloor \frac{b}{\varphi(m)}\rfloor \times \varphi(m)} \\ & \equiv a^{b \bmod \varphi(m)} \\ & \equiv a^{b \bmod \varphi(m)} \times a^{\varphi(m)} \\ & \equiv a^{b \bmod m + \varphi(m)} \pmod {{p_i}^{\alpha_i}} \end{aligned}$$ - 若 $(a,{p_i}^{\alpha_i}) \ne 1$，那么就有 $p_i \mid a$，设 $a = x p_i$。 引理 1：${p_i}^{\alpha_i} > \alpha_i$。考虑证明。注意到 $\varphi({p_i}^{\alpha_i}) = {p_i}^{\alpha_i}-{p_i}^{\alpha_{i}-1}$，对于每一个 $0 \le t \le \alpha_i$ 的 $\varphi({p_i}^t)$ 展开后作和，得： $${p_i}^{\alpha_i} = 1 + \varphi(p_i) + \varphi({p_i}^2) + \cdots + \varphi({p_i}^{\alpha_i})$$ 由于 $\varphi(k) \ge 1$，所以 ${p_i}^{\alpha_i} \ge (\alpha_i + 1) \times 1 = \alpha_i + 1 > \alpha_i$。 引理 1 证毕。 引理 2：$\varphi({p_i}^{\alpha_i}) \ge \alpha_i$。考虑用上面引理 1 来证明。因为 $\varphi({p_i}^{\alpha_i}) = {p_i}^{\alpha_i - 1}(p_i - 1)$。而根据引理 1，有 ${p_i}^{\alpha_i - 1} > \alpha_i - 1$，也就是说，${p_i}^{\alpha_i - 1} \ge \alpha_i$。所以 $\varphi({p_i}^{\alpha_i}) = {p_i}^{\alpha_i - 1}(p_i - 1) \ge \alpha_i (p_i - 1) \ge \alpha_i$。 引理 2 证毕。 所以 $b \ge \varphi(m) \ge \varphi({p_i}^{\alpha_i}) \ge \alpha_i$。 所以 ${p_i}^{\alpha_i} \mid a^{b \bmod \varphi(m) + \varphi(m)}$ 以及 ${p_i}^{\alpha_i} \mid a^b$（将 $a$ 用 $xp_i$ 代换即可证明）。 所以 $a^{b \bmod \varphi(m) + \varphi(m)} \equiv a^b \equiv 0 \pmod {{p_i}^{\alpha_i}}$。 综上，定理得证。