抽象代数的研究对象是代数结构，而整数集 $\mathbb Z$ 是最经典、最基础的代数结构（环）。
许多抽象概念（如理想、生成元）的直觉都源于整数。
本节将回顾有理整数环 $\mathbb Z$ 的基本性质，为后续的群论与环论打下基础。

# 最大公因数与最小公倍数

在整数论中，最大公约数与最小公倍数是两个重要的概念
取整数 $a,b$ （不全为 0），若整数 $d$ 满足

$d \mid a$
$d \mid b$
则称 $d$ 为 $a,b$ 的一个公约数

在所有公约数中，最大的那个称为 $a,b$ 的 最大公约数 (Greatest Common Divisor, GCD)「最大公約数」，记作 $\gcd(a,b)$

同样地，取整数 $m,n$ ，若整数 $l$ 满足

$m \mid l$
$n \mid l$
则称 $l$ 为 $m,n$ 的一个公倍数

在所有正的公倍数中，最小的那个称为 $m,n$ 的 最小公倍数 (Least Common Multiple, LCM)「最小公倍数」，记作 $\mathrm{lcm}(m,n)$

它们之间满足关系：

$|ab| = \gcd(a,b) \cdot \mathrm{lcm}(a,b)$

# Euclidean 算法

Euclidean 算法（辗转相除法）是一种用于计算两个整数的最大公约数的有效算法，记为 Euclidean 算法 (Euclidean Algorithm)「ユークリッドの互除法」。
其原理基于以下性质：

命题
设 $a,b$ 为非负整数，且 $b \neq 0$ ，则

$\gcd(a,b) = \gcd(b,a \bmod b)$

证明

设 $d = \gcd(a,b)$ ，则 $d \mid a$ 且 $d \mid b$
由于 $a \bmod b = a - \lfloor a/b \rfloor b$ ，即 $a \bmod b$ 是 $a$ 与 $b$ 的线性组合
所以 $d \mid (a - \lfloor a/b \rfloor b)$ ，即 $d \mid (a \bmod b)$
因此， $d$ 是 $b$ 和 $a \bmod b$ 的公约数，所以 $d \leq \gcd(b, a \bmod b)$

反之，设 $d' = \gcd(b,a \bmod b)$ ，则 $d' \mid b$ 且 $d' \mid (a \bmod b)$
由于 $a = \lfloor a/b \rfloor b + (a \bmod b)$
所以 $d' \mid (\lfloor a/b \rfloor b + (a \bmod b))$ ，即 $d' \mid a$
因此， $d'$ 是 $a$ 和 $b$ 的公约数，所以 $d' \leq \gcd(a, b)$

综上 $d = d'$ ，即 $\gcd(a,b) = \gcd(b,a \bmod b)$

Euclidean 算法的步骤如下

给定两个非负整数 $a$ 和 $b$ ，其中 $a \geq b$
计算 $a$ 除以 $b$ 的余数 $r$
如果 $r = 0$ ，则 $\gcd(a,b) = b$ ，算法结束
否则，令 $a = b$ ， $b = r$ ，重复步骤 2 和 3

通过不断地用较小的数去除较大的数，并取余数，最终会得到最大公约数

示例
使用 Euclidean 算法计算 $\gcd(484,186)$

解

$\begin{aligned} 484 &= 2 \times 186 + 112 \\ 186 &= 1 \times 112 + 74 \\ 112 &= 1 \times 74 + 38 \\ 74 &= 1 \times 38 + 36 \\ 38 &= 1 \times 36 + 2 \\ 36 &= 18 \times 2 + 0 \end{aligned}$

余数为 0 时的除数即为最大公约数，所以 $\gcd(484,186) = 2$

# 扩展 Euclidean 算法

