8.1 整除、素数与因数分解

第 7 章学习了怎样通过递归过程把问题不断缩小。数论也从一个朴素的缩减问题开始：

> 一个整数能否被另一个整数平均分组，并且没有任何剩余？

这个问题会引出整除、素数与因数分解，并为后面的欧几里得算法、模运算和 RSA 准备基本材料。

整数与恰好除尽

整数集合记作

\mathbb Z=\{\ldots,-2,-1,0,1,2,\ldots\}.

本节中的除数始终不为零。设 $a,b\in\mathbb Z$ 且 $a\ne0$ 。如果存在整数 $k$ ，使得

b=ak,

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

a\mid b.

整数 $k$ 是恰好除尽时的商。符号 $\mid$ 表示一种关系，不是普通的除法运算符。

例子

因为

42=6\cdot7,

所以 $6\mid42$ 。

不存在整数 $k$ 使 $43=6k$ ，因此写作

6\nmid43,

读作“ $6$ 不整除 $43$ ”。

定义也允许负整数：

-5\mid30,

因为 $30=(-5)(-6)$ 。

任意非零整数都整除 $0$ ，因为

0=a\cdot0.

此外， $1$ 和 $-1$ 整除每个整数。

因数与倍数描述的是同一条等式

若 $a\mid b$ ，则 $a$ 是 $b$ 的因数，而 $b$ 是 $a$ 的倍数。

例如， $18$ 的正因数是

1,2,3,6,9,18.

$6$ 的正倍数从

6,12,18,24,30,\ldots

开始。一个固定非零整数的因数只有有限个，但它的倍数有无限多个。

用因数对避免遗漏

要列出 $36$ 的全部正因数，可以把乘积为 $36$ 的因数配成对：

1\cdot36,qquad2\cdot18,qquad3\cdot12,qquad4\cdot9,qquad6\cdot6.

读取每一对的两端，得到

\{1,2,3,4,6,9,12,18,36\}.

当第一个因数超过 $\sqrt{36}=6$ 后，只会遇到顺序相反的相同因数对。之后判断素数时，这个观察会显著缩短试除范围。

基本整除规则都来自定义

利用 $b=ak$ ，可以推导规则，而不必死记结论。

传递性

若 $a\mid b$ 且 $b\mid c$ ，则 $a\mid c$ 。

因为存在整数 $r,s$ 使得

b=ar \qquad\text{且}\qquad c=bs.

把第一条等式代入第二条：

c=(ar)s=a(rs).

又因为 $rs\in\mathbb Z$ ，所以根据定义， $a\mid c$ 。

整数线性组合

若 $a\mid b$ 且 $a\mid c$ ，那么对任意整数 $x,y$ ，

a\mid(xb+yc).

写成 $b=ar$ 、 $c=as$ 后，

xb+yc=x(ar)+y(as)=a(xr+ys).

这条规则很重要：欧几里得算法会不断用整数线性组合替换两个数，同时保持它们的公因数不变。

正在加载交互实验...

选择一个整数，把因数对排列在镜像因数格上，再为你提出的整除箭头填写整数商。完全平方数的中间因数对会合并，而非法箭头会直接显示阻止恰好除尽的非零余数。

正在加载概念检查...

正在加载本节练习...

素数与合数

从这里开始，我们主要研究正整数。

若正整数 $p>1$ 只有两个正因数

1\quad\text{和}\quad p,

就称 $p$ 为素数。

例如：

2,3,5,7,11,13,\ldots

若正整数 $n>1$ 除了 $1$ 和 $n$ 以外还有其他正因数，就称 $n$ 为合数。

例如，

15=3\cdot5,

所以 $15$ 是合数。

整数 $1$ 既不是素数，也不是合数。它只有一个正因数，而不是恰好两个。把 $1$ 排除在素数之外，才能保证素因数分解具有唯一性。

整数 $2$ 是唯一的偶素数。所有大于 $2$ 的偶数都有真因数 $2$ ，因此都是合数。

为什么试除只需进行到平方根

假设 $n$ 是合数，则

n=ab,

其中整数 $a,b$ 满足 $1<a<n$ 且 $1<b<n$ 。

如果同时有 $a>\sqrt n$ 和 $b>\sqrt n$ ，那么

ab>\sqrt n\sqrt n=n,

这与 $ab=n$ 矛盾。因此两个因数中至少有一个不超过 $\sqrt n$ 。

所以判断 $n$ 是否为素数时，只需要尝试不超过 $\sqrt n$ 的素数因子。

例子：判断 $97$

因为

9<\sqrt{97}<10,

只需尝试素数 $2,3,5,7$ 。

$97$ 不是偶数，所以 $2\nmid97$ 。

各位数字之和为 $9+7=16$ ，所以 $3\nmid97$ 。

末位不是 $0$ 或 $5$ ，所以 $5\nmid97$ 。

除以 $7$ 后余数不为零。

没有任何不超过 $\sqrt{97}$ 的素数整除它，因此 $97$ 是素数。

素因数分解

