5.4.1 整除性

5.4.1.1 整除性和基本整除法则

1. 因子

整数 $b \in Z$ 可被整数 $a$ 整除而无余数当且仅当存在整数 $q$ 使得

\begin{matrix} (5.214) & q a = b \end{matrix}

成立. 这里 $a$ 是 $b$ 在 $Z$ 中的因子, $q$ 是对于 $a$ 的余因子; $b$ 是 $a$ 的倍数. 将 “ $a$ 整除 $b$ ” 记作 $a ∣ b$ . 将 “ $a$ 不整除 $b$ ” 记作 $a ∤ b$ . 整除性关系 (5.214) 是 $Z$ 中的二元关系 (参见第 444 页 5.2.3, 2.). 类似地, 整除性也在自然数集中定义.

2. 基本整除法则

(DR1) 对于每个 $a \in Z$ ,我们有 $1 | a, a | a, a ∣ 0$ .(5.215)

(DR2) 如果 $a ∣ b$ ,那么 $(- a) ∣ b$ 及 $a ∣ (- b)$ .(5.216)

(DR3) $a | b, b | a$ 蕴涵 $a = b$ ,或 $a = - b$ .(5.217)

(DR4) $a ∣ 1$ 蕴涵 $a = 1$ ,或 $a = - 1$ .(5.218)

(DR5) $a ∣ b$ 及 $b \neq 0$ 蕴涵 $| a | \leq | b |$ .(5.219)

(DR6) $a ∣ b$ 蕴涵 $a ∣ z b$ (对每个 $z \in Z$ ).(5.220)

(DR7) $a ∣ b$ 蕴涵 $a z ∣ b z$ (对每个 $z \in Z$ ).(5.221)

(DR8) $a z ∣ b z$ 并且 $b \neq 0$ 蕴涵 $a ∣ b$ (对每个 $z \in Z$ ).(5.222)

(DR9) $a ∣ b$ 并且 $b ∣ c$ 蕴涵 $a ∣ c$ .(5.223)

(DR10) $a ∣ b$ 并且 $c ∣ d$ 蕴涵 $a c ∣ b d$ .(5.224)

(DR11) $a ∣ b$ 并且 $a ∣ c$ 蕴涵 $a ∣ (z_{1} b + z_{2} c)$ (对任意 $z_{1}, z_{2} \in Z$ )(5.225)

(DR12) $a ∣ b$ 并且 $a ∣ (b + c)$ 蕴涵 $a ∣ c$ .(5.226)

5.4.1.2 素数

1. 素数的定义和性质

正整数 $p (p > 1)$ 称为素数,当且仅当 1 和 $p$ 是它在正整数集 $N$ 中仅有的因子. 不是素数的正整数称为合数.

对于每个整数, 最小的不为 1 的正因子是一个素数. 存在无穷多个素数.

正整数 $p (p > 1)$ 是素数,当且仅当对于任意正整数 $a, b, p ∣ (a b)$ 蕴涵 $p ∣ a$ 或 $p ∣ b$ .

2. 埃拉托色尼 (Eratosthenes) 筛法

应用埃拉托色尼筛法,可以确定每个小于给定的正整数 $n$ 的素数:

a) 列出所有 2 到 $n$ 的正整数.

b) 在 2 下方画一道横线, 并去掉其后所有 2 的倍数.

c) 如果 $p$ 是第一个没有去掉也没有在下方画横线的数,那么在 $p$ 下方画一道横线,并去掉每个 $p$ 的倍数 (从 $2 p$ 开始,按原列出的表计数).

d) 对每个 $p (p \leq \sqrt{n})$ 重复步骤 c),并停止算法.

每个下方画了横线而没有去掉的数都是素数. 这样就得到所有 $\leq n$ 的素数.

素数称作整数集的素元素.

3. 素数对

相差 2 的两个素数形成一个素数对(孪生素数).

$(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103)$ 是素数对.

4. 三素数组

出现在四个连续奇数中的三个素数称作三素数组.

$(5, 7, 11), (7, 11, 13), (11, 13, 17), (13, 17, 19), (17, 19, 23), (37, 41, 43)$ 是三素数组.

5. 四素数组

