再学欧拉之欧拉定理
All_Unluck_Beginning
·
·
算法·理论
没错,本文的一切还是为了它 ——\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),再运算。