欧拉函数
定义
对于正整数\(n\)，欧拉函数是小于等于\(n\)的数中与\(n\)互质的数的数目，写作\(\varphi (n)\)。特别的，\(\varphi (1)=1\)。
性质
若\(n\)、\(m\)互质，则\(\varphi (nm)=\varphi (n)\varphi (m)\)；
若\(n\)为质数，则\(\varphi (n)=n-1\)。
\(\varphi (p^{a})=p^{a}-p^{a-1}\)（\(p\)为质数）。
证明：
\([1,p^{a}]\)内总共有\(p^{a}\)个数，其中，有\(p\)这个因子的数有\(p^{a-1}\)个。
\(\varphi (n)=n \prod_{i=1}^{k} \frac{p_i -1}{p_i}\)
证明：
由算术基本定理，设：
\[n=\prod_{i=1}^{k} p_i^{a_i}\]
其中\(p_i\)为质数，且\(p_i|n\)；
又：\(\varphi (p_i^{a_i})=p_i^{a_i}-p_i^{a_i-1}\)（性质 3）；
把\(p_i^{a_i-1}\)提出来，得\(\varphi (p_i^{a_i})=(p_i -1)p_i^{a_i-1}\)。
当\(i\not =j\)时，由于\(p_i^{a_i},p_j^{a_j}\)不存在共同的因子，故它们俩互质；
于是，求\(\varphi (n)\)可以直接把\(k\)个\(\varphi (p_i^{a_i})\)相乘（性质 1）；
可以初步得出
\[\varphi (n)=\prod_{i=1}^{k} (p_i -1)p_i^{a_i-1}\]
分子分母同时乘\(p_i\)，得
\[\varphi (n)=\prod_{i=1}^{k} \frac{(p_i -1)p_i^{a_i}}{p_i}\]
又因为
\[n=\prod_{i=1}^{k} p_i^{a_i}\]
得
\[\varphi (n)=n \prod_{i=1}^{k} \frac{p_i -1}{p_i}\]
如果\(i\bmod pri_j\not =0\)，那么\(\varphi (i\cdot pri_j)=\varphi (i)\cdot (pri_j-1)\)（积性函数的性质）；
如果\(i\bmod pri_j=0\)，那么\(\varphi (i\cdot pri_j)=\varphi (i)\cdot pri_j\)。
证明：
引理：若\(\gcd(a,b)=1\)，则\(\gcd(a+b,b)=1\)。
简单证明如下：
假设\(\gcd(a+b,b)=d\not =1,a+b=xd,b=yd\)；
得\(a+yd=xd\)；
即\(a=(x-y)d\)；
得\(\gcd(a,b)=d\not =1\), 与\(\gcd(a,b)=1\)矛盾，故假设不成立。
在\([1,i]\)有\(\varphi (i)\)个数与\(i\)互质，而根据以上定理，在\([i+1,2i]\)也有\(\varphi (i)\)个数与\(i\)互质，在\([2i+1,3i]\)也有\(\varphi (i)\)个数与\(i\)互质……
于是可得，在\([1,i\cdot pri_j]\)有\(\varphi (i)\cdot pri_j\)个数与\(i\)互质。
而又因为\(pri_j\)是\(i\)的因子，故与\(i\)互质的数必定与\(pri_j\)互质，也与\(i\cdot pri_j\)互质。
欧拉定理是一个关于同余的性质：若正整数\(a,n\)互质，则\(a^{\varphi (n)}\equiv 1\quad \pmod n\)。
证明：
令\(Z_n=\{x_1,x_2,\ldots x_{\varphi (n)}\}\)即\(n\)的质因子集。
设\(S=\{y_i|y_i=ax_i\bmod n\},\quad i\in [1,\varphi (n)]\)；
当\(i\not =j\)时，\(x_i\not =x_j\)，故\(ax_i\bmod n\not =ax_j\bmod n\)；
又因为\(\gcd(a,n)=1\)，\(\gcd(x_i,n)=1\)，故\(\gcd(ax_i,n)=1\)，故\(ax_i\bmod n\in Z_n\)；
得出\(Z_n=S\)。
故
\[a^{\varphi (n)}\prod_{i=1}^{\varphi (n)} x_i\equiv \prod_{i=1}^{\varphi (n)} ax_i\equiv \prod_{i=1}^{\varphi (n)} x_i\quad \pmod n\]
观察同余式两端，由消去律可得\(a^{\varphi (n)}\equiv 1\pmod n\)。故得证。
费马小定理：若\(p\)为质数，且\(a\)与\(p\)互质，则\(a^{p-1}\equiv 1\quad \pmod p\)。
欧拉定理在\(p\)为质数时的特殊情况。
小于\(n\)的与\(n\)互质的数的和为\(\frac{n\cdot\varphi(n)}{2}\)。
引理：若\(\gcd(n,n-i)=1\)，则\(\gcd(n,i)=1\)。
假设\(\gcd(n,i)=d\not =1,n=xd,i=yd\)； 得\(n-i=(x-y)d\)；
得\(\gcd(n,n-i)=d\not =1\)，与\(\gcd(n,n-i)=1\)矛盾，故假设不成立。
于是可得与\(n\)互质的数是成对出现的，且每一对的和为\(n\)。
\(n=\sum_{d|n}\varphi (d)\)
证明在 莫比乌斯函数及莫比乌斯反演。
求解算法
扩展
\[a^b\equiv \begin{align} \begin{cases} a^{b\bmod \varphi(p)} & \gcd(a,p)=1\\ a^b & \gcd(a,p)\neq1,b<\varphi(p)\\ a^{b\bmod \varphi(p)+\varphi(p)} & \gcd(a,p)\neq1,b\geq\varphi(p) \end{cases} \end{align}\qquad\pmod p\]