如果五个连续奇数中的前两个和后两个都是素数对, 那么这四个数称作一个四素数组.

$(5, 7, 11, 13), (11, 13, 17, 19), (101, 103, 107, 109), (191, 193, 197, 199)$ 是四素数组. 存在无穷多个素数对、三素数组和四素数组的猜想还未被证明.

6. 梅森素数

如果 $2^{k} - 1, k \in N$ 是素数,那么 $k$ 也是素数. 数 $2^{p} - 1$ ( $p$ 是素数) 称作梅森 (Mersenne) 数. 一个本身是素数的梅森数 $2^{p} - 1$ 称作梅森素数.

对于下列最初几个 $p$ 的值:2,3,5,7,13,17,19,31,61,89,107,等等, $2^{p} - 1$ 是素数.

注近几年来最大的已知素数总是梅森素数,例如 $2^{43112609} - 1 (2008 年)$ , $2^{57885161} - 1 (2013)$ 年). 与此相反,对于其他自然数形式为 $2^{k} - 1$ 的数可以用相对简单的方式检验它们是素数: 设 $p > 2$ 是一个素数,定义自然数列 $s_{1} = 4, s_{i + 1} :=$ $s_{i}^{2} - 2 (i \geq 1)$ . 数 $2^{p} - 1$ 是素数,当且仅当数列的项 $s_{p - 1}$ 可被 $2^{p} - 1$ 整除.

基于这个命题的素数判别法称为卢卡斯-莱默 (Lucas-Lehmer) 判别法.

7. 费马素数

如果数 $2^{k} + 1, k \in N$ 是一个奇素数,那么 $k$ 是 2 的幂. 数 $2^{k} + 1, k \in N$ 称为费马数. 如果一个费马数是素数, 那么它称作费马素数.

当 $k = 0, 1, 2, 3, 4$ 时对应的费马数3,5,17,257,65537是素数. 人们猜测没有其他的费马素数.

8. 初等数论基本定理

每个正整数 $n > 1$ 可以表示为素数的乘积. 这种表示除因子次序外是唯一的. 因此称 $n$ 恰有一个素因子分解式.

$360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5 = 2^{3} \cdot 3^{2} \cdot 5.$

注类似地, 整数 (除 -1,0,1 ) 可表示为素元素之积, 除因子的次序和符号外表示是唯一的.

9. 标准素因子分解

正整数的素因子分解式中因子通常按它们的大小排列, 并且相同的因子组成幂. 如果规定不出现的素数的指数为 0 , 那么每个正整数由它的素因子分解式的指数序列唯一确定.

属于 $1533312 = 2^{7} \cdot 3^{2} \cdot 11^{3}$ 的指数序列是 $(7, 2, 0, 0, 3, 0, 0, \dots)$ .

对于正整数 $n$ ,设 $p_{1}, p_{2}, \dots, p_{m}$ 是 $n$ 的两两不同的素因子,还设 $α_{k}$ 表示 $n$ 的素因子分解式中素数 $p_{k}$ 的指数. 那么

\begin{matrix} (5.227a) & n = \prod_{k = 1}^{m} p_{k}^{α_{k}}, \end{matrix}

并且这个表示称为 $n$ 的标准素因子分解. 它常记作

\begin{matrix} (5.227b) & n = \prod_{p} p^{ν_{p} (n)}, \end{matrix}

其中乘积应用于所有素数 $p$ ,并且 $ν_{p} (n)$ 是 $p$ 作为 $n$ 的因子的重数. 它总是表示有限积,因为只有有限多个指数 $ν_{p} (n)$ 异于 0 .

10. 正因子

如果正整数 $n \geq 1$ 由它的标准素因子分解 (5.227a) 给出,那么 $n$ 的每个正因子 $t$ 可写成形式

\begin{matrix} (5.228a) & t = \prod_{k = 1}^{m} p_{k}^{τ_{k}}, τ_{k} \in {0, 1, 2, \dots, α_{k}}, k = 1, 2, \dots, n . \end{matrix}

$n$ 的所有正因子的个数 $τ (n)$ 是

\begin{matrix} (5.228b) & τ (n) = \prod_{k = 1}^{m} (α_{k} + 1) . \end{matrix}

