再学欧拉之欧拉定理

· · 算法·理论

没错,本文的一切还是为了它 ——\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

因为 an 互质,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

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

因为 cr 的约数也是 n 的约数。

k\times n,a\times x_ic 的约数。

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

因为 an 互质,x_in 互质。

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

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

the last step

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

\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,bp 取余,再将结果对 p 取余。

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