欧拉定理

欧拉定理

在学习欧拉定理之前，请先了解。定理：若\(gcd(a,m)=1\)，则\(a^{\varphi(m)}\equiv1(mod\:m)\)。

证明

欧拉定理的证明还是很简单的，我们只需要构造一个与\(m\)互质的数列，再进行操作。

设\(k_1,k_2,\dots,k_{\varphi(m)}\)为模\(m\)意义下的简化剩余系，则\(a\times k_1,a\times k_2,\dots,a\times k_{\varphi(m)}\)也为模\(m\)意义下的一个简化剩余系。所以\(k_1\times k_2\times\dots\times k_{\varphi(m)}\equiv a\times k_1\times a\times k_2\times\dots\times a\times k_{\varphi(m)}=a^{\varphi(m)}\times k_1\times k_2\times\dots\times k_{\varphi(m)}(mod\:m)\)，可以约去\(k_1\times k_2\times\dots\times k_{\varphi(m)}\)，即为\(a^{\varphi(m)}\equiv1(mod\:m)\)。证毕。

欧拉定理的一些推论

1. \[a^b= \begin{cases} a^{b\:mod\:\varphi(p)},\quad\quad\quad gcd(a,p)=1\\ a^b,\quad\quad\quad\quad\quad\quad gcd(a,p)\neq1,b<\varphi(p)\quad(mod\:p)\\ a^{b\:mod\:\varphi(p)+\varphi(p)},\quad gcd(a,p)\neq1,b\geq\varphi(p) \end{cases} \]

2. \(\forall n>1,1\)到\(n\)中所有互质的数的和为\(n\times\frac{\varphi(n)}{2}\)。

3. 很多人都喜欢称之为欧拉反演。对于任意正整数\(n\)，有\(\sum_{d|n}\varphi(d)=n\).