欧拉定理
看欧拉定理之前，要先看一看欧拉函数
欧拉函数
对于正整数$n$，$phi=$小于等于$n$的数中与n互质的数的个数。$phi$就表示欧拉函数
举个栗子，$phi (6)=2$，因为从$0$到$6$中，与$6$互素的只有$1,5$。同样的，$6$的一个完全剩余系是$0,1,2,3,4,5$，$phi (n)$还可以表示n的简化剩余系的元素个数，也是$2$
公式：$phi (n)=n(1-frac{1}{P_1})(1-frac{1}{P_2})ldots (1-frac{1}{P_k})$。例如，$36=2^2*3^2$，$phi (36)=36(1-frac{1}{2})(1-frac{1}{3})=12$
欧拉定理
若$mge 2$，且$(a,m)=1$，$phi(m)$为欧拉函数，则$a^{phi(m)}equiv 1pmod{m}$
证明：
若设$r_1,r_2,ldots ,r_{phi(m)}$是模$m$的一个简化剩余系，由$(a,m)=1$，所以$ar_1,ar_2,ldots ,ar_{phi(m)}$也是模$m$的一个简化剩余系
所以$ar_1*ar_2*ldots *ar_{phi(m)}equiv r_1r_2ldots r_{phi(m)}pmod{m}$，即$mmid (a^{phi(m)}-1)r_1r_2ldots r_{phi(m)}$
又因为$(m,r_1r_2ldots r_{phi(m)})=1$，所以$mmid a^{phi(m)}-1$，故$a^{m}equiv 1pmod{m}$
由上可知，$(a,b)=1$，则$phi(ab)=phi(a)*(b)$
性质
设$m>1$是一个固定的整数，$a$是与$m$互素的整数，存在整数$k$，$1leq kleq m$，使$a^kequiv 1pmod{m}$，则称具有这一性质的最小正整数（仍记为$k$）为$a$模$m$的阶
$a$模$m$的阶$k$具有如下性质：
$(1)$设$(a,m)=1$，$k$是$a$模$m$的阶，$u$，$v$是任意整数，则$a^uequiv a^vpmod{m}$的充要条件是$uequiv vpmod{k}$
特别地，$a*uequiv 1pmod{k}$的充要条件是$kmid u$
$(2)$设$(a,m)=1$，$a$模$m$的阶为$k$，则数列$a,a^2,ldots,a^k,a^{k+1},ldots$是模$m$的周期数列，其最小正周期为$k$，而$k$个数$a,a^2,ldots,a^k$模$m$互不同余
$(3)$设$(a,m)=1$，则$a$模$m$的阶整除欧拉函数$phi(m)$
欧拉函数代码
ll Eular(ll x) { ll ans=1; for(ll i=2;i*i<=x;i++) if(x-floor(x/i)*i==0) { x/=i; ans*=i-1; while(x-floor(x/i)*i==0) { x/=i; ans*=i; } } if(x>1) ans*=x-1; return ans; }
费马小定理
设$p$是素数，且$(a,p)=1$，则$a^{p-1}equiv 1pmod{p}$
$(1)$对于任意的整数$a$和任意的素数$p$，有$a^pequiv apmod{p}$
事实上，若$(a,p) e 1$，则$pmid a$，这时结论显然成立。若$(a,p)=1$，则由欧拉定理，有$a^{phi(p)}equiv 1pmod{p}$，又因为$phi(p)=p-1$，所以$a^{p-1}equiv 1pmod{p}$
$(2)$费马小定理是当欧拉定理当$m$为素数时的特例，也就是说，费马小定理是欧拉定理的特殊情形
$(3)$费马小定理的逆命题不成立
例题
$(1)$设$n,k$是正整数，$n$不被$3$整除，$kge n.$证明，存在正整数$m$，是$m$可被$n$整除，且它的各位数字之和为$k$
分析：
设$n=2^a*5^b*p$，其中$a,b$是非负整数，且$(p,10)=1$，只要证明存在正整数$m$，使$pmid m$，且$m$的各位数字之和等于$k$。实际上，这时只要取$m=m*10^c$，其中$cge max{a,b}$即可
因为$(p,10)=1$，由欧拉定理，存在正整数$dge 2$，使$10^dequiv 1pmod{p}$，于是对于任意非负整数$i,j$，有
$10^{id}equiv 1pmod{p}$，$10^{jd+1}equiv 10pmod{p}$
设$m=sum_{i=1}^u 10^{id}+sum_{j=1}^v 10^{jd+1}$，则$m$的各位数字之和为$u+v$（当$u,v$中某个为零时，则对应的那项求和为零）且$mequiv u+10vpmod{p}$故只需证明，存在$u,v$使
$egin{cases} u+v=k\ pmid u+10v end{cases}Longleftrightarrow egin{cases} u+v=k\ pmid k+9v end{cases}$ $(1)$
因为$(p,3)=1$，则$k,k+9m,k+18,ldots,k+9(p-1)$中必有一个被$p$整除，即存在整数$v_0(0leq v_0leq p-1)$使$pmid (k+9v_0)$。设$u_0=k-v_0$，则$u_0+v_0=k,pmid k+9v_0$，即$u_0,v_0$满足$(1)$，故由前面分析知$m=m*10^c$的各位数字之和为$k$且$m$被$n$整除。
$(2)$求所有的正整数对$(a,n)$，使得$frac{(a+1)^n-a^n}{n}$是整数
分析：
若$a$为任意正整数，则$(a,1)$显然是原问题的解，下面要证明原问题没有其他解
假设$(a,n)(nge 2)$是原问题的一个解，则存在某正整数$k$，使得
$(a+1)^n-a^n=kn$
由于$a$和$a+1$互素，由上面的方程可知，n肯定和$a,a+1$都互素
由欧拉定理可得
$(a+1)^{phi(n)}equiv a^{phi(n)}equiv 1pmod{n}$
令$d=gcd(n,phi(n))$，由$Bezout$不等式，存在整数$alpha$和$eta$使得$d=alpha n+eta phi(n)$
由$(a+1)^{n}equiv a^{n}pmod{n}$，和$(a+1)^{phi(n)}equiv a^{phi(n)}equiv 1pmod{n}$可推出
$(a+1)^dequiv (a+1)^{alpha n+eta phi(n)}equiv a^{alpha n+eta phi(n)}equiv a^dpmod{n}$
显然$d>1$(否则$a+1equiv 1pmod n$推出$n=1$)。同时注意到$phi(n)<n$，所以$d<n$，因此$(a,d)$是原问题的一个解，并且$1<d<n$。重复上述过程，我们就得到了一个无穷递降正整数序列，而这是不可能的，所以上面的假设是错误的，即没有$n>1$的解。
$updateing ldots$