欧拉降幂证明及应用

欧拉定理

内容

若正整数 $a,n$互质，则$a^{\phi(n)}≡1(mod n)$其中$\phi(n)$是1-n中与n互质的数的个数

证明

不妨设$X_1,X_2,{\cdots},X_n$为1~n中与n两两互质的数
那么对一些数进行讨论$aX_1,aX_2,{\cdots},aX_n$

引理1

$aX_1,aX_2,{\cdots},aX_n$中，任意两个数模n的余数一定不同。

证明

设$aX_1≡aX_2(mod n)$
则 $a(X_1-X_2)≡0(mod n)$
因为a与n互质，并且$X_1-X_2≠n$
所以不存在$aX_1≡aX_2(mod n)$
因此$aX_1,aX_2,{\cdots},aX_n$中，任意两个数模n的余数一定不同。
证毕

引理2

$aX_1,aX_2,{\cdots},aX_n$中，任意的$aX_i≡1(mod n)$

证明

因为a与n互质，$X_i$与n互质，所以$aX_i$与n互质，即$gcd(aX_i,n)==gcd(n,aX_i\%n)==1$;
因此$aX_i(mod n)≡1(mod n)$
证毕

总结

把$aX_1,aX_2,{\cdots},aX_n$都模n看成一个集合，根据引理1，这个集合具有互异性，引理2，我们发现集合中的元素与$X_1,X_2,{\cdots},X_n$中的元素是一致的。那么就有

$$aX_1(mod\ n)*aX_2(mod\ n)*{\cdots}*aX_{\phi(n)}==X_1*X_2*{\cdots}*X_{\phi(n)}$$

就可以得出

$$a^{\phi(n)}*X_1*X_2*{\cdots}*X_{\phi(n)}(mod\ n)==X_1*X_2*{\cdots}*X_{\phi(n)}$$

因为$X_1*X_2*{\cdots}*X_{\phi(n)}$与n互质，所以得到

$$a^{\phi(n)}*X_1*X_2*{\cdots}*X_{\phi(n)}==1(mod\ n)$$ $$a^{\phi(n)}≡1(mod\ n)$$

欧拉降幂

欧拉降幂其实就是下面这个式子

$$a^b≡\begin{cases} a^{b\%\phi(p)}\quad \quad \quad \ \ gcd(a,p) = 1\\ a^b\quad \quad \quad \quad \ \ \ \ \ gcd(a,p)≠1,b<\phi(p) \\ a^{b\%\phi(p)+\phi(p)}\ \ \ gcd(a,p)≠1,b ≥ \phi(p)\\ \end{cases} \quad \quad (mod\ p)$$

证明

证一

$$a^b≡a^{b\%\phi(p)}\quad \quad gcd(a,p) = 1\quad (mod\ p)$$

这个证明用到上面讲的欧拉定理
∵$b=b\%\phi(p)+k*\phi(p)$
∴$a^b=a^{b\%\phi(p)+k*\phi(p)}\quad (mod\ p)$
∵$a^{\phi(p)}≡1\quad (mod\ p)$
∴$a^{b\%\phi(p)+k*\phi(p)}=a^{b\%\phi(p)}\quad (mod\ p)$
即$a^b≡a^{b\%\phi(p)}\quad \quad gcd(a,p) = 1\quad (mod\ p)$
证毕

证二

$$a^b \ \ gcd(a,p)≠1,b<\phi(p)$$

直接得此结论

证三

$$a^{b\%\phi(p)+\phi(p)}\ \ \ gcd(a,p)≠1,b ≥ \phi(p)$$

不妨设$b=k*\phi(p)+c\quad (a≥1,c≥0)$
要证$a^{b\%\phi(p)+phi(p)}\ \ \ gcd(a,p)≠1,b > \phi(p)$
则证$a^{ k*\phi(p)+c }≡a^{ \phi(p)+c } \ (mod\ p)$
即 $a^{k*\phi(p)}≡a^{\phi(p)}\ (mod\ p)$
即 $a^{2*\phi(p)}≡a^{\phi(p)}\ (mod\ p)$
即证 $a^{\phi(p)}*(a^{\phi(p)}-1)≡ 0 (mod\ p)$

接下来假设

$$N=\frac{p}{gcd(p,a^{\phi(p)})}$$