我们不仅关心最大公约数是多少，还关心它如何通过原数字线性组合得到。这引出了数论中极为重要的 Bézout 定理 (Bézout's Identity)「ベズーの等式」。

定理 Bézout 定理
对于不全为 0 的整数 $a, b$ ，存在整数 $x, y$ 使得

$ax + by = \gcd(a, b)$

扩展 Euclidean 算法可以找到满足上述等式的整数 $x,y$ 。
尤其在求解线性同余方程时非常有用，特别是对于互质问题 $\gcd(a,b) = 1 \iff ax + by = 1$ 。

通常利用矩阵行变换代为计算，步骤如下：

给定两个非负整数 $a$ 和 $b$ ，其中 $a \geq b$
设定初始矩阵

$\begin{pmatrix} 1 & 0 & a \\ 0 & 1 & b \\ \end{pmatrix}$

通过反复行基本变换，每次用上一行减去下一行乘以商 $q$ ，使得第三列的数值模拟 Euclidean 算法的取余过程
直到某一行第三列为 $\gcd(a,b)$ ，而另一行第三列为 $0$
此时非零行对应的第一、二列即为所求的 $x, y$

示例
使用扩展 Euclidean 算法计算 $\gcd(484,186)$ 并找到整数 $x,y$ 使得 $484x + 186y = \gcd(484,186)$

解

初始矩阵

$\begin{pmatrix} 1 & 0 & 484 \\ 0 & 1 & 186 \\ \end{pmatrix}$

执行行变换（ $R_1 \leftarrow R_1 - q R_2$ 等）：

$484 \div 186 = 2 \dots 112$ ：

$\begin{pmatrix} 1 - 2(0) & 0 - 2(1) & 484 - 2(186) \\ 0 & 1 & 186 \end{pmatrix} = \begin{pmatrix} 1 & -2 & 112 \\ 0 & 1 & 186 \end{pmatrix}$

$186 \div 112 = 1 \dots 74$ ：

$\begin{pmatrix} 1 & -2 & 112 \\ 0 - 1(1) & 1 - 1(-2) & 186 - 1(112) \end{pmatrix} = \begin{pmatrix} 1 & -2 & 112 \\ -1 & 3 & 74 \end{pmatrix}$

$112 \div 74 = 1 \dots 38$ ：

$\begin{pmatrix} 1 - 1(-1) & -2 - 1(3) & 38 \\ -1 & 3 & 74 \end{pmatrix} = \begin{pmatrix} 2 & -5 & 38 \\ -1 & 3 & 74 \end{pmatrix}$

$74 \div 38 = 1 \dots 36$ ：

$\begin{pmatrix} 2 & -5 & 38 \\ -1 - 1(2) & 3 - 1(-5) & 36 \end{pmatrix} = \begin{pmatrix} 2 & -5 & 38 \\ -3 & 8 & 36 \end{pmatrix}$

$38 \div 36 = 1 \dots 2$ ：

$\begin{pmatrix} 2 - 1(-3) & -5 - 1(8) & 2 \\ -3 & 8 & 36 \end{pmatrix} = \begin{pmatrix} 5 & -13 & 2 \\ -3 & 8 & 36 \end{pmatrix}$

此时第一行第三列出现了 $2 = \gcd(484, 186)$ 。
（若继续做一步，第二行将变为 $\begin{pmatrix}-93 & 242 & 0\end{pmatrix}$ ，对应 $-93 \times 484 + 242 \times 186 = 0$ ）

所以 $\gcd(484,186) = 2$ ，且满足方程的解为 $x=5, y=-13$ 。
验证： $484 \cdot 5 + 186 \cdot (-13) = 2420 - 2418 = 2$ 。

# 同余方程

同余关系是一种在整数上的等价关系，为整数论的核心分析要素。

定义
取整数 $m \geq 1$ 。
若整数 $a,b$ 满足： $a-b$ 能被 $m$ 整除（即 $m \mid (a-b)$ ）
则称 $a$ 与 $b$ 关于模 $m$ 同余 (Congruent modulo $m$ )「 $m$ を法として合同」，记作

$a \equiv b \pmod{m}$

同余关系具有以下性质：
若 $a \equiv b \pmod{m},\ a' \equiv b' \pmod{m}$ ，则有

$a + a' \equiv b + b' \pmod{m} \quad$
$a a' \equiv b b' \pmod{m} \quad$

利用同余性质，可以实现快速判断一些数字是不是具有因数关系：

模 9 同余： $10 \equiv 1 \pmod 9 \implies 10^k \equiv 1 \pmod 9$ 。一个数模 9 同余于其各位数字之和。
模 11 同余： $10 \equiv -1 \pmod{11} \implies 10^k \equiv (-1)^k \pmod{11}$ 。一个数模 11 同余于其奇数位数字和与偶数位数字和的差。

同余方程指的是形如

$f(x) \equiv 0 \pmod{m}$

的方程，其中 $f(x)$ 为整数系数多项式。
若 $x_0$ 是方程的解，则 $x_0 + km$ 也是解。

其中，针对一次形式的 线性同余方程

$ax \equiv b \pmod{m}$

其解的存在性与结构由以下命题给出：

命题
线性同余方程 $ax \equiv b \pmod{m}$ 有解的充分必要条件是 $\gcd(a,m) \mid b$ 。
特别地，若 $\gcd(a,m) = 1$ ，则该方程在模 $m$ 意义下有唯一解。

证明

设 $d = \gcd(a,m)$ ，则存在整数 $a', m'$ 使得 $a = da', m = dm'$ ，且 $\gcd(a', m') = 1$ 。
方程 $ax \equiv b \pmod{m}$ 等价于 $da'x \equiv b \pmod{dm'}$ ，即 $da'x - b = dm'k$ ，化简得到 $a'x - m'k = b/d$ 。
由于 $\gcd(a', m') = 1$ ，根据 Bézout 定理，存在整数 $x_0, k_0$ 使得 $a'x_0 - m'k_0 = 1$ 。
将等式两边乘以 $b/d$ ，得到 $a'(x_0 \cdot b/d) - m'(k_0 \cdot b/d) = b/d$ ，即 $a'x_1 - m'k_1 = b/d$ ，其中 $x_1 = x_0 \cdot b/d, k_1 = k_0 \cdot b/d$ 。
因此， $x = x_1$ 是方程 $ax \equiv b \pmod{m}$ 的一个解。
反之，若 $x = x_1$ 是方程的一个解，则 $a x_1 \equiv b \pmod{m}$ ，即 $a x_1 - b = m k$ ，化简得到 $a x_1 - m k = b$ 。
由于 $a = da', m = dm'$ ，所以 $d a' x_1 - d m' k = b$ ，即 $d (a' x_1 - m' k) = b$ ，因此 $d \mid b$ 。
$\square$

