回顾

再看一下前置知识

一定要熟悉欧拉函数的三条性质

正文

欧拉定理

若\(a\)与\(m\)互质，则\(a^{\phi(m)}\equiv 1\pmod{m}\)。其中\(\phi()\)为欧拉函数。

证明：设\(\leq m\)且与\(m\)互质的正整数的集合为\(T=\{x_1,x_2,x_3,...,x_{\phi(m)}\}\)

令\(S={ax_1\%m,ax_2\%m,...,ax_{\phi(m)}}\%m\)

任取\(i\in\{1,\phi(m)\}\)

因为\(\gcd(a,m)=1,\gcd(x_i,m)=1\)

所以\(\gcd(ax_i,m)=1\)

所以\(\gcd(ax_i\%m,m)=1\)（辗转相除法）

因为\(S\)中的元素\(ax_i\%m\)于\(m\)互质且均小于\(m\)，所以\(S=T\)。

接下来的推导请看图

因为\(x_i\)与\(m\)互质，两边的一大坨约掉，证毕。

欧拉定理的推论

对于任意正整数\(b\)

\(a^b\equiv a^{b\%\phi(m)}\pmod{m}\)

证明：

设\(b=q\phi(m)+r\)，其中\(r=b\%\phi(m)\)

扩展欧拉定理

\(a,m\)不需要互质

若\(b\geq \phi(m)\)，则\(a^b\equiv a^{b\%\phi(m)+\phi(m)}\pmod{m}\)

证明不会。

应用

当\(b\)特别大时，先对\(b\)关于\(\phi(m)\)取模，然后再计算，对\(m\)取模

有的人会问，如果\(b<\phi(m)\)怎么办呢？直接快速幂啊！！！