假设$gcd(\frac{p}{gcd(p,a^{\phi(p)})},A)≡ 1 (mod\ p)\quad \quad (1)$
因为欧拉函数为积性函数，所以有

$$\phi(p)=\phi(gcd(p,a^{\phi(p)})*\phi(\frac{p}{gcd(p,a^{\phi(p)})})\quad \quad (2)$$

假设$k=gcd(p,a^{\phi(p)})\quad \quad (3)$
根据(1)(2)(3)以及欧拉定理，有

$$a^{\phi(p)}≡(a^{\frac{p}{gcd(p,a^{\phi(p)})}})^k ≡ 1\quad (mod\ \frac{p}{gcd(p,a^{\phi(p)})})$$

得到

$$a^{\phi(p)}≡ 1 \quad (mod\ \frac{p}{gcd(p,a^{\phi(p)})})$$ $$\frac{p}{gcd(p,a^{\phi(p)})} \mid (a^{\phi(p)}-1)$$

移项

$$p \mid (a^{\phi(p)}-1)*gcd(p,a^{\phi(p)})$$

因为$gcd(\frac{p}{gcd(p,a^{\phi(p)})},A)≡ 1 (mod\ p)\quad \quad (1)$
所以

$p \mid (a^{\phi(p)}-1)*a^{\phi(p)}$
与上述需证明的一致，于是证明完毕。
但是，我们是基于假设上的，也就是

$gcd(\frac{p}{gcd(p,a^{\phi(p)})},A)≡ 1 (mod\ p)\quad \quad$
所以，我们现在需要证明我们的假设
对a进行素因子分解

$$a=q_1^{k_1}*q_2^{k_2}*{\cdots}*q_t^{k_t}*p_1^{l_1}*p_2^{l_2}*{\cdots}*p_t^{l_{t1}}$$ $$p=q_1^{u_1}*q_2^{u_2}*{\cdots}*q_t^{u_t}*w_1^{v_1}*w_2^{v_2}*{\cdots}*w_t^{v_{t1}}$$

前面是相同的部分，后面是不同的部分。

$$gcd(a,p)=q_1^{min(k_1,u_1)}*q_2^{min(k_2,u_2)}*{\cdots}*q_t^{min(k_t,u_t)}$$ $$gcd(a^{\phi(p)},p)=q_1^{min(k_1*\phi(p),u_1)}*q_2^{min(k_2*\phi(p),u_2)}*{\cdots}*q_t^{min(k_t*\phi(p),u_t)}$$

根据欧拉函数的性质

$$\phi(p)=q_1^{u_1-1}*q_2^{u_2-1}*{\cdots}*q_t^{u_t-1}*(q_1-1)*(q_2-1)*(q_t-1)*{\cdots}(不相同部分不管)$$

∴

$$k_i*\phi(p)≥k_i*q_i^{u_i-1}*(q_i-1)≥q_i^{u_i-1}$$

现在需证明

$$q_i^{u_i-1}≥u_i$$

这个证明可以化成函数$x^{a-1}-a$求导后判断单调性和最小值可以证明
得出这个结果之后
即可得到

$$k_1*\phi(p)≥u_1$$ $$gcd(a^{\phi(p)},p)=q_1^{u_1}*q_2^{u_2}*{\cdots}*q_t^{u_t}$$

回到原式子以及进行质因数分解的出来的a,p；

$$gcd(\frac{p}{gcd(p,a^{\phi(p)})},a)≡ 1 (mod\ p)\quad \quad$$ $$p=q_1^{u_1}*q_2^{u_2}*{\cdots}*q_t^{u_t}*w_1^{v_1}*w_2^{v_2}*{\cdots}*w_t^{v_{t1}}$$ $$a=q_1^{k_1}*q_2^{k_2}*{\cdots}*q_t^{k_t}*p_1^{l_1}*p_2^{l_2}*{\cdots}*p_t^{l_{t1}}$$ $$\frac{p}{gcd(p,a^{\phi(p)})}=w_1^{v_1}*w_2^{v_2}*{\cdots}*w_t^{v_{t1}}$$

因为他们相同的素因子已经被除去了因此。

$$gcd(\frac{p}{gcd(p,a^{\phi(p)})},a)≡ 1 (mod\ p)\quad \quad$$

到这里全部的欧拉降幂就证明完成了。