文章迁移信息

本文写于 240323，原笔记名「🌻质数与合数」，251011 由本地知识库迁移而来。

为了更好理解本章节，建议先学习站内文章关于同余。

本文题目难度标识：🟩简单，🟨中等，🟥困难。

素数与合数

如果 1 的整数 p 的正因数只是 1 和 p，则 p 称为素数（或质数、不可约数）。大于 1 但又不是素数的正整数称为合数。

定理 ZS-1（算术基本定理）：每一个大于 1 的正整数都可以唯一地写成素数或两个或多个素数的乘积，其中素数因子以非递减序排列。

定理 ZS-2：如果 n 是一个合数，那么 n 必有一个素因子小于等于

\sqrt{ n }

定理 ZS-3：存在无限多个素数。

证明：假设只有有限多个素数 $p_{1},p_{2},\dots p_{n}$ 。令 $Q=p_{1}p_{2}\dots p_{n}+1$

若 Q 是素数，即找到了除 $p_{1},p_{2},\dots p_{n}$ 以外的素数。
若 Q 是合数，根据算术基本定理，Q 能被写成两个或多个素数之积。但是，没有一个素数 $p_{i}$ 能整除 Q。因此，存在一个不在 $p_{1},p_{2},\dots p_{n}$ 的素数。因此，存在无限多个素数。

$p$ 和 $-p$ 总是同为素数或者同为合数。如果没有特别说明，素数总是指正的素数。

整数的因数是素数，则该素数称为该整数的素因数（素约数）。

最大公约数

令 a 和 b 是两个整数，不全为 0。能使 $d\mid a$ 和 $d\mid b$ 的最大整数 d 称为 a 和 b 的最大公约数，记为 $gcd(a,b)$ 。不引起歧义时可简写为 $(a,b)$ 。

整数 a 和 b 是互素的如果它们的最大公约数为 1.
如果当 $1≤i<j≤n$ 时有 $gcd(a_i, a_j) = 1$ ，则称整数 $a_{1},a_{2},\dots,a_{n}$ 是两两互素的。

关于 0 和 0 的最大公约数

一些作者认为 0 和 0 的最大公约数无定义，其余作者一般将其视为 0。C++ STL 的实现中采用后者，即认为 0 和 0 的最大公约数为 0^[1]。

素因子分解式求最大公约数：假定两个正整数 a 和 b 的素因子分解式为：

\begin{aligned} a&= p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{n}^{a_{n}} \\ b&= p_{1}^{b_{1}}p_{2}^{b_{2}}\dots p_{n}^{b_{n}} \end{aligned}

其中每个指数都是非负整数，而且出现在 a 和 b 的素因子分解式中的所有素数都出现在这两个分解式中，必要时以 0 指数出现。则 a 和 b 的最大公约数：

gcd(a,b)= p_{1}^{\min (a_{1},b_{1})}p_{2}^{\min (a_{2},b_{2})}\dots p_{n}^{\min (a_{n},b_{n})} \\

x 是 a 和 b 的公因子，当且仅当 x 是 a 和 b 的最大公约数的因子。（来自题目：🟩 2427. 公因子的数目 - 力扣（LeetCode））

定理 ZS-4：设

a = bq + r

，其中

a,b,q

和

r

是整数。那么

gcd(a,b) = gcd(b,r)

。

即 $gcd(a,b) = gcd(b, a \bmod b)$ ，这也是辗转相除法的理论基础。

证明（利用站内文章推论 TY-2.1）：

假设 d 整除 a 和 b，那么 d 也整除 $a − bq = r$ 。因此，a 和 b 的任何公约数也是 b 和 r 的任何公约数。
假设 d 整除 b 和 r，那么 d 也整除 $bq + r = a$ 。因此，b 和 r 的任何公约数也必须是 a 和 b 的任何公约数。
所以， $gcd(a,b) = gcd(b,r)$ 。

定理 ZS-5（贝祖定理）：如果 a 和 b 为正整数，则存在整数 s 和 t 使