素因数分解把一个大于 $1$ 的整数写成若干素数的乘积。

不断拆分合数因子：

360=36\cdot10=(6\cdot6)(2\cdot5) =(2\cdot3)(2\cdot3)(2\cdot5).

把相同素数合并为指数形式：

360=2^3\cdot3^2\cdot5.

指数 $3$ 表示因子 $2$ 出现三次；指数 $2$ 表示因子 $3$ 出现两次。

算术基本定理

算术基本定理说明：

> 每个大于 $1$ 的整数都能写成素数的乘积；除去因子排列顺序后，这种分解是唯一的。

所以

60=2^2\cdot3\cdot5

和

60=5\cdot2\cdot3\cdot2

只是顺序不同的同一份素因数分解。 $60$ 不可能拥有另一套真正不同的素因数清单。

定理包含两个结论：

1. 存在性：不断拆分合数最终会到达素数，因为每次拆分都使用更小的正整数。

2. 唯一性：同一整数的两份素数乘积必须包含相同的素数及相同的指数。

存在性再次呼应第 7 章的良基递归：正整数不可能永远严格下降。

根据素因数分解统计正因数

设

n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r},

其中 $p_i$ 是互不相同的素数， $e_i$ 是正整数。

构造 $n$ 的任意正因数时，需要为每个素数选择一个指数：

p_i^0,p_i^1,\ldots,p_i^{e_i}.

对素数 $p_i$ 有 $e_i+1$ 种选择。根据第 6 章的乘法原理，正因数个数为

\tau(n)=\prod_{i=1}^{r}(e_i+1).

符号 $\tau(n)$ 表示 $n$ 的正因数数量。

例如，

360=2^3\cdot3^2\cdot5^1,

所以

\tau(360)=(3+1)(2+1)(1+1)=24.

正在加载交互实验...

把合数方块沿因数树不断拆开，直到每个叶子都是素数。锻造炉会持续检查尚未完成的合数叶子，再把整棵树折叠为指数清单，并通过选择指数坐标生成因数，而不是盲目枚举。

正在加载概念检查...

正在加载本节练习...

注意

a\mid b

必须拥有整数商。素因数分解进一步为每个大于

1

的整数提供一份唯一的不可再分构造清单。

本节衔接

素因数分解可以找出公因数，但分解大整数的成本很高。第 8.2 节将介绍欧几里得算法：它不需要分解输入，只靠不断缩小余数就能求出最大公因数。

8.1 整除、素数与因数分解

第 7 章学习了怎样通过递归过程把问题不断缩小。数论也从一个朴素的缩减问题开始：

> 一个整数能否被另一个整数平均分组，并且没有任何剩余？

这个问题会引出整除、素数与因数分解，并为后面的欧几里得算法、模运算和 RSA 准备基本材料。

整数与恰好除尽

整数集合记作

\mathbb Z=\{\ldots,-2,-1,0,1,2,\ldots\}.

本节中的除数始终不为零。设 $a,b\in\mathbb Z$ 且 $a\ne0$ 。如果存在整数 $k$ ，使得

b=ak,

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

a\mid b.

整数 $k$ 是恰好除尽时的商。符号 $\mid$ 表示一种关系，不是普通的除法运算符。

例子

因为

42=6\cdot7,

所以 $6\mid42$ 。

不存在整数 $k$ 使 $43=6k$ ，因此写作

6\nmid43,

读作“ $6$ 不整除 $43$ ”。

定义也允许负整数：

-5\mid30,

因为 $30=(-5)(-6)$ 。

任意非零整数都整除 $0$ ，因为

0=a\cdot0.

此外， $1$ 和 $-1$ 整除每个整数。

因数与倍数描述的是同一条等式

若 $a\mid b$ ，则 $a$ 是 $b$ 的因数，而 $b$ 是 $a$ 的倍数。

例如， $18$ 的正因数是

1,2,3,6,9,18.

$6$ 的正倍数从

6,12,18,24,30,\ldots

开始。一个固定非零整数的因数只有有限个，但它的倍数有无限多个。

用因数对避免遗漏

要列出 $36$ 的全部正因数，可以把乘积为 $36$ 的因数配成对：

1\cdot36,qquad2\cdot18,qquad3\cdot12,qquad4\cdot9,qquad6\cdot6.

读取每一对的两端，得到

\{1,2,3,4,6,9,12,18,36\}.

当第一个因数超过 $\sqrt{36}=6$ 后，只会遇到顺序相反的相同因数对。之后判断素数时，这个观察会显著缩短试除范围。

基本整除规则都来自定义

利用 $b=ak$ ，可以推导规则，而不必死记结论。

传递性

若 $a\mid b$ 且 $b\mid c$ ，则 $a\mid c$ 。

因为存在整数 $r,s$ 使得

b=ar \qquad\text{且}\qquad c=bs.

把第一条等式代入第二条：

c=(ar)s=a(rs).

又因为 $rs\in\mathbb Z$ ，所以根据定义， $a\mid c$ 。

整数线性组合

若 $a\mid b$ 且 $a\mid c$ ，那么对任意整数 $x,y$ ，

