经典网文分享: 初等数论Part 1：欧拉定理

这是一个关于初等数论的入门级别文章
适合中学数学水平的读者
主要内容：唯一分解定理，互质，最大公因数，最小公倍数，同余关系，同余类，完全剩余系，缩剩余系，欧拉函数，欧拉定理，费马小定理，中国剩余定理，逆元。

求正整数 $3^{83}$ 的最后两位数

看到类似这样求一个数的某次方的最后几位数的问题，

没有接触过初等数论的同学可能第一反应是小学的做法：找规律。

$\begin{align} &3^0 = \quad\space \space \color{red}1\\ &3^1 = \space \quad \space \color{red}3\\ &3^2 =\space \quad \space \color{red}9\\ &3^3 =\space \space \space \space 2 \color{red} 7\\ &3^4 =\space \space \space \space 8 \color{red} 1 \\ &3^5 =\space \space 24 \color{red} 3 \\ &3^6 =\space \space 72 \color{red} 9 \\ &3^7 =218\color{red}7 \\ &3^8 = 656\color{red} 1 \\ \end{align}\\$

可以看出来 $3^n$ 的个位是 $1,3,9,7$ 循环，循环周期是 $4$

而十位是 $0,0,0,2, 8, 4, 2, 8, 6, 8, 4, 4, 4, 2, 6, 0, 2, 6, 8, 6$ 循环，循环周期是 $20$

所以 $3^{83}$ 最后两位是 $27$

接触过一点初等数论的同学表示这种方法too young，因为这个问题可以用欧拉定理(Euler's theorm)秒杀。

如果正整数 $n$ 和整数 $a$ 互质，那么就有
$a^{\varphi(n)}\equiv 1 \pmod{n}\\$
其中欧拉函数 $\varphi(n)$ 是「小于 $n$ 的正整数中和 $n$ 互质的数」的个数

因为

$\varphi(100)=100\left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{5}\right)=40\\$

我们又知道 $\gcd(3, 100)=1$ ，所以

$3^{83}=3^{3}\times 3^{80} =3^{3}\times \left(3^{\varphi(100)}\right)^2 \equiv 3^3\times 1 = 27\pmod{100}\\$

利用好欧拉定理我们还可以解决很多类似的问题（部分选自Brilliant）

求 $2014^{2014^{2014}}$ 的最后两位数
求 $1^{2016}+2^{2016}+\cdots + 2016^{2016}$ 除以 $2016$ 的余数
求 $8^{7^{6^{5^{4^{3^{2^{1}}}}}}}$ 的最后三位数
有多少个正整数 $1\le n \le 2015$ 使得 $n^{n^{n}}$ 和 $n^n$ 的个位数相同？
$249$ 的奇数次方末尾总会出现其本身 $\color{red}{249}^3 =15438\color{red}{249}$ ， $\color{red}{249}^5=957186876\color{red}{249}$ 等等。 $1000$ 以内有多少个正整数有这样的性质？

我们首先从初等数论最基本的几个概念说起

1.唯一质数分解定理（Unique factorisation theorm）

任何一个正整数 $n>1$ 都可以唯一地分解为一组质数的乘积

$n=2^{e_1}\times3^{e_2}\times 5^{e_3}\times \cdots=\prod_{k=1}^\infty p_k^{e_k}\\$

其中 $e_1, e_2,\ldots \in \mathbb{N}$ ，我们称这个分解为 $n$ 的标准分解

2.互质（Coprime）、最大公因数（GCD）和最小公倍数（LCM）

对于整数 $a, b$ 我们记 $\gcd(a, b)$ 和 $\operatorname{lcm}(a, b)$ 为 $a, b$ 的最大公因数和最小公倍数，有时候我们会直接把他们简写为 $(a, b)$ 和 $[a, b]$ 。如果 $\gcd(a, b)=1$ ，我们称 $a, b$ 互质，也就是说他们没有任何共同的质因数。

它有几个基本的性质，对于正整数 $a, b, n$

$\gcd(a, b)=\gcd(a\pm b, b)$
$\gcd(na, nb)=n\gcd(a, b)$
$\gcd(a, b)=\frac{a\cdot b}{\operatorname{lcm}(a, b)}$
贝祖定理：总能找到整数 $x, y$ 使得 $\gcd(a, b)=ax+by$

2.同余关系（Congruence relations）

整数 $a$ 和 $b$ 除以 $n$ 的余数相同，则称 $a,b$ 模 $n$ 同余，计作

$a \equiv b \pmod{n}\\$

如果对于整数 $a_1, a_2, b_1, b_2$ 有