gcd(a,b)=sa+tb

。

其中，s 和 t 称为 a 和 b 的贝祖系数； $gcd(a,b)=sa+tb$ 称为贝祖恒等式。

方法：

欧几里德算法的反向处理
扩展欧几里德算法

引理 ZS-6：如果

a,b

和

c

是正整数使得

gcd(a,b)=1

且

a\mid bc

, 那么

a\mid c

。

ME：理解方式：a 和 b 互素，b 和 a 没有公因子。但是 bc 和 a 有公因子，那么就是 c 携带了这个公因子。

引理 ZS-7：如果 p 是素数，

p|a_1a_2\dots a_n

，其中

a_i

为整数，则对于某个 i，

p|a_i

。

定理 ZS-8（正整数素因子分解式的唯一性）：每个整数最多只有一种方式可以写成非递减序素数的乘积。

定理 ZS-9

令 m 为正整数，a、b 和 c 为整数。如果 $ac≡bc~(\bmod m)$ 且 $gcd(c,m)=1$ ，则 $a≡b~(\bmod m)$ 。

证明：因为 $ac≡bc~(\bmod m)$ ，则 $m\mid ac-bc$ ，即 $m\mid c(a-b)$ 。根据引理 ZS-6，因为 $gcd(c,m)=1$ ，所以可得 $m\mid a-b$ 。从而得到结论。

最小公倍数

正整数 a 和 b 的最小公倍数是能被 a 和 b 整除的最小正整数，记为 lcm(a,b)。

\begin{aligned} a&= p_{1}^{a_{1}}p_{2}^{a_{2}}\dots p_{n}^{a_{n}} \\ b&= p_{1}^{b_{1}}p_{2}^{b_{2}}\dots p_{n}^{b_{n}} \\ lcm(a,b)&=p_{1}^{\max (a_{1},b_{1})}p_{2}^{\max (a_{2},b_{2})}\dots p_{n}^{\max (a_{n},b_{n})} \end{aligned}

定理 ZS-10：令 a 和 b 为正整数，则

ab=gcd(a,b)\cdot lcm(a,b)

互质（互素）

若 $gcd(a_1,a_2)=1$ ，则称 $a_1$ 和 $a_2$ 互素（既约）；若 $gcd(a_1,\dots ,a_k)=1$ ，则称 $a_1,\dots ,a_k$ 互素（既约）。

多个整数互素，不一定两两互素。例如 6、10 和 15 互素，但是任意两个都不互素。

算法

质数筛

更多质数筛详见站内文章判断质数。

求最大公约数

辗转相除法（欧几里得算法）

理论基础：定理 ZS-4。

假定 a 和 b 为正整数，且 a≥b，令 $r_0=a$ 和 $r_1=b$ ，当连续应用整除算法时，可得

\begin{aligned} r_{0}=&r_{1}q_{1}+r_{2}&0\leq r_{2}<r_{1} \\ r_{1}=&r_{2}q_{2}+r_{3}&0\leq r_{3}<r_{2} \\ \vdots \\ r_{n-2}=&r_{n-1}q_{n-1}+r_{n}&0\leq r_{n}<r_{n-1} \\ r_{n-1}=&r_{n}q_{n} \end{aligned}

$gcd(a,b)=gcd(r_0,r_1)=gcd(r_1,r_2)=\dots=gcd(r_{n-1},r_n)=r$

最大公约数是除法序列中最后一个非零余数。

v 直观的，我们可以得到一个递归版本：

// 递归版本
public static int gcd(int a,int b){
	if (b == 0) return a;
	return gcd(b, a % b);
}

根据递归版本可写出迭代版本：

// 迭代版本
public int gcd(int a, int b) {
	while (b != 0) {
		a %= b;
		swap(new int[]{a,b}); // 交换结束 b 是小的那一个
	}
	return a;
}

// 自己写的版本
public int gcd(int a,int b){
	while(a%b!=0){
		a%=b;
		swap(new int[]{a,b});
	}
	return b;
}