本节对应原书 PDF 第 278–279 页（印刷 p263–p264）。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

对任意正整数 n，把 \{0,1,\cdots,n-1\} 中与 n 互素的个数记作 \phi(n)，称作欧拉(Euler)函数。如 \phi(1) = \phi(2) = 1，\phi(3) = \phi(4) = 2。显然，当 n 为素数时 \phi(n) = n-1；当 n 为合数时 \phi(n)<n-1。

解读：\phi(n) 数的是 0 到 n-1 中与 n 互素的个数，也就是模 n 的可逆元个数。正因如此，它才会在同余式的「约分」中反复出现。

定理 11.12（欧拉定理） 设 a 与 n 互素，则

a^{\phi(n)} \equiv 1(\bmod\ n) \tag{11.6}

证明 设 r_1,r_2,\cdots,r_{\phi(n)} 是 \{0,1,\cdots,n-1\} 中与 n 互素的 \phi(n) 个数。由于 a 与 n 互素，对每一个 1 \leqslant i \leqslant \phi(n)，ar_i 也与 n 互素，故存在 1 \leqslant \tau(i) \leqslant \phi(n) 使得 ar_i \equiv r_{\tau(i)}(\bmod\ n)。\tau 是 \{1,2,\cdots,\phi(n)\} 上的一个映射。要证 \tau 是一个单射，即当 i \neq j 时，\tau(i) \neq \tau(j)。

由定理 11.10，a 的模 n 逆 a^{-1} 存在。显然，a^{-1} 也与 n 互素。当 i \neq j 时，假设 \tau(i) = \tau(j)，则有 ar_i \equiv ar_j(\bmod\ n)。由性质 11.3.5，两边同乘 a^{-1}，得 r_i \equiv r_j(\bmod\ n)，矛盾。得证 \tau 是 \{1,2,\cdots,\phi(n)\} 上的单射，当然它也是 \{1,2,\cdots,\phi(n)\} 上的双射。从而有

a^{\phi(n)}\prod_{i=1}^{\phi(n)} r_i \equiv \prod_{i=1}^{\phi(n)} ar_i \equiv \prod_{i=1}^{\phi(n)} r_{\tau(i)} \equiv \prod_{i=1}^{\phi(n)} r_i(\bmod\ n)

而 \prod_{i=1}^{\phi(n)} r_i 与 n 互素，故 a^{\phi(n)} \equiv 1(\bmod\ n)。

解读：证明的关键是「用 a 去乘全体可逆元，得到的仍是全体可逆元的一个排列」。既然是同一个集合，全部乘起来自然相等，两边约掉公因子 \prod r_i 就得到 a^{\phi(n)} \equiv 1。a 与 n 互素这个条件同时保证了两件事：\tau 是双射，以及 \prod r_i 可约。

当 p 为素数时，\phi(p) = p-1。于是，得到下述定理。

定理 11.13（费马小定理^①^） 设 p 是素数，a 与 p 互素，则

a^{p-1} \equiv 1(\bmod\ p) \tag{11.7}

定理的另一种形式是，设 p 是素数，则对任意的整数 a，

a^p \equiv a(\bmod\ p) \tag{11.8}

当 a 与 p 互素时，由性质 11.3.5，式(11.7)与式(11.8)等价。当 a 与 p 不互素时，必有 p \mid a，从而 a \equiv 0(\bmod\ p)，式(11.8)自然成立。

解读：式(11.8)是比式(11.7)更强的形式，因为它对任意整数 a 都成立，不需要互素前提。两种形式互推：a 与 p 互素时式(11.8)两边同乘 a^{-1} 即得式(11.7)；反之式(11.7)两边同乘 a 即得式(11.8)。a 与 p 不互素时 p 是素数，只能是 p \mid a，此时式(11.8)两端同为 0，无需另证。

费马小定理提供了一种不用因子分解就能肯定一个数是合数的新途径。例如考虑 9（假设不知道它是合数），取 a = 2，计算

2^{9-1} \equiv 4(\bmod\ 9)

由费马小定理，可以断定 9 是合数。但是，这里没有提供对 9 如何进行因子分解的任何信息。在第 13 章中将介绍欧拉定理和费马小定理在 RSA 公钥密码及素数测试中的应用。

解读：这是「反着用」定理：定理说素数必满足 a^{p-1} \equiv 1，于是只要算出结果不是 1，就能断定该数不是素数。这正是费马素性测试的依据，但它只给「是合数」的结论，不给因子。

① 为了区别于著名的费马大定理，故将此定理冠名为费马小定理。费马大定理：对所有的正整数 a,b,c 和 n，当 n>2 时，a^n+b^n \neq c^n。费马(Pierre de Fermat)是 17 世纪著名的数学家，他提出了许多未加证明的定理，其中最著名的当数费马大定理。费马大定理直到 1995 年才被英国数学家 Andrew Wiles 证明。