精品学习资料 精品学习资料
第四节 素数、整数的唯一分解定理
第五节 Eratosthenes筛
法
教学目的： 1、掌握素数的一系列性质； 2、理解并掌握唯一分解定理 .
教学重点：素数的性质及唯一分解定理的证明及应用 教学难点：唯一分解定理的证明及应用 教学课时： 4 课时 教学过程 一、素数
1、定义 1 大于 1 的整数，如果只有平凡因子，就叫素数，否则
叫合数 .
2、引理 1 设
a 是任意大于 1 的整数，则 a 除 1 以外的最小正因 子 p 是素数，并且当 a 是合数时，则 p
a .
3、引理 2 设
p 是素数， a 是任意整数，则 p | a 或 ( p, a) 1 . 4、引理 3 设
p 是素数， p|ab , 则 p|a 或 p|b. 5、定理 1 素数有无穷多个
. 6、定理 2 形如
4n-1 型的素数有无穷多个 . 例 1 写出不超过 100 的所有的素数。 解 将不超过 100 的正整数排列如下：
1
2
3
4
5
6
7
8
9 10
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
欢迎下载 第 1 页，共 7 页
精品学习资料 精品学习资料
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 90 91 92 93 94 95 96 97 98 99 100 按以下步骤进行：
(ⅰ ) 删去 1，剩下的后面的第一个数是 2， 2 是素数；
(ⅱ ) 删去 2 后面的被 2 整除的数，剩下的 2 后面的第一个数是 3，3 是素数；
(ⅲ ) 再删去 3 后面的被 3 整除的数，剩下的 3 后面的第一个数 是 5， 5 是素数；
(ⅳ ) 再删去 5 后面的被 5 整除的数，剩下的 5 后面的第一个数 是 7， 7 是素数；
照以上步骤可以依次得到素数 2, 3, 5, 7, 11, .
由引理 1 可知，不超过 100 的合数必有一个不超过 10 的素约数， 因此在删去 7 后面被 7 整除的数以后， 就得到了不超过 100 的全部素 数 . 例 1 中所使用的寻找素数的方法，称为 Eratosthenes筛
它可 法 .
以用来求出不超过任何固定整数的所有素数 . 在理论上这是可行的； 但在实际应用中，这种方法需要大量的计算时间，是不可取的
.
欢迎下载 第 2 页，共 7 页
精品学习资料 精品学习资料
曾经有人希望找到一个表示素数的方便的公式，例如，是否存在 一个不是常数的整系数多项式 f(x)，当 x x0 时， f(x)都表示素数？
7、定理 3 对于任意给定的整数 x0 ，不存在整系数多项式
n
f (x)
ai
i x
，其中 an 0, n 0,
i 0
使得当 x x0 时， f(x)都表示素数 . 二、整数唯一分解定理（算术基本定理）
1、引理 1 任何大于 1 的正整数 n 可以写成素数之积，即
n = p1p2 pm，
(1)
其中 pi（1 i m）是素数
. 证明：当 n = 2 时，结论显然成立 .
假设对于 2 n k，式 (1)成立， 我们来证明式 (1)对于 n = k 1 也 成立，从而由归纳法推出式 (1)对任何大于 1 的整数 n 成立 .
如果 k 1 是素数，式 (1)显然成立 .
如果 k 1 是合数， 则存在素数 p 与整数 d，使得 k 1 = pd. 由于 2 d k，由归纳假定知存在素数 q1, q2, , ql，使得 d = q1q2 ql ，从
而 k 1 = pq1q2 ql. 证毕
2、定理 1(算术基本定理 ) 任何大于 1 的整数 n 可以唯一地表示 成
n = p1
2
1 p2
pk
k ，
(2)
其中 p1, p2,
, pk 是素数， p1 < p2 < < pk， 1,
2
,
,
k
是正整数 .
证明 由引理 1，任何大于 1 的整数 n 可以表示成式 (2)的形式， 因此，只需证明表示式 (2)的唯一性 .
欢迎下载 第 3 页，共 7 页
精品学习资料 精品学习资料
假设 pi（ 1 i k）与 qj（ 1 j l）都是素数，
p1 p2
pk，q1 q2
ql，
(3)
并且
n = p1p2 pk = q1q2 ql ，
(4)
则必有某个 qj（ 1 j l），使得 p1 qj，所以 p1 = qj；又有某个 pi（ 1 i k），使得 q1 pi，所以 q1 = pi. 于是，由式 (3)可知 p1 = q1，从而由 式 (4)得到
p2 pk = q2 ql .
重复上述这一过程，得到
k = l，pi = qi ，
1 i k. 证毕 3、定义 1 使用定理 1 中的记号，称
n = p1
1
p 2
2
pk
k
是 n 的标准分解式，其中 pi （1 i k）是素数， p1 < p2 <
< pk，
i
（1 i k）是正整数 .
推论 1 使用式 (2)中的记号，有 (ⅰ ) n 的正因数 d 必有形式
d = p 1
2
k
1
p 2
p k
， i Z ，0
i i
， 1 i k；
(ⅱ ) n 的正倍数 m 必有形式
m = p 1 1 p2
2
pk
k
M ， M N， i N， i
i
，1 i k.
证明：留作习题 .
推论 2 设正整数 a 与 b 的标准分解式是
a
p1
k l 1
k 1
1
pk q1
1
ql ， b p1
pk r1
rs
s ，
欢迎下载 第 4 页，共 7 页
精品学习资料 精品学习资料
其中 pi（1 i k）， qi（1 i l）与 ri（ 1 i s）是两两不相同的素 数， i ， i（ 1 i k）， i（ 1 i l）与 i （1 i s）都是非负整数， 则 (a, b) = p1
1
p k
k ，
i
= min{ i, i }，
1 i k， [a, b] = p1
1
p k k
q 1 1
q l l
r 1 1
r s
s
， i = max{ i, i}，1 i k.
证明：留作习题 .
为了方便，推论 2 常叙述为下面的形式： 推论 2
设正整数 a 与 b 的标准分解式是
a
p1 2
1 p2
pk
1 1
k ， b
p1 p2
pk
k
，
其中 p1, p2, , pk 是互不相同的素数，
i
， i（ 1 i k）都是非负整
数，则
( a, b) p1 1
1 p2 pk
k ，
i min{ i , i }， 1 i
k，
[a, b]
p1 1
1 p2
pk k ，
i
max{ i , i }，
1 i k .
推论 3 设 a， b， c， n 是正整数，
ab = cn
，
(a, b) = 1， (5)
则存在正整数 u，v，使得
a = un，b = vn
，c = uv，
(u, v) = 1. 证明 : 设 c = p 1 1
p 2 1
p k k ，其中 p 1 , p ,2 , pk 是互不相同的素数，
i
（ 1 i k）是正整数 .又设
a
p1
2
1 p 2
pk
1 1
k ， b
p1 p2
pk
k
，
其中 I ， i（ 1 i k）都是非负整数 . 由式
(5)及推论 2 可知 min{ i, i} = 0，
i
i
= n i，1 i k，
因此，对于每个 i（1 i k），等式
i
= n i ， i = 0 与 i = 0， i = n i
欢迎下载 第 5 页，共 7 页
精品学习资料 精品学习资料
有且只有一个成立 .这就证明了推论 . 证毕
例 1 写出 51480 的标准分解式 . 解 : 我们有
51480 = 225740 = 2 2
12870 = 2 3
35
= 23
5 1287 = 23 5 3 429 = 23
5 32
143 = 2
3
32
5 11 13.
例 2 设 a，b，c 是整数，证明： (ⅰ ) (a, b)[a, b] = ab； (ⅱ ) (a, [b, c]) = [( a, b), (a, c)].
解：为了叙述方便，不妨假定 a， b， c 是正整数 . (ⅰ ) 设
a
p1
k
1 1
1 p 2
2
pk ， b
p1 p2
pk
k
，
其中 p1, p2,
, pk 是互不相同的素数，
i
， i （1 i k）都是非负整
数 .由定理 1 推论 2 ，有
(a, b) p1
1
1 p 2 pk k ，
i min{ i , i }， 1 i k，
[ a, b] p1 1 p 1
2
pk
k ，
i
max{
i , i }，
1 i k。
由此知
(a, b)[a, b] = k
k
p i i
i , i }
max{
i , i }
k
i
i
p
i
i i =ab；
i 1
i 1
p min{
i 1
(ⅱ ) 设
k k k
a
p i i ， b
p i i ， c
p i
i
，
i 1
i 1
i 1
其中 p1, p2,
, pk 是互不相同的素数， i， i， i（
1 i k）都是非负 整数 .由定理 1 推论 2 ，有
欢迎下载 第 6 页，共 7 页
精品学习资料 精品学习资料
k
k
( a, [b, c])
p i
i i ， [( a, b), (a, c)]
p i
，
i 1
i 1
其中，对于 1 i k，有
i
= min{ i, max{ i, i}}，
i
= max{min{ i, i}, min{ i, i}}，
不妨设
i i
，则
min{ i, i} min{ i, i}，
所以
i
= min{ i, i} =
i
，
即 (a, [b, c]) = [( a, b), (a, c)].
注：利用定理 1 可以容易地处理许多像例 2 这样的问题 . 例 3 证明： N
1
1 1 1 3 5
2n 1
（ n 2）不是整数 .
解：设 3k 2n 1 < 3
k + 1
. 对于任意的 1 i n， 2i 1 3k
，记
2i 1 = 3 i
Qi，
Qi Z， 从而知
i
k 1. 因为 3
k 1
Q Q1 2
Q2n 1
是整数，所以，如果 N 是整
数，则存在整数 Q，使得
3k 1
Q Q1 2 Q 2n 1N = Q 3k 1Q 1 Q2 Q2n 1
1 3
k
.
由于 3 | Q1Q2 Q2n 1，所以上式右端不是整数，这个矛盾说明 N 不能
是整数 . 三、小结
四、作业 25 页 ex17、 ex18、 ex22、ex23
26 页 ex32
欢迎下载 第 7 页，共 7 页
