再学欧拉之欧拉定理

· · 算法·理论

没错，本文的一切还是为了它 ——\varphi。

欧拉定理

内容

若 a,n 互质，则有 a^{\varphi(n)} \equiv 1 \pmod n。

证明

设小于 n 且与 n 互质的自然数集合（即 n 的剩余系）为：X:x_1,x_2,x_3,\dots ,x_{\varphi(n)},P:p_1=a\times x_1,p_2=a\times x_2,\dots,p_{\varphi(n)}=a\times x_{\varphi(n)}。

引理一：集合 P 中的数对 n 取模的余数两两不同。

反证法

若 \exists p_i \mod n=p_j \mod n(i\ne i)(x_i>x_j)。

则 (p_i-p_j)\mod n=0\Longleftrightarrow a(x_i-x_j)\mod n=0。

因为 a 与 n 互质，x_i<n,x_j<n。

所以 x_i-x_j<n。

则 a(x_i-x_j)\mod n\ne0。

于是引理一成立。

引理二：P\mod n 的每个余数都与 n 互质。

反证法

设 a\times x_i=k\times n+r，则 r=a\times x_i-k\times n。

因为 r 与 n 互质，则 c=\gcd(a\times x_i-k\times n,n)>1。

因为 c 是 r 的约数也是 n 的约数。

则 k\times n,a\times x_i 是 c 的约数。

则 \gcd(a\times x_i,n)\ge c。

因为 a 与 n 互质，x_i 与 n 互质。

所以 \gcd(a\times x_i,n)=1。

则结论相对，所以引理二正确。

the last step

则推理得 P 的每个数 \mod n 与 X 所包含的数相同且一一对应。

则 \prod_{i=1}^{\varphi(n)}p_i \mod n=\prod_{i=1}^{\varphi(n)}x_i \mod n。

(ax_1\times ax_2\times \dots \times ax_{\varphi(n)})\mod m=\prod_{i=1}^{\varphi(n)}x_i \mod n a^{\varphi(n)}\times\prod_{i=1}^{\varphi(n)}x_i \mod n=\prod_{i=1}^{\varphi(n)}x_i \mod n a^{\varphi(n)}\mod n=1 证毕。 ## 欧拉定理的推论 若正整数 $a,n$ 互质，则对于任意正整数 $b$，有 $a^b\equiv a^{b\bmod \varphi(n)}\pmod n$。 ### 证明： 设 $b=q\times\varphi(n)+r,(0\le r<varphi(n))$。 用另一种说法就是 $r=b\bmod p$。 于是： $a^b\equiv (a^{q\times\varphi(n)}+r)\equiv(a^{varphi(n)})^q\times a^r\pmod n

有欧拉定理得 a^{\varphi(n)} 是 n 的倍数，所以 (a^{varphi(n)})^q 这里可以化简为 1。

则 a^b\equiv a^r\equiv a^{b\bmod \varphi(n)}\pmod n。

证毕。

欧拉定理简单运用

当计数类题目要求结果对质数 p 取余，面对 a+b,a\times b 之类的算式，先将 a,b 对 p 取余，再将结果对 p 取余。

对于 a^b，将 a\bmod p,b\bmod\varphi(p)，再运算。