在数论中，对正整数 n，欧拉函数 $\varphi (n)$ 是小于或等于 n 的正整数中与 n 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 φ 函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。（来自维基百科）
温馨提示：
本文中有大量 KaTeX 公式，请确保浏览器支持，否则卡到超乎你想象。
Windows 可以在控制面板-程序-卸载程序-卸载\更新 Windows 组件中卸载IE浏览器。
本文中 (a,b) 或者 gcd(a,b) 表示a、b的最大公因数。
本文隶属⌈ 数论学习系列 ⌋。
欧拉函数
定义
欧拉函数 $\varphi(n)$ 是小于或等于 n 的正整数中与 n 互质的数的数目。例如：$\varphi(10)$=4，因为在1到10中1、3、7、9 这4个数字与 10 互质。
（注：$\varphi (n)$的另一种写法是$\phi(n)$，但是我更喜欢前者……）
几个性质
这两个性质下面证明的时候要用。
当x为质数p的k次幂时
如果$\varphi(x)$中的x是质数 p 的 k 次幂，那么可以用这个公式求：
$$\varphi (x)=\varphi (p^k)=p^k-p^{k-1}=(p-1)p^{k-1}=p^k\cdot (1-\frac 1 p)$$
很好理解，除了 p 的倍数外，其他数都与 x 互质。（为什么要化成这样？因为后面我们证明 $\varphi (x)$ 的公式要用~）
欧拉函数是积性函数
欧拉函数是积性函数，就是说如果 x 和 y 互质，则
$$\varphi(xy)=\varphi(x) \varphi(y)=(x-1)(y-1)$$
（剩下的两个性质就是下面要讲的费马小定理和欧拉定理了）
计算方法（公式）
$\varphi(x)$的计算公式是：
$$\varphi(x)=x(1-\frac 1 {P_1})(1-\frac 1 {P_2})\cdots(1-\frac 1 {P_x})$$
写得高端点：
$$\varphi (x)=x\prod_{i=1}^n (1-\frac 1 {P_i})$$
其中$P_i$表示 $x$ 的第 $i$ 个质因子，上式条件为 $x \geqslant 2$ 且 $x \in Z$ 。
特殊地，$\varphi(1)=1$。因为小于等于 1 的正整数中唯一和1互质的数就是 1 本身。
举例
比如说计算 $\varphi(10)$：10 的质因子有 2 和 5。那么：
$$\varphi(10)=10(1-\frac 1 2)(1-\frac 1 5)=4$$
与前面验证的答案一致~
公式证明
我们先把 $x$ 标准分解：
$$x=P_1^{k_1} \cdot P_2^{k_2} \cdots P_n^{k_n}$$
其中 $P_i$ 表示 $x$ 的第 $i$ 个质因子，$k_i$ 则表示x中含有质因子 $P_i$ 的数量。接下来根据“欧拉函数是积性函数”这一性质可以得出：
$$\varphi(x)=\varphi(P_1^{k_1})\cdot \varphi(P_2^{k_2})\cdots \varphi(P_n^{k_n})$$
又根据前面推出的 $\varphi (p^k)=p^k\cdot (1-\frac 1 p)$，得到：
$$\varphi(x) = x(1-\frac 1 {P_1})(1-\frac 1 {P_2})\cdots(1-\frac 1 {P_x}) = x\prod_{i=1}^n (1-\frac 1 {P_i})$$
就得到了刚刚的等式！！！
费马小定理
费马小定理（Fermat's Little Theorem）是数论中的一个重要定理，在1636年由费马提出。基本内容是：如果 p 是质数并且 $(a,p)=1$，则有：
$$a^{p-1}\equiv 1 \pmod p$$
举个例子，对于质数 p=3，a=8，那么：
$$8^{3-1}\equiv 64\equiv 1 \pmod 3$$
完全剩余系
为了方便证明，先要普及下完全剩余系的概念：
完全剩余系（简称完系），即是通过对一系列正整数模 m 后产生的从 0 至（m-1）的完全数系。通常地，完全剩余系在研究数论时很有用。
举个例子：{0, 1, 2, 3} 就是模 4 的完系。
知道了完全剩余系，我们就可以方便地开始证明了……
证明
证明其实并不难。
假设 $\lbrace 1,2,\dots,p-1,p \rbrace$ 是模 $p$ 的完全剩余系，那么显然，$\displaystyle \lbrace a-1,a-2,\dots,a-p \rbrace $ 也是模 $p$ 的完全剩余系。得到：
$$(a-1)(a-2)\cdots(a-(p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod p$$
等价于：
$$a^{p-1}\cdot (p-1)! \equiv (p-1)! \pmod p$$
又 $((p-1)!,p)=1$，所以
$$a^{p-1} \equiv 1 \pmod p$$
欧拉定理
欧拉定理（Euler's Theorem）可以看作费马小定理的一般情况，即如果 $(a,n)=1$ ，则 $a,n$ 满足：
$$ a^{\varphi (n)}\equiv 1 \pmod n $$
举例：$n=6,a=5$：$\varphi(6)=2$ ；
$$ 5^2 \equiv 25 \equiv 1 \pmod 6 $$
显然当 $n$ 是质数的时候 $\varphi(n)=n-1$ ，就成了费马小定理了……
减缩剩余系
在证明之前又要普及一下减缩剩余系的概念了……
简缩剩余系（也叫简化剩余系，简称减系或者缩系）：在每个剩余类选取至 1 个与 m 互素代表元构成简缩剩余系。举个例子：
10 的完系是：{0,1,2,3,4,5,6,7,8,9}；
则 {1,2,5,6} 是 10 的一个减系。也就是说从完系里选几个数。要注意不一定是从这个固定的完系里选，例如 {10,14,15} 也是 10 的一个减系。
证明
这个定理证明和费马小定理类似：
假设 $\lbrace x_1,x_2,\dots,x_{\varphi (n)} \rbrace$ 是模 $p$ 的减缩剩余系，那么：
$$ x_i \not ≡ x_j \pmod n $$
又 $(a,n)=1$，所以
$$ ax_i \not ≡ ax_j \pmod n $$
所以 $\displaystyle \lbrace ax_1,ax_2,\dots,ax_{\varphi (n)} \rbrace$ 也是模 $p$ 的减缩剩余系。所以：
$$ (ax_1)(ax_2)\cdots(ax_{\varphi (n)}) \equiv x_1 \cdot x_2 \cdots x_{\varphi (n)} \pmod n $$
上式等价于：
$$ a^{\varphi(n)}(x_1 \cdot x_2 \cdots x_{\varphi (n)}) \equiv x_1 \cdot x_2 \cdots x_{\varphi (n)} \pmod n $$
即：
$$ a^{\varphi(n)} \equiv 1 \pmod n $$
参考
欧拉函数 - 维基百科，自由的百科全书
费马小定理 - 维基百科，自由的百科全书
完全剩余系 - 维基百科，自由的百科全书
欧拉定理 (数论) - 维基百科，自由的百科全书 "欧拉定理 (数论) - 维基百科，自由的百科全书")
费马小定理_百度百科
欧拉函数 - handsomecui - 博客园