a\mid(xb+yc).

写成 $b=ar$ 、 $c=as$ 后，

xb+yc=x(ar)+y(as)=a(xr+ys).

这条规则很重要：欧几里得算法会不断用整数线性组合替换两个数，同时保持它们的公因数不变。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

素数与合数

从这里开始，我们主要研究正整数。

若正整数 $p>1$ 只有两个正因数

1\quad\text{和}\quad p,

就称 $p$ 为素数。

例如：

2,3,5,7,11,13,\ldots

若正整数 $n>1$ 除了 $1$ 和 $n$ 以外还有其他正因数，就称 $n$ 为合数。

例如，

15=3\cdot5,

所以 $15$ 是合数。

整数 $1$ 既不是素数，也不是合数。它只有一个正因数，而不是恰好两个。把 $1$ 排除在素数之外，才能保证素因数分解具有唯一性。

整数 $2$ 是唯一的偶素数。所有大于 $2$ 的偶数都有真因数 $2$ ，因此都是合数。

为什么试除只需进行到平方根

假设 $n$ 是合数，则

n=ab,

其中整数 $a,b$ 满足 $1<a<n$ 且 $1<b<n$ 。

如果同时有 $a>\sqrt n$ 和 $b>\sqrt n$ ，那么

ab>\sqrt n\sqrt n=n,

这与 $ab=n$ 矛盾。因此两个因数中至少有一个不超过 $\sqrt n$ 。

所以判断 $n$ 是否为素数时，只需要尝试不超过 $\sqrt n$ 的素数因子。

例子：判断 $97$

因为

9<\sqrt{97}<10,

只需尝试素数 $2,3,5,7$ 。

$97$ 不是偶数，所以 $2\nmid97$ 。

各位数字之和为 $9+7=16$ ，所以 $3\nmid97$ 。

末位不是 $0$ 或 $5$ ，所以 $5\nmid97$ 。

除以 $7$ 后余数不为零。

没有任何不超过 $\sqrt{97}$ 的素数整除它，因此 $97$ 是素数。

素因数分解

素因数分解把一个大于 $1$ 的整数写成若干素数的乘积。

不断拆分合数因子：

360=36\cdot10=(6\cdot6)(2\cdot5) =(2\cdot3)(2\cdot3)(2\cdot5).

把相同素数合并为指数形式：

360=2^3\cdot3^2\cdot5.

指数 $3$ 表示因子 $2$ 出现三次；指数 $2$ 表示因子 $3$ 出现两次。

算术基本定理

算术基本定理说明：

> 每个大于 $1$ 的整数都能写成素数的乘积；除去因子排列顺序后，这种分解是唯一的。

所以

60=2^2\cdot3\cdot5

和

60=5\cdot2\cdot3\cdot2

只是顺序不同的同一份素因数分解。 $60$ 不可能拥有另一套真正不同的素因数清单。

定理包含两个结论：

1. 存在性：不断拆分合数最终会到达素数，因为每次拆分都使用更小的正整数。

2. 唯一性：同一整数的两份素数乘积必须包含相同的素数及相同的指数。

存在性再次呼应第 7 章的良基递归：正整数不可能永远严格下降。

根据素因数分解统计正因数

设

n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r},

其中 $p_i$ 是互不相同的素数， $e_i$ 是正整数。

构造 $n$ 的任意正因数时，需要为每个素数选择一个指数：

p_i^0,p_i^1,\ldots,p_i^{e_i}.

对素数 $p_i$ 有 $e_i+1$ 种选择。根据第 6 章的乘法原理，正因数个数为

\tau(n)=\prod_{i=1}^{r}(e_i+1).

符号 $\tau(n)$ 表示 $n$ 的正因数数量。

例如，

360=2^3\cdot3^2\cdot5^1,

所以

\tau(360)=(3+1)(2+1)(1+1)=24.

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

注意

a\mid b

必须拥有整数商。素因数分解进一步为每个大于

1

的整数提供一份唯一的不可再分构造清单。

本节衔接

素因数分解可以找出公因数，但分解大整数的成本很高。第 8.2 节将介绍欧几里得算法：它不需要分解输入，只靠不断缩小余数就能求出最大公因数。

8.1 整除、素数与因数分解

8.1 整除、素数与因数分解

整数与恰好除尽

例子

因数与倍数描述的是同一条等式

用因数对避免遗漏

基本整除规则都来自定义

传递性

整数线性组合

素数与合数

为什么试除只需进行到平方根

例子：判断 979797

素因数分解

算术基本定理

根据素因数分解统计正因数

本节衔接

8.1 整除、素数与因数分解

8.1 整除、素数与因数分解

整数与恰好除尽

例子

因数与倍数描述的是同一条等式

用因数对避免遗漏

基本整除规则都来自定义

传递性

整数线性组合

素数与合数

为什么试除只需进行到平方根

例子：判断 979797

素因数分解

算术基本定理

根据素因数分解统计正因数

本节衔接

例子：判断 $97$

例子：判断 $97$