$◼ A$ : $τ (5040) = τ (2^{4} \cdot 3^{2} \cdot 5 \cdot 7) = (4 + 1) (2 + 1) (1 + 1) (1 + 1) = 60$ .

$◼ B$ : 如果 $p_{1}, p_{2}, \dots, p_{r}$ 是两两不同的素数,那么 $τ (p_{1} p_{2} \dots p_{r}) = 2^{r}$ .

$n$ 的所有正因子之积 $P (n)$ 由

\begin{matrix} (5.228c) & P (n) = n^{\frac{1}{2} τ (n)} \end{matrix}

给出.

$◼ A$ : $P (20) = 20^{3} = 8000$ .

$◼ B$ : 如果 $p$ 为素数,那么 $P (p^{3}) = p^{6}$ .

$◼ C$ : 如果 $p, q$ 是不同的素数,那么 $P (p q) = p^{2} q^{2}$ .

$n$ 的所有正因子之和 $σ (n)$ 是

\begin{matrix} (5.228d) & σ (n) = \prod_{k = 1}^{m} \frac{p_{k}^{α_{k} + 1} - 1}{p_{k} - 1} . \end{matrix}

$◼ A$ : $σ (120) = σ (2^{3} \cdot 3 \cdot 5) = 15 \cdot 4 \cdot 6 = 360$ .

$◼ B$ : 如果 $p$ 为素数,那么 $σ (p) = p + 1$ .

5.4.1.3 整除性判别法

1. 记号

考虑一个用十进制形式给出的正整数:

\begin{matrix} (5.229a) & n = {(a_{k} a_{k - 1} \dots a_{2} a_{1} a_{0})}_{10} = a_{k} 10^{k} + a_{k - 1} 10^{k - 1} + \dots + a_{2} 10^{2} + a_{1} 10 + a_{0} \end{matrix}

那么

\begin{matrix} (5.229b) & Q_{1} (n) = a_{0} + a_{1} + a_{2} + \dots + a_{k} \end{matrix}

和