$a_1 \equiv b_1 \pmod{n}\\a_2 \equiv b_2 \pmod{n}$

那么可以把他们相加或相减

$a_1 \pm a_2 \equiv b_1 \pm b_2\pmod{n}\\$

也可以把他们相乘

$a_1a_2 \equiv b_1b_2\pmod{n}\\$

通过这两条性质，我们容易知道，如果 $a\equiv b \pmod{n}$ 那么

$\mathrm P(a)\equiv \mathrm P(b) \pmod{n}\\$

对于任意整系数多项式 $\mathrm P(x)$ 都成立，这个结论很重要哦，经常会用

这里需要注意的一点是，如果整数 $a, b, c$ 满足

$ac\equiv bc \pmod{n}\\$

那么只有当 $n, c$ 互质时才可以把两边的 $c$ 直接约掉，得到 $a\equiv b \pmod{n}$ ，更一般的

$a\equiv b \pmod{\frac{n}{\gcd(n, c)}}\\$

3.同余类(Residue class)、完全剩余系(Complete residue system)、缩剩余系(Reduced residue system)

通过一个整数模 $n$ 的余数，我们可以把所有整数分成 $n$ 类，记

$\overline{r}_n=\{m\in \mathbb{Z} \mid mn+r\}\\$

为模 $n$ 余 $r$ 的同余类（也叫剩余类）举个例子

$\overline{4}_{10}=\{\dots,-16,-6,4, 14, 24, \dots\}\\$

是模 $10$ 余 $4$ 的同余类

从 $\overline{0}_n, \overline{1}_n, \overline{2}_n, \dots,\overline{(n-1)}_n$ 中各挑出一个数就组成了一个模 $n$ 的完全剩余系（完系） $R_n$

$R_n = \{r_0, r_1, \dots, r_{n-1}\}\\$

其中 $r_0 \in \overline0_n, r_1 \in \overline1_n, r_2 \in \overline2_n, \dots, r_{n-1} \in \overline{(n-1)}_n$

换言之， $n$ 个模 $n$ 互相不同余的整数组成一个模 $n$ 的完全剩余系。

我们称 $R_n = \{0, 1, \dots, n-1\}$ 为模 $n$ 的最小非负完全剩余系（最小非负完系）。

取一个模 $n$ 的完全剩余系 $R_n$ ，取出里面所有和 $n$ 互质的数，这些数组成一个模 $n$ 的缩剩余系（缩系），记为 $\Phi_n$

$\Phi_n = \{c_1, c_2, \dots, c_{\varphi(n)} \}\\$

其中 $\varphi(n)$ 是序言里提到的欧拉函数，代表「小于 $n$ 的正整数中和 $n$ 互质的数」的个数。

注意，因为 $\gcd(c_i, n)=\gcd(c_i+n, n)=1$ ，每一个模 $n$ 的缩剩余系有相同数量的元素（缩剩余系中的每一个数所属的同余类是确定的，所以总有确定的 $\varphi(n)$ 个同余类）

如果缩剩余系 $\Phi_n = \{c_1, c_2, \dots, c_{\varphi(n)} \}$ 满足 $1\le c_1, c_2, \dots, c_{\varphi(n)}\le n -1$ ，那么称其为模 $n$ 的最小正缩剩余系（最小正缩系）。

4.欧拉函数(Euler's totient function)

对于正整数 $n$ ， $\varphi(n)$ 代表「小于 $n$ 的正整数中和 $n$ 互质的数」的个数，这个函数被称为欧拉函数；欧拉还告诉我们

$\frac{\varphi(n)}{n}=\prod_{p|n}\left( 1-\frac{1}{p}\right)\\$

其中 $p$ 取到 $n$ 的所有质因数

所以我们可以很方便的计算一个正整数欧拉函数的值，比如

$\varphi(1926)=\varphi(2 \times 3^2\times 107)=1926\left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{3}\right)\left( 1-\frac{1}{107}\right)=636 \\$

欧拉函数还有一些非常有用的性质（跳过不影响下一部分的阅读）

如果正整数 $n>2$ 那么 $\varphi(n)$ 是偶数
如果 $n\ |\ N$ ，那么 $\varphi(n)\ | \ \varphi(N)$
对于正整数 $a, n$ 有 $n \ |\ \varphi(a^n - 1)$
对于正整数 $m, n$ 有 $\varphi(mn)=\varphi(m)\varphi(n)\frac{\gcd(m, n)}{\varphi(\gcd(m, n))}$
特别地，如果 $m, n$ 互质，那么 $\varphi(mn)=\varphi(m)\varphi(n)$
对于正整数 $n$ 有 $\sum_{d| n}\varphi(d)=n$
对于正整数 $n$ 有 $\sum_{1\le k \le n\atop \gcd(k, n)=1}\frac{k}{n}=\frac{\varphi(n)}{2}$

