欧拉定理及扩展欧拉定理

###欧拉定理

$\forall~a,m \in Z^+$,若$\gcd(a,m)=1$,则$a^{\phi(m)} \equiv 1(mod~m)$

假设这$\phi(m)$个数为$X_1,X_2,...,X_{\phi(m)}$

引理1 $X_i$两两模$m$不同余

证明

$\forall 1\le i,j \le \phi(m)$且$i \ne j$,那么

$$X_i~mod~m = X_i \ne X_j = X_j~mod~m$$

$$X_i \not\equiv X_j (mod~m)$$

证毕

设 $p_i=a\times X_i$

引理2 $p_i$ 之间两两模 $m$ 不同余

证明

$\forall 1\le i,j \le \phi(m)$且$i \ne j$

假设 $p_i$ 与 $p_j$ 同余,那么

$$a \times X_i \equiv a \times X_j (mod~m)$$

$$\because \gcd(a, m) = 1$$

$$\therefore X_i \equiv X_j (mod~m)$$

矛盾,故$p_i \not\equiv p_j (mod~m)$

证毕

引理3 $p_i$ 与 $m$ 互质

证明

写出他们的唯一分解式

$$m=P_1^{d_1}P_2^{d_2}...P_k^{d_k}$$

$$a=P_1^{f_1}P_2^{f_2}...P_k^{f_k}$$

$$X_i=P_1^{e_1}P_2^{e_2}...P_k^{e_k}$$

$$p_i=P_1^{e_1+d_1}P_2^{e_2+d_2}...P_k^{e_k+d_k}$$

可知$\forall d_i \ne 0$,都有$e_i=f_i=0$,所以 $e_i+f_i=0$

所以$p_i$ 与 $m$ 互质

证毕

$\because a$ 与 $m$ 互质, $X_i$ 也与 $m$ 互质

$\therefore aX_i$ 也与 $m$ 互质

所以 $aX_i$ 模 $m$ 后一定是 $\phi(m)$ 个与 $m$ 互质的数, 即$X_1...X_{\phi(m)}$

所以 $X_1X_2...X_{\phi(m)}\equiv aX_1aX_2...aX_{\phi(m)} (mod~m)$

即$1\equiv a^{phi(m)} (mod~m)$

###扩展欧拉定理

$$a^c \equiv \begin{cases}a^{c~mod~\phi(m)},gcd(a,m)=1\\a^c,gcd(a,m)\ne 1,c<\phi(m)\\a^{c~mod~\phi(m)+\phi(m)},gcd(a,m)\ne 1,c \ge \phi(m) \end{cases}$$

首先证明 $gcd(a,m)=1$ 的情况,当 $m=1$ 时,显然成立.当 $m \ne 1$ 时,因为 $a^{\phi(m)} \equiv 1 (mod~m)$,每 $\phi(n)$ 个数字就相当于乘了一个 $1$, 所以 $a^c \equiv a^{c~mod~\phi(m)}$

然后是 $gcd(a,m) \ne 1$, 若 $c < \phi(m)$, 直接快速幂计算即可.

接下来证明 $c \ge \phi(m)$ 的情况, 只需要 $a$ 的任意一个质因子满足即可

考虑取 $a$ 的一个质因子 $p$, 令 $m = t \times p^r,\gcd(t,p)=1$

显然 $r \le \phi(m)$, 证明如下：

---

因为$\phi$是个积性函数,满足 $\phi(ab)=\phi(a)\phi(b)$

那么 $\phi(m)=\phi(t) \times \phi(p^r) \ge phi(p^r),t=1,2$ 时取等

又有 $\phi(p^r)=p^r-p^{r-1}=(p-1) \times p^{r-1} \ge p^{r-1},p\ge 2,p=2$ 时取等

数学归纳法证明 $p^{r-1} \ge r$, 当 $r=1$ 时成立, 假设 $r=i$ 时 $p^{i-1} \ge i$成立, $p^{i}=p \times p^{i-1} \ge 2 \times p^{i-1}=p^{i-1}+p^{i-1} \ge p^{i-1}+1 \ge i+1$ 成立

因此对于任意 $p,r \in Z, p \ge 2, r \ge 1$, 都有 $p^{r-1} \ge r$ 成立

将不等式串起来, 得到 $r \le \phi(m)$

---

显然 $p^{\phi(t)} \equiv 1 (mod~t)$,

又因为 $\phi(m)=\phi(t)\phi(p^r) \Rightarrow \phi(t)|\phi(m)$

所以 $p^{\phi(m)}=(p^{\phi(t)})^{\phi(p^r)} \equiv 1^{\phi(p^r)}=1 (mod~t)$,根据同余的性质

两边同乘一个 $p^r \Rightarrow p^{\phi(m)+r}\equiv p^r (mod~m)$

那么 $p^c \equiv p^{c-r+r} \equiv p^{c-r+\phi(m)+r} \equiv p^{\phi(m)+c} (mod~m)$

可得 $p^c \equiv p^{k\phi(m)+c}(mod~m) \Rightarrow p^c \equiv p^{c~mod~\phi(m)+\phi(m)}$

令 $f(x)=p^x\mod~m(x\ge\phi(m))$

将上式写成函数递推式可得 $f(x)=f(x-\phi(m))$,函数定义域需满足 $x\ge\phi(m)$,即 $x\ge 2\phi(m)$ 时可使用此递推式,所以在模后面加个 $\phi(m)$

考虑 $p^k$,$(p^k)^c = p^ck \equiv p^{ck+k\phi(m)} \equiv (p^k)^{\phi(m)+c} \equiv (p^k)^{c~mod~\phi(m)+\phi(m)}(mod~m)$,成立

令 $a=\prod p_i^{k_i}$,根据同余的性质,$a^c \equiv a^{c~mod~\phi(m)+\phi(m)}$成立