欧拉定理：
若\(gcd(a,m)=1\)，则\(a^{\varphi(m)}\equiv1\pmod{m}\)
证明：令\(r_1,r_2,···,r_{\varphi(m)}\)为模m下的一个简化剩余系，则\(ar_1,ar_2,···,ar_{\varphi(m)}\)也为模m下的一个简化剩余系,令\(f=r_1*r_2*···*r_{\varphi(m)}\)，则有：\(f\equiv ar_1*ar_2*···*ar_{\varphi(m)}\pmod{m}\)
即\(f\equiv f*a^{\varphi(m)}\pmod{m}\)
因为\(gcd(r_1*r_2*···*r_{\varphi(m)},m)=1\)，所以上式两边同时约去\(f\)，就有\(a^{\varphi(m)}\equiv1\pmod{m}\)
证毕。
特别的，当m为质数时\(\varphi(m)=m-1\)，为费马小定理
关于简化剩余系的说明：
百度定义:在\(m\)的完全剩余系中与m互素的数构成的子集，如果模m的一个剩余类里所有数都与\(m\)互素，就把它叫做与模\(m\)互素的剩余类。在与模\(m\)互素的全体剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模\(m\)的一个简化剩余系。
感性理解：与m互质的数且满足集合内任意\(r_i\not\equiv r_j\pmod{m}\)的最大集合，eg:\(G=\{1,2,3,4\}\)为m=5的一个简化剩余系,\(G=\{2,3,6,9\}\)也为m=5的一个简化剩余系。
性质：当集合\(A=\{a_1,a_2,···,a_n\}\)为关于\(m\)的一个简化剩余系，若\(gcd(k,m)=1\)，则集合\(B=\{ka_1,ka_2,···,ka_n\}\)也为关于\(m\)的一个简化剩余系。
证明：因为\(gcd(k,m)=1,gcd(a_i,m)=1\)，所以\(gcd(ka_i,m)=1\) (集合中的每个数都与m互质)又因为\(m\not|k(a_j-a_i)\)，所以集合中的每个数都不同余，共有n个数，与集合\(A\)一样，所以集合\(B\)为关于m的一个简化剩余系。
证毕
扩展欧拉定理：
\(a^b=\begin{cases}a^{b\mod\varphi(m)}&b\geqslant\varphi(m),gcd(a,m)=1\\a^b&b<\varphi(m)\\a^{b\mod\varphi(m)+\varphi(m)}&b\geqslant\varphi(m),gcd(a,m)>1\end{cases}\)
证明：
我们只考虑当\(b\geqslant\varphi(m)\)的情况
1、当\(gcd(a,m)=1\)时
有\(a^{\varphi(m)}\equiv1\pmod m\)
令\(b=k\varphi(m)+c\)，则\(c=b\bmod\varphi(m)\)
即\(a^b\equiv a^c*a^{k\varphi(m)}\equiv a^c*a^{\varphi(m)^k}\equiv a^c*1^k\equiv a^c\equiv a^{b\bmod\varphi(m)}\pmod m\)
1、当\(gcd(a,m)>1\)时
设\(gcd(a,m)=d,m=m_1d,a=a_1d\)，则\(gcd(a_1,m)=1\)
有\(a_1^{\varphi(m)}\equiv1\pmod m\)
有\(d^{\varphi(m)}*a_1^{\varphi(m)}\equiv d^{\varphi(m)}\pmod m\)
即\(a^{\varphi(m)}\equiv d^{\varphi(m)}\pmod m\)
下证：\(d^{\varphi(m)}\equiv d^{k\varphi(m)}\pmod m\)，\(k\)是整数
因为\(gcd()\)
标签：剩余,gcd,pmod,定理,varphi,ar,笔记,欧拉,equiv From： https://www.cnblogs.com/pengchujie/p/17658939.html