解线性同余方程实际上是在利用扩展 Euclidean 算法寻找 $a$ 在模 $m$ 下的逆元。

示例
解线性同余方程 $3x \equiv 4 \pmod{7} \quad$

解

由于 $\gcd(3,7) = 1$ ，且 $1 \mid 4$ ，所以方程有唯一解。
目标是寻找 $3^{-1} \pmod 7$ 。
利用扩展 Euclidean 算法，寻找 $3x + 7y = 1$ 的解：

$7 = 2 \times 3 + 1 \implies 1 = 7 - 2 \times 3$

所以 $3 \cdot (-2) \equiv 1 \pmod{7}$
即 $3 \cdot 5 \equiv 1 \pmod{7}$ （因为 $-2 \equiv 5$ ）

方程两边同时乘以 $3^{-1} \equiv 5 \pmod{7} \quad$

$\begin{aligned} 5 \cdot 3 x &\equiv 5 \cdot 4 \pmod 7 \\ 1 \cdot x &\equiv 20 \pmod 7 \\ x &\equiv 6 \pmod 7 \end{aligned}$

$\square$

另外一种常见的同余方程是二次同余方程

$x^2 + px + q \equiv 0 \pmod{m}$

面对这一类方程，首先的做法是给出求根公式下的因式分解：

$x^2 + px + q \equiv (x - \frac{-p + \sqrt{p^2 - 4q}}{2})(x - \frac{-p - \sqrt{p^2 - 4q}}{2}) \equiv 0 \pmod{m}$

