整除、质数与最大公约数

1. 为什么从整除开始

后面学习同余、模逆元和有限域时，会反复遇到“一个数能否被另一个数整除”以及“两个数是否互质”。整除不是普通除法的另一种写法，而是一个真假关系。

读完这一篇，应当能够回答：

1. $a\mid b$ 的严格含义是什么；
2. 质数和合数怎样区分；
3. 最大公约数与互质有什么关系；
4. 为什么互质会成为模逆元存在的前置条件。

---

2. 整除的定义

对整数 $a,b$，如果存在整数 $k$，使得

$$b=ka,$$

就称 $a$ 整除 $b$，记作

$$a\mid b.$$

例如：

$$3\mid12,$$

因为存在整数 $4$，使

$$12=3 * 4.$$

相反，$5\nmid12$，因为不存在整数 $k$ 使 $12=5k$。

整除与除法的区别

• $a\mid b$ 是一个命题，结果为真或假；
• $b/a$ 是一个运算，结果是一个数；
• 即使 $b/a$ 在有理数中有结果，也不代表 $a\mid b$。

例如 $12/5$ 是有理数，但 $5\nmid12$。

---

3. 质数与合数

质数（Prime Number）是大于 1，并且正因数只有 1 和自身的整数。

例如：

$$2,3,5,7,11,\dots$$

合数（Composite Number）是大于 1、但不是质数的整数。它可以分解为两个更小正整数的乘积，例如：

$$12=3 * 4.$$

数字 1 既不是质数，也不是合数。

质数在后续知识中很重要：当模数 $p$ 为质数时，任意 $1\leq a<p$ 都与 $p$ 互质，因此每个非零余数类都有乘法逆元。

---

4. 最大公约数

同时整除 $a$ 和 $b$ 的正整数称为它们的公约数。最大的公约数记作

$$\gcd(a,b).$$

例如，18 的正因数为

$$1,2,3,6,9,18,$$

12 的正因数为

$$1,2,3,4,6,12.$$

两者共同拥有的最大正因数是 6，所以

$$\gcd(18,12)=6.$$

枚举因数可以帮助理解定义，但对于很大的整数并不高效。实际计算通常使用下一篇的欧几里得算法。

---

5. 互质

如果

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

就称 $a$ 与 $b$ 互质（Coprime）。

互质不要求两个数本身都是质数。例如：

$$\gcd(8,15)=1,$$

所以 8 和 15 互质，虽然它们都是合数。

这个条件会在模逆元中变成关键判据：

$$a\text{ 在模 }n\text{ 下可逆} \iff \gcd(a,n)=1.$$

当前只先记住这条联系；其原因将在模逆元中通过 Bézout 等式推导。

---

6. 容易混淆的地方

“没有共同因数”并不准确

任意两个正整数都至少有共同因数 1。互质的准确含义是：最大公约数等于 1。

质数与互质不是同一概念

• “质数”描述一个整数自身；
• “互质”描述两个整数之间的关系。

最大公约数只取正值

即使输入包含负数，最大公约数通常也约定为非负整数。

---

7. 自测

1. 为什么 $4\mid20$？
2. 为什么 $6\nmid20$？
3. 9 是质数还是合数？
4. $\gcd(24,18)$ 等于多少？
5. 8 与 15 为什么互质？

参考答案

1. 因为 $20=4 * 5$，且 5 是整数。
2. 因为不存在整数 $k$ 使 $20=6k$。
3. 9 是合数，因为 $9=3 * 3$。
4. $\gcd(24,18)=6$。
5. 因为它们的最大公约数是 1。

下一篇：欧几里得算法与 Bézout 等式。