整除与素数

参考资料

• 整除 - 维基百科
• 素数 - 维基百科

引入

整除 是数论一切性质的起点：从素数分布、最大公约数到费马小定理，最底层都是「$a$ 能不能整除 $b$」。

整除

定义

整数 $a,b$（$a\ne 0$），若存在整数 $q$ 使 $b=aq$，称 $a$ 整除 $b$，记为：

$$a\mid b$$

否则记 $a\nmid b$。

性质

性质	描述
传递性	$a\mid b,\,b\mid c\Rightarrow a\mid c$
线性组合	$a\mid b,\,a\mid c\Rightarrow a\mid(bx+cy)$
整除积	$a\mid b\Rightarrow a\mid bc$
同号大小	$a\mid b,\,b\ne 0\Rightarrow\lvert a\rvert\le\lvert b\rvert$
反对称	$a\mid b,\,b\mid a\Rightarrow a=\pm b$

带余除法

对任意整数 $a,b$（$b>0$），存在 唯一 的整数 $q,r$ 使：

$$a=bq+r,\quad 0\le r<b$$

$q$ 称为 商，$r$ 称为 余数。带余除法是 同余 与欧几里得算法的基础。

最大公约数

定义

整数 $a,b$ 不全为 $0$，最大的同时整除 $a,b$ 的正整数称为 最大公约数，记为：

$$\gcd(a,b)\quad\text{或}\quad (a,b)$$

若 $(a,b)=1$，称 $a,b$ 互素。

欧几里得算法

基于性质 $(a,b)=(b,a\bmod b)$：

$$\begin{aligned} \gcd(252,105)&=\gcd(105,42) \\ &=\gcd(42,21) \\ &=\gcd(21,0)=21 \end{aligned}$$

复杂度 $O(\log\min(a,b))$。

裴蜀定理

对任意整数 $a,b$，存在整数 $x,y$ 使：

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

$x,y$ 可由 扩展欧几里得算法 求出。

推论：$ax+by=c$ 有整数解 $\iff\gcd(a,b)\mid c$。

最小公倍数

定义：同时是 $a,b$ 倍数的最小正整数，记 $\operatorname{lcm}(a,b)$ 或 $[a,b]$。

关键恒等式：

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

素数

定义

大于 $1$ 的整数 $p$，若其因子只有 $1$ 和 $p$，称为 素数（质数）；否则称为 合数。

$1$ 既不是素数也不是合数。最小的素数是 $2$，也是唯一的偶素数。

算术基本定理

任意大于 $1$ 的整数 $n$ 可 唯一地 分解为素数的乘积（不计顺序）：

$$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$$

这是整个数论的「基石」。

tip

「唯一分解」让我们能把整除、$\gcd$、$\operatorname{lcm}$ 都化为对指数的比较：

$$\gcd=\prod p_i^{\min(a_i,b_i)},\quad \operatorname{lcm}=\prod p_i^{\max(a_i,b_i)}$$

素数的无穷性

欧几里得反证法：假设素数有限 $p_1,\dots,p_k$，考虑 $N=p_1p_2\cdots p_k+1$。$N$ 不被任何 $p_i$ 整除，故 $N$ 本身是素数，或有新素因子，矛盾。

素数判定

试除法：判断 $n$ 是否为素数，只需检验 $2$ 到 $\lfloor\sqrt n\rfloor$ 之间的因子。

埃拉托色尼筛法

筛 $1\sim N$ 中的素数：从 $2$ 起，将每个素数的所有倍数划掉。复杂度 $O(N\log\log N)$。

线性筛（欧拉筛）可做到 $O(N)$。

素数分布

素数计数函数

$\pi(x)$ 表示不超过 $x$ 的素数个数。素数定理（PNT）给出：

$$\pi(x)\sim\frac{x}{\ln x}\quad(x\to\infty)$$

即「在 $x$ 附近，每 $\ln x$ 个整数中约有一个素数」。

著名猜想

• 孪生素数猜想：存在无穷多对 $(p,p+2)$ 都是素数（未证）。
• 哥德巴赫猜想：每个大于 $2$ 的偶数可表为两个素数之和（未证；陈景润给出「$1+2$」最佳进展）。
• 黎曼猜想：与 $\pi(x)$ 的精细分布有关，是数学界第一大未解之谜。