接下来我们进入正题：欧拉定理

如果正整数 $n$ 和整数 $a$ 互质，那么就有
$a^{\varphi(n)}\equiv 1 \pmod{n}\\$
其中 $\varphi(n)$ 是欧拉函数

以下是证明

考虑模 $n$ 的最小正缩系

$\Phi_n =\{c_1, c_2, \dots, c_{\varphi(n)}\}\\$

已知 $\gcd(a,n)=1$ 我们在 $\Phi_n$ 的每一个元素前面都乘一个 $a$

$a\Phi_n = \{ac_1,a c_2, \dots, ac_{\varphi(n)}\}\\$

利用反证法可以证明 $a\Phi_n$ 也是一个模 $n$ 的缩系（其元素的同余类的顺序有可能会改变，但是这并没有任何影响），假设

$ac_i \equiv ac_j \pmod{n} \\$

其中 $i\ne j$ ，因为 $a, n$ 互质可以将两边消去 $a$ ，那么就得到

$c_i \equiv c_j \pmod{n} \\$

这是不可能的，因为 $\Phi_n$ 中的元素互相模 $n$ 不同余，矛盾啦！

接下来的思路就比较清晰了，因为 $\Phi_n$ 和 $a\Phi_n$ 都是模 $n$ 的缩系

$\prod_{i=1}^{\varphi(n)} c_i\equiv \prod_{i=1}^{\varphi(n)} ac_i = a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} c_i \pmod{n} \\$

显然 $\gcd\left(n, \prod_{i=1}^{\varphi(n)} c_i \right)=1$ 所以可以两边消去它

$a^{\varphi(n)}\equiv 1 \pmod{n}\\$

然后我们就证毕啦，是不是意外的简单？

另外，如果我们让 $n=p$ 是一个质数，我们就可以从欧拉定理推出费马小定理（Fermat's little theorm）

如果 $p$ 是质数，那么 $p \ | \ n^p -n$ 对于任意整数 $n$ 都成立

当然，费马小定理也可以用归纳法证明，假设 $p \ | \ n^p -n$ ，那么

$(n+1)^p-(n+1)=\sum_{r=1}^{p-1}\binom{p}{r}n^r + n^p - n\\$

当 $1\le r \le p -1$ 时，二项式系数 $\binom{p}{r}=\frac{p!}{(p-r)!r!}$ 的分子中有 $p$ ，分母中每一个乘子都不能整除 $p$ （因为 $p$ 是质数），所以 $p$ 能够整除 $\binom{p}{r}$ ，进而得到 $p \ | \ (n+1)^p - (n+1)$ 。当 $n=0$ 时显然成立，所以定理成立。

接下来我们看看如何证明

$\frac{\varphi(n)}{n}=\prod_{p|n}\left( 1-\frac{1}{p}\right)\\$

首先考虑 $\varphi(p^e)$ ，其中 $p$ 是质数， $e$ 是非负整数

如果要使 $\gcd(p^e, k)\ne 1$ ，只能让 $k$ 等于 $p$ 的倍数

在 $1\le k \le p^e$ 范围内， $p$ 的倍数有 $p, 2p, 3p, \dots p^{e-1}p=p^e$ 总共 $p^{e-1}$ 个，所以

$\varphi(p^e)=p^e - p^{e-1}=p^e \left( 1-\frac{1}{p}\right)\\$

然后我们证明对于 $\gcd(m, n)=1$ 有 $\varphi(mn)=\varphi(m)\varphi(n)$ ，我们首先构造两个集合，第一个集合是模 $mn$ 的最小正缩系 $\Phi_{mn}$ ，第二个集合定义为

$S=\{(m, n)\mid m\in \Phi_m, n\in \Phi_n \}\\$

其中 $\Phi_m, \Phi_n$ 分别是模 $m,n$ 的最小正缩系，显然 $|\Phi_{mn}|=\varphi(mn)$ 和 $|S|=\varphi(m)\varphi(n)$

如果我们证明存在一个双射 $f:\Phi_{mn}\rightarrow S$ ，就证明了 $\varphi(mn)=\varphi(n)\varphi(n)$

我们让

$f(a)=(a \bmod m,\ a \bmod n)\\$