\begin{matrix} (5.229c) & Q_{1}^{'} (n) = a_{0} - a_{1} + a_{2} - + \dots + {(- 1)}^{k} a_{k} \end{matrix}

分别称为 $n$ 的(一阶) 数字和以及(一阶) 数字交错和. 还有,

\begin{matrix} (5.229d) & Q_{2} (n) = {(a_{1} a_{0})}_{10} + {(a_{3} a_{2})}_{10} + {(a_{5} a_{4})}_{10} + \dots, \end{matrix}

和

\begin{matrix} (5.229e) & Q_{2}^{'} (n) = {(a_{1} a_{0})}_{10} - {(a_{3} a_{2})}_{10} + {(a_{5} a_{4})}_{10} - + \dots \end{matrix}

分别称为(二阶) 数字和以及(二阶) 数字交错和, 以及

\begin{matrix} (5.229f) & Q_{3} (n) = {(a_{2} a_{1} a_{0})}_{10} + {(a_{5} a_{4} a_{3})}_{10} + {(a_{8} a_{7} a_{6})}_{10} + \dots \end{matrix}

和

\begin{matrix} (5.229g) & Q_{2}^{'} (n) = {(a_{2} a_{1} a_{0})}_{10} - {(a_{5} a_{4} a_{3})}_{10} + {(a_{8} a_{7} a_{6})}_{10} - + \dots \end{matrix}

分别称为(三阶) 数字和以及(三阶) 数字交错和.

数1,2,3,4,5,6,7,8,9有下列数字和: $Q_{1} = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 =$ $45, Q_{1}^{'} = 9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5, Q_{2} = 89 + 67 + 45 + 23 + 1 = 225, Q_{2}^{'} =$ $89 - 67 + 45 - 23 + 1 = 45, Q_{3} = 789 + 456 + 123 = 1368, Q_{3}^{'} = 789 - 456 + 123 = 456$ .

2. 整除性判别法

有下列整除性判别法:

DC-1: $3 ∣ n \Leftrightarrow 3 ∣ Q_{1} (n)$ ,(5.230a)

DC-2: $7 ∣ n \Leftrightarrow 7 ∣ Q_{3}^{'} (n)$ ,(5.230b)

DC-3: $9 ∣ n \Leftrightarrow 9 ∣ Q_{1} (n)$ ,(5.230c)

DC-4: $11 ∣ n \Leftrightarrow 11 ∣ Q_{1}^{'} (n)$ ,(5.230d)

DC-5: $13 ∣ n \Leftrightarrow 13 ∣ Q_{3}^{'} (n)$ ,(5.230e)

DC-6: $37 ∣ n \Leftrightarrow 37 ∣ Q_{3} (n)$ ,(5.230f)

DC-7: $101 ∣ n \Leftrightarrow 101 ∣ Q_{2}^{'} (n)$ ,(5.230g)

DC-8: $2 | n \Leftrightarrow 2 | a_{0}$ ,(5.230h)

DC-9: $5 | n \Leftrightarrow 5 | a_{0}$ ,(5.230i)

DC-10: $2^{k} | n \Leftrightarrow 2^{k} | {(a_{k - 1} a_{k - 2} \dots a_{1} a_{0})}_{10}$ ,(5.230j)

DC-11: $5^{k} ∣ n \Leftrightarrow 5^{k} ∣ {(a_{k - 1} a_{k - 2} \dots a_{1} a_{0})}_{10}$ .(5.230k)

$A : a = 123456789$ 被 9 整除,因为 $Q_{1} (a) = 45$ ,并且 $9 ∣ 45$ ,但不被 7 整除, 因为 $Q_{3}^{'} (a) = 456$ ,并且 $7 ∤ 456$ .

$◼ B$ : 11 整除 91619,因为 $Q_{1}^{'} (91619) = 22$ ,并且 11|22.

$◼ C$ : $2^{4}$ 整除 99994096,因为 $2^{4} ∣ 4096$ .

5.4.1.4 最大公因子和最小公倍数

1. 最大公因子

对于不全为零的整数 $a_{1}, a_{2}, \dots, a_{n}$ ,将 $a_{1}, a_{2}, \dots, a_{n}$ 的公因子的集合中最大的数称作 $a_{1}, a_{2}, \dots, a_{n}$ 的最大公因子,并将它记作 $gcd (a_{1}, a_{2}, \dots, a_{n})$ . 如果 $gcd (a_{1}, a_{2}, \dots, a_{n}) = 1$ ,那么称数 $a_{1}, a_{2}, \dots, a_{n}$ 互素.

为确定最大公因子,只需考虑正的公因子. 如果给定 $a_{1}, a_{2}, \dots, a_{n}$ 的标准素因子分解

\begin{matrix} (5.231a) & a_{i} = \prod_{p} p^{ν_{p} (a_{i})}, \end{matrix}

那么

\begin{matrix} (5.231b) & gcd (a_{1}, a_{2}, \dots, a_{n}) = \prod_{p} p^{min_{i} (ν_{p} (a_{i}))} . \end{matrix}

对于数 $a_{1} = 15400 = 2^{3} \cdot 5^{2} \cdot 7 \cdot 11, a_{2} = 7875 = 3^{2} \cdot 5^{3} \cdot 7, a_{3} = 3850 = 2 \cdot 5^{2} \cdot 7 \cdot 11$ , 最大公因子是 $gcd (a_{1}, a_{2}, a_{3}) = 5^{2} \cdot 7 = 175$ .

2. 欧几里得算法

两个整数 $a, b$ 的最大公因子可以不用它们的素因子分解,而是用欧几里得算法确定. 为此,依据下列格式完成一系列带余除法. 对于 $a > b$ ,令 $a_{0} = a, a_{1} = b$ . 那么

a_{0} = q_{1} a_{1} + a_{2}, 0 < a_{2} < a_{1} .

a_{1} = q_{2} a_{2} + a_{3}, 0 < a_{3} < a_{2} .

(5.232a)

a_{n - 2} = q_{n - 1} a_{n - 1} + a_{n}, 0 < a_{n} < a_{n - 1},

a_{n - 1} = q_{n} a_{n} .

因为数列 $a_{2}, a_{3}, \dots$ 是严格单调减少的正整数列,所以除法算法有限步后停止. 最后不等于 0 的余数 $a_{n}$ 就是 $a_{0}$ 和 $a_{1}$ 的最大公因子.

借助下面的表可见 $gcd (38, 105) = 1$ :

105 = 2 \cdot 38 + 29,

38 = 1 \cdot 29 + 9,

29 = 3 \cdot 9 + 2,

9 = 4 \cdot 2 + 1

2 = 2 \cdot 1 .

由递推公式

\begin{matrix} (5.232b) & gcd (a_{1}, a_{2}, \dots, a_{n}) = gcd (gcd (a_{1}, a_{2}, \dots, a_{n - 1}), a_{n}) \end{matrix}

可见 $n$ 个正整数 $(n > 2)$ 的最大公因子可以通过重复应用欧几里得算法确定.

$gcd (150, 105, 56) = gcd (gcd (150, 105), 56) = gcd (15, 56) = 1$ .

如果两个数是斐波那契 (Fibonacci) 数列 (参见第 501 页 5.4.1.5) 中的相邻数, 那么确定这两个数的 gcd 的欧几里得算法 (还可参见第 3 页 1.1.1.4, 1.) 有特别多的步骤. 下面附加的计算给出一个例子, 其中所有的商始终等于 1 .

55 = 1 \cdot 34 + 21,

34 = 1 \cdot 21 + 13,

21 = 1 \cdot 13 + 8,

13 = 1 \cdot 8 + 5,

8 = 1 \cdot 5 + 3,

5 = 1 \cdot 3 + 2,

3 = 1 \cdot 2 + 1,

2 = 1 \cdot 1 + 1

1 = 1 \cdot 1 .

3. 欧几里得算法定理

对于两个自然数 $a, b, a > b > 0$ ,令 $λ (a, b)$ 表示欧几里得算法中带余除法的次数,并设 $κ (b)$ 是 $b$ 的十进表示中数字个数. 那么

\begin{matrix} (5.233) & λ (a, b) \leq 5 \cdot κ (b) . \end{matrix}

4. 作为线性组合的最大公因子

从欧几里得算法可以得到

a_{2} = a_{0} - q_{1} a_{1} = c_{0} a_{0} + d_{0} a_{1},

\begin{matrix} (5.234a) & a_{3} = a_{1} - q_{2} a_{2} = c_{1} a_{0} + d_{1} a_{1}, \end{matrix}

......

a_{n} = a_{n - 2} - q_{n - 1} a_{n - 1} = c_{n - 2} a_{0} + d_{n - 2} a_{1} .

这里 $c_{n - 2}$ 和 $d_{n - 2}$ 是整数. 于是 $gcd (a_{0}, a_{1})$ 可以表示为 $a_{0}$ 和 $a_{1}$ 的整系数线性组合:

\begin{matrix} (5.234b) & gcd (a_{0}, a_{1}) = c_{n - 2} a_{0} + d_{n - 2} a_{1} . \end{matrix}

此外, $gcd (a_{1}, a_{2}, \dots, a_{n})$ 可以表示为 $a_{1}, a_{2}, \dots, a_{n}$ 的线性组合,因为

gcd (a_{1}, a_{2}, \dots, a_{n}) = gcd (gcd (a_{1}, a_{2}, \dots, a_{n - 1}), a_{n})

\begin{matrix} (5.234c) & = c \cdot gcd (a_{1}, a_{2}, \dots, a_{n - 1}) + d a_{n} . \end{matrix}

$gcd (150, 105, 56) = gcd (gcd (150, 105), 56) = gcd (15, 56) = 1$ ,并且 $15 = (- 2)$ . $150 + 3 \cdot 105$ ,以及 $1 = 15 \cdot 15 + (- 4) \cdot 56$ ,于是 $gcd (150, 105, 56) = (- 30) \cdot 150 +$ $45 \cdot 105 + (- 4) \cdot 56$ .

5. 最小公倍数

对于全不为零的整数 $a_{1}, a_{2}, \dots, a_{n}$ ,将 $a_{1}, a_{2}, \dots, a_{n}$ 的正公倍数的集合中最小的数称作 $a_{1}, a_{2}, \dots, a_{n}$ 的最小公倍数,并将它记作 $lcm (a_{1}, a_{2}, \dots, a_{n})$ .

如果给定 $a_{1}, a_{2}, \dots, a_{n}$ 的标准素因子分解式 (5.231a),那么

\begin{matrix} (5.235) & lcm (a_{1}, a_{2}, \dots, a_{n}) = \prod_{p} p^{max_{i} (ν_{p} (a_{i}))} . \end{matrix}

对于数 $a_{1} = 15400 = 2^{3} \cdot 5^{2} \cdot 7 \cdot 11, a_{2} = 7875 = 3^{2} \cdot 5^{3} \cdot 7, a_{3} = 3850 = 2 \cdot 5^{2} \cdot 7 \cdot 11$ , 最小公倍数是 $lcm (a_{1}, a_{2}, a_{3}) = 2^{3} \cdot 3^{2} \cdot 5^{3} \cdot 7 \cdot 11 = 693000$ .

6. $\gcd$ 与 $lcm$ 间的关系

对于任意整数 $a, b$ :

\begin{matrix} (5.236) & | a b | = gcd (a, b) \cdot lcm (a, b) . \end{matrix}

因此, $lcm (a, b)$ 可以借助欧几里得算法而不应用素因子分解确定.

5.4.1.5 斐波那契数

1. 递推公式

序列

\begin{matrix} (5.237) & {(F_{n})}_{n \in N}, F_{1} = F_{2} = 1, F_{n + 1} = F_{n} + F_{n + 1} \end{matrix}

称为斐波那契数列. 它开头的元素是1,1,2,3,5,8,13,21,34,55,89,144,233,377,

这个数列的研究要回溯到斐波那契于 1202 年提出的一个问题: 如果每对兔子每月生育一对新兔子, 并且从第二个月开始生育后代, 那么一对兔子在年末总共繁殖多少对兔子? 答案是 $F_{14} = 377$ .

2. 明显公式

除递推定义 (5.237) 外, 有一个斐波那契数的明显公式:

\begin{matrix} (5.238) & F_{n} = \frac{1}{\sqrt{5}} ({[\frac{1 + \sqrt{5}}{2}]}^{n} - {[\frac{1 - \sqrt{5}}{2}]}^{n}) . \end{matrix}

斐波那契数的一些重要性质如下. 对于 $m, n \in N$ :

(1) $F_{m + n} = F_{m - 1} F_{n} + F_{m} F_{n + 1} (m > 1)$ .(5.239a)

(2) $F_{m} ∣ F_{m n}$ .(5.239b)

(3) $gcd (m, n) = d$ 蕴涵 $gcd (F_{m}, F_{n}) = F_{d}$ .(5.239c)

(4) $gcd (F_{n}, F_{n + 1}) = 1$ .(5.239d)

(5) 当且仅当 $m ∣ k$ 时, $F_{m} ∣ F_{k}$ .(5.239e)

(6) $\sum_{i = 1}^{n} F_{i}^{2} = F_{n} F_{n + 1}$ .(5.239f)

(7) $gcd (m, n) = 1$ 蕴涵 $F_{m} F_{n} ∣ F_{m n}$ .(5.239g)

(8) $\sum_{i = 1}^{n} F_{i} = F_{n + 2} - 1$ .(5.239h)

(9) $F_{n} F_{n + 2} - F_{n + 1}^{2} = {(- 1)}^{n + 1}$ .(5.239i)

(10) $F_{n}^{2} + F_{n + 1}^{2} = F_{2 n + 1}$ .(5.239j)

(11) $F_{n + 2}^{2} - F_{n}^{2} = F_{2 n + 2}$ .(5.239k)

5.4.1 整除性 ​

5.4.1.1 整除性和基本整除法则 ​

1. 因子 ​

2. 基本整除法则 ​

5.4.1.2 素数 ​

1. 素数的定义和性质 ​

2. 埃拉托色尼 (Eratosthenes) 筛法 ​

3. 素数对 ​

4. 三素数组 ​

5. 四素数组 ​

6. 梅森素数 ​

7. 费马素数 ​

8. 初等数论基本定理 ​

9. 标准素因子分解 ​

10. 正因子 ​

5.4.1.3 整除性判别法 ​

1. 记号 ​

2. 整除性判别法 ​

5.4.1.4 最大公因子和最小公倍数 ​

1. 最大公因子 ​