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

设 a 和 b 是两个整数，如果 d|a 且 d|b，则称 d 是 a 与 b 的公因子，或公约数.除 0 之外，任何整数只有有限个因子.因而，两个不全为 0 的整数只有有限个公因子，其中最大的叫做最大公因子，或最大公约数.

定义 11.2 设 a 和 b 是两个不全为 0 的整数，称 a 与 b 的公因子中最大的为 a 与 b 的最大公因子，或最大公约数，记作 \gcd(a,b).

例如，12 与 18 的正公约数有 1,2,3 和 6，故 \gcd(12,18)=6.

设 a 和 b 是两个非零整数，如果 a|m 且 b|m，则称 m 是 a 与 b 的公倍数.a 与 b 有无穷多个公倍数，其中最小的正公倍数叫做最小公倍数.

定义 11.3 设 a 和 b 是两个非零整数，称 a 与 b 最小的正公倍数为 a 与 b 的最小公倍数，记作 \operatorname{lcm}(a,b).

例如，12 与 18 的公倍数有 36,72,108 等，故 \operatorname{lcm}(12,18)=36.

显然，对任意的正整数 a，\gcd(0,a)=a，\gcd(1,a)=1，\operatorname{lcm}(1,a)=a.

根据定义，最大公约数和最小公倍数有下述性质.

定理 11.5 （1）若 a|m,b|m，则 \operatorname{lcm}(a,b)|m.

（2）若 d|a,d|b，则 d|\gcd(a,b).

证明 （1）记 M=\operatorname{lcm}(a,b)，设 m=qM+r，0\leqslant r<M.

根据性质 11.1.1，由 a|m,a|M，及 r=m-qM，可推出 a|r.同理，有 b|r.即 r 是 a 和 b 的公倍数.根据最小公倍数的定义，必有 r=0.得证 M|m.

（2）记 D=\gcd(a,b)，令 m=\operatorname{lcm}(D,D).若 m=D，自然有 d|D，结论成立.否则 m>D，注意到 d|a,D|a，由(1)，得 m|a.同理，m|b.即 m 是 a 和 b 的公因子，与 D 是 a 和 b 的最大公约数矛盾.

解读：两条性质说的是同一件事的两面：\operatorname{lcm} 是"最小的公倍数"，所以任何公倍数都被它整除；\gcd 是"最大的公因子"，所以任何公因子都整除它.证明手法都是带余除法造矛盾.

可以利用整数的素因子分解，求最大公约数和最小公倍数.设

a=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k},\quad b=p_1^{s_1}p_2^{s_2}\cdots p_k^{s_k}

其中 p_1,p_2,\cdots,p_k 是不同的素数，r_1,r_2,\cdots,r_k,s_1,s_2,\cdots,s_k 是非负整数.则

\gcd(a,b)=p_1^{\min(r_1,s_1)}p_2^{\min(r_2,s_2)}\cdots p_k^{\min(r_k,s_k)}
\operatorname{lcm}(a,b)=p_1^{\max(r_1,s_1)}p_2^{\max(r_2,s_2)}\cdots p_k^{\max(r_k,s_k)}

例 11.3 求 150 和 168 的最大公约数和最小公倍数.

解 对 150 和 168 做素因子分解：

150=2\times 3\times 5^2,\quad 168=2^3\times 3\times 7

可把它们写成

150=2^1\times 3^1\times 5^2\times 7^0,\quad 168=2^3\times 3^1\times 5^0\times 7^1

于是有

\gcd(150,168)=2^1\times 3^1\times 5^0\times 7^0=6
\operatorname{lcm}(150,168)=2^3\times 3^1\times 5^2\times 7^1=4200

解读：把两个数补成同一组素因子（缺的写 0 次幂）是这一步的关键，否则无法逐位取 \min / \max.注意 \gcd\cdot\operatorname{lcm}=a\cdot b，可用于自检：6\times 4200=25\ 200=150\times 168.

求最大公约数的常用方法是辗转相除法.它是基于下述定理构造的.

定理 11.6 设 a=qb+r，其中 a,b,q,r 都是整数，则 \gcd(a,b)=\gcd(b,r).

证明 只需证 a 与 b 和 b 与 r 有相同的公因子.设 d 是 a 与 b 的公因子，即 d|a 且 d|b.注意到，r=a-qb，由性质 11.1.1，有 d|r.从而，d|b 且 d|r，即 d 也是 b 与 r 的公因子.反之一样，设 d 是 b 与 r 的公因子，即 d|b 且 d|r.注意到，a=qb+r，故有 d|a.从而，d|a 且 d|b，即 d 也是 a 与 b 的公因子.