首先我们用反证法证明 $f$ 是单射，假设 $a, b \in \Phi_{mn}$ 满足 $a\ne b$ 且 $f(a)=f(b)$ 那么

$\begin{align}a&\equiv b \pmod{m}\\a&\equiv b \pmod{n}\end{align}\\$

显然因为 $\gcd(m,n)=1$ 我们能得出 $a\equiv b \pmod{mn}$ ，这与我们的假设矛盾（因为 $\Phi_{mn}$ 是模 $mn$ 的缩系， $a, b$ 是 $\Phi_{mn}$ 的两个不同的元素，所以他们模 $mn$ 不同余）。接下来，中国剩余定理告诉我们

如果整数 $r_1, r_2$ 和正整数 $\gcd(n_1,n_2)=1$ ，同余方程组
$\begin{align}x&\equiv r_1 \pmod{n_1}\\ x &\equiv r_2 \pmod{n_2}\end{align}\\$
在 $0 \le x < n_1n_2$ 范围内有且只有一个解

通过中国剩余定理我们能够证明 $f$ 是满射，所以 $f$ 是双射。

所以对于 $\gcd(m,n)=1$ 就有 $\varphi(mn)=\varphi(n)\varphi(n)$ ，假设 $n$ 的标准分解为

$n=2^{e_1}\times3^{e_2}\times 5^{e_3}\times \cdots=\prod_{k=1}^\infty p_k^{e_k}\\$

其中 $e_1, e_2,\ldots \in \mathbb{N}$ ，那么

$\begin{align}\varphi(n)&=\varphi\left(\prod_{k=1}^\infty p_k^{e_k}\right)\\&=\prod_{k=1}^\infty \varphi\left(p_k^{e_k}\right)\\&=\prod_{k=1}^\infty p^{e_k} \left( 1-\frac{1}{p_k}\right)\\&=\left(\prod_{k=1}^\infty p^{e_k}\right)\prod_{k=1}^\infty\left( 1-\frac{1}{p_k}\right)\\&=n\times\prod_{k=1}^\infty\left( 1-\frac{1}{p_k}\right)\end{align}\\$

证毕

序言中题目的解答

求 $2014^{2014^{2014}}$ 的最后两位数
正确答案是 $36$

因为 $100$ 和 $2014$ 不互质，我们把它拆成 $100=4\times 25$

注意到 $\varphi(25)=25\left( 1-\frac{1}{5} \right)=20$

$2014^{2014^{2014}} \equiv 2014^{2014^{2014} \bmod 20} \pmod{25}\\$

再拆一次 $20=4\times 5$

$2014^{2014}\equiv 2014^2\times \left( 2014^{\varphi(5)}\right)^{503}\equiv 2014^2\equiv4^2=16 \pmod{5}\\$

这里取 $16$ 因为要保证它能被 $4$ 整除，接着

$2014^{2014^{2014}}\equiv2014^{16}\equiv 14^{16}\equiv36 \pmod{100}\\$

因为 $36$ 能被 $4$ 整除，所以最后两位是 $36$

求 $1^{2016}+2^{2016}+\cdots + 2016^{2016}$ 除以 $2016$ 的余数
正确答案是 $48$

因为 $2016=2^5\times 3^2 \times 7$ ，我们只需分别找出这个数模 $32, 9, 7$ 的余数

因为 $\varphi(32)\ | \ 2016$

$\begin{align}1^{2016}+2^{2016}+\cdots+2016^{2016}&\equiv 63\times \left(1^{2016}+2^{2016}+3^{2016}+\cdots+32^{2016} \right) \pmod{32}\\ &=63\times (1^{2016}+3^{2016}+5^{2016}+\cdots+31^{2016})\\&\equiv 63\times 16\\&\equiv 16\end{align}$

因为 $\varphi(7)\ | \ 2016$

$\begin{align}1^{2016}+2^{2016}+\cdots+2016^{2016}&\equiv 288\times \left(1^{2016}+2^{2016}+\cdots+7^{2016} \right) \pmod{7}\\ &=288\times (1^{2016}+2^{2016}+\cdots+6^{2016})\\&\equiv 288\times 6\\&\equiv 6\end{align}$

因为 $\varphi(9) \ | \ 2016$

$\begin{align}1^{2016}+2^{2016}+\cdots+2016^{2016}&\equiv 224\times \left(1^{2016}+2^{2016}+\cdots+9^{2016} \right) \pmod{9}\\ &=224\times (1^{2016}+2^{2016}+4^{2016}+5^{2016}+7^{2016}+8^{2016})\\&\equiv 224\times 6\\&\equiv 3\end{align}$