解的存在性取决于根号是否存在，等价于以下方程是否有解

$y^2 \equiv p^2 - 4q \pmod{m}$

示例
求解二次同余方程 $x^2 + x + 1 \equiv 0 \pmod{67} \quad$

解

首先计算判别式 $D = 1^2 - 4 \cdot 1 \cdot 1 = -3$ 。
令方程

$y^2 \equiv -3 \pmod{67}$

等价于

$y^2 \equiv 64 \equiv 8^2 \pmod{67}$

因此，原二次同余方程转换为

$(x - \frac{-1 + 8}{2})(x - \frac{-1 - 8}{2}) \equiv 0 \pmod{67} \quad$

为了求解这个方程，我们还需要计算模 $67$ 下的 $2^{-1}$ 。
利用扩展 Euclidean 算法，寻找 $2x + 67y = 1$ 的解：

$67 = 33 \times 2 + 1 \implies 1 = 67 - 33 \times 2$

所以 $2 \cdot (-33) \equiv 1 \pmod{67}$ ，即 $2^{-1} \equiv 34 \pmod{67}$ 。

因此，方程的两个解为

$\begin{aligned} x &\equiv \frac{-1 + 8}{2} \equiv 7 \cdot 34 \equiv 37 \pmod{67} \\ x &\equiv \frac{-1 - 8}{2} \equiv -9 \cdot 34 \equiv 29 \pmod{67} \end{aligned}$

得到二次同余方程的解为 $x \equiv 37 \pmod{67}$ 或 $x \equiv 29 \pmod{67}$ 。
$\square$

# Euler 函数

Euler 函数是群论中计算元素阶数和循环群结构的关键工具。

定义
设 $n$ 为正整数，定义函数 $\varphi(n)$ 为小于等于 $n$ 且与 $n$ 互素的正整数的个数
称 $\varphi$ 为 Euler 函数 (Euler's Totient Function)「オイラーのトーシェント関数」

命题 积性性质
设 $m,n$ 为正整数，且 $\gcd(m,n) = 1$ ，则

$\varphi(mn) = \varphi(m) \varphi(n)$

命题 素数幂的计算
设 $p$ 为素数， $k$ 为正整数，则

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

理由：在 $1 \dots p^k$ 中，只有 $p$ 的倍数 $p, 2p, \dots, p^{k-1}p$ 与 $p^k$ 不互素，共有 $p^{k-1}$ 个。

结合积性与素数幂公式，可得通项公式：

命题
设 $n$ 的素因子分解为 $n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$ ，则

$\varphi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right)$

命题 Gauss 循环公式
设 $n \geq 1$ ，则

$\sum_{d \mid n} \varphi(d) = n$

其中求和是对 $n$ 的所有正因子 $d$ 进行的。

证明

考虑集合 $S = \{1, 2, \ldots, n\}$ 。我们将 $S$ 中的元素 $k$ 按照其与 $n$ 的最大公约数 $\gcd(k, n)$ 进行分类。
设 $d$ 为 $n$ 的一个因子。我们考察满足 $\gcd(k, n) = d$ 的 $k$ 的个数。
条件 $\gcd(k, n) = d$ 等价于 $\gcd(k/d, n/d) = 1$ ，且 $1 \leq k/d \leq n/d$ 。
这意味着这样的 $k$ 的个数等于小于等于 $n/d$ 且与 $n/d$ 互素的数的个数，即 $\varphi(n/d)$ 。
由于 $S$ 中每个元素都有唯一的 $\gcd(k, n)$ ，且 $\gcd(k, n)$ 必为 $n$ 的因子，所以

$n = \sum_{d \mid n} \#\{k \in S : \gcd(k, n) = d\} = \sum_{d \mid n} \varphi(n/d)$

由于 $d$ 遍历 $n$ 的所有因子时， $n/d$ 也遍历 $n$ 的所有因子，因此

$n = \sum_{d' \mid n} \varphi(d')$