设整数 a,b，且 b\neq 0.做带余除法

a=q_1b+r_2\qquad 0\leqslant r_2<|b|

若 r_2>0，再对 b 和 r_2 做带余除法，得

b=q_2r_2+r_3\qquad 0\leqslant r_3<r_2

重复上述过程.由于 |b|>r_2>r_3>\cdots\geqslant 0，必存在 k 使 r_{k+1}=0.于是有

\begin{aligned} a &= q_1b+r_2 & 1\leqslant r_2<|b| \\ b &= q_2r_2+r_3 & 1\leqslant r_3<r_2 \\ r_2 &= q_3r_3+r_4 & 1\leqslant r_4<r_3 \\ &\vdots & \vdots \\ r_{k-2} &= q_{k-1}r_{k-1}+r_k & 1\leqslant r_k<r_{k-1} \\ r_{k-1} &= q_kr_k \end{aligned} \tag{①}

根据定理 11.6，有

\gcd(a,b)=\gcd(b,r_2)=\cdots=\gcd(r_{k-1},r_k)=r_k

这就是辗转相除法，又称作欧几里得(Euclid)算法.

定理 11.7 设 a 和 b 不全为 0，则存在整数 x 和 y 使得 \gcd(a,b)=xa+yb.

证明 记 a=r_0,b=r_1，①式可写成

r_i=q_{i+1}r_{i+1}+r_{i+2}\qquad i=0,1,\cdots,k-2
r_{k-1}=q_kr_k

其中 \gcd(a,b)=r_k.把上式改写成

r_i=r_{i-2}-q_{i-1}r_{i-1}\qquad i=2,3,\cdots,k

从后向前逐个回代，就可将 r_k 表示成 a 和 b 的线性组合.

记 x_{k-1}=1,y_{k-1}=-q_{k-1}，把最后一式写成

r_k=x_{k-1}r_{k-2}+y_{k-1}r_{k-1}

一般地，设 r_k=x_ir_{i-1}+y_ir_i，代入 r_i

\begin{aligned} r_k &= x_ir_{i-1}+y_i(r_{i-2}-q_{i-1}r_{i-1}) \\ &= y_ir_{i-2}+(x_i-q_{i-1}y_i)r_{i-1} \end{aligned}

得

x_{i-1}=y_i,\quad y_{i-1}=x_i-q_{i-1}y_i,\quad i=k-1,k-2,\cdots,2

取 x=x_1,y=y_1，得 r_k=xa+yb.

解读：定理 11.7 是辗转相除法的"副产品"：只要把每步除法反着代回去，最大公因子就能写成 a,b 的整系数线性组合.这个结论本身很简单，却是下一节一次同余方程有解判据的来源.

例 11.4 求 210 与 715 的最大公因子 d，并把 d 表示成 210 和 715 的线性组合，即求整数 x 和 y 使 d=210x+715y.

解 用辗转相除法

715=3\times 210+85
210=2\times 85+40
85=2\times 40+5
40=8\times 5

得

\gcd(715,210)=5

由上面的式子，又有

\begin{aligned} 5 &= 85-2\times 40 \\ &= 85-2\times(210-2\times 85) \\ &= 5\times 85-2\times 210 \\ &= 5\times(715-3\times 210)-2\times 210 \\ &= -17\times 210+5\times 715 \end{aligned}

定义 11.4 如果 \gcd(a,b)=1，则称 a 和 b 互素.

如果整数 a_1,a_2,\cdots,a_n 中的任意两个都互素，则称它们两两互素.

例如，4 和 15 互素，4,9,11,35 两两互素，而 9 和 12 不互素.

定理 11.8 整数 a 和 b 互素的充分必要条件是存在整数 x 和 y 使得 xa+yb=1.

证明 必要性可由定理 11.7 得到.

充分性.设 xa+yb=1，x 和 y 是整数.又设 d>0 是 a 和 b 的公因子，由性质 11.1.1，d|xa+yb，即 d|1.再由性质 11.1.5，必有 d=1，得证 a 和 b 互素.

例 11.5 设 a|c,b|c，且 a 与 b 互素，则 ab|c.

证明 根据定理 11.8，存在整数 x,y，使 xa+yb=1.两边同乘以 c，得 cxa+cyb=c.

又由 a|xa 和 b|c，可得 ab|cxa.同理，ab|cyb.于是，有 ab|cxa+cyb，即 ab|c.

解读：定理 11.8 把"互素"这个关于因子的说法，翻译成了一个关于线性组合的等式 xa+yb=1.例 11.5 正是这条翻译的直接用途——"a|c 且 b|c"在没有互素条件时推不出 ab|c（如 6|12，10|12，但 60\nmid 12）.