第四节素数、整数的唯一分解定理第五节Eratosthenes筛法教学目的：1、掌握素数的一系列性质；2、理解并掌握唯一分解定理.教学重点：素数的性质及唯一分解定理的证明及应用教学难点：唯一分解定理的证明及应用教学课时：4 课时教学过程一、素数1 大于1 的整数，如果只有平凡因子，就叫素数，否则1、定义叫合数.1 设a 是任意大于1 的整数，则a 除1 以外的最小正因2、引理子p 是素数，并且当 a 是合数时，则p a .2 设p 是素数，a 是任意整数，则p | a 或( p, a)3、引理 1 .3 设p 是素数，p|ab , 则p|a 或p|b.4、引理1 素数有无穷多个.5、定理2 形如4n-1 型的素数有无穷多个.6、定理例1 写出不超过100 的所有的素数。
解将不超过100 的正整数排列如下：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100按以下步骤进行：(ⅰ)删去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筛法.以用来求出不超过任何固定整数的所有素数. 在理论上这是可行的；但在实际应用中，这种方法需要大量的计算时间，是不可取的.曾经有人希望找到一个表示素数的方便的公式，例如，是否存在一个不是常数的整系数多项式 f(x)，当 x 0 时， f(x)都表示素数？x 7、定理 3 对于任意给定的整数 x 0 ，不存在整系数多项式nia i x ，其中 a n 0, n 0,f (x) i 0使得当 时， f(x)都表示素数 .x x 0 二、整数唯一分解定理（算术基本定理）1、引理 任何大于 1 的正整数 n 可以写成素数之积，即1 p m ， (1)n = p 1p 2 其中 p i （1 m ）是素数 .i 证明：当 n = 2 时，结论显然成立 .假设对于 n k ，式 (1)成立， 我们来证明式 (1)对于 n = k 1 也2 成立，从而由归纳法推出式 (1)对任何大于 1 的整数 n 成立 .如果 1 是素数，式 (1)显然成立 .k 如果 1 是合数， 则存在素数 p 与整数 d ，使得 由于k k 1 = pd. , q l ，使得 d = q 1q 2 q l ，从k ，由归纳假定知存在素数 2 d q 1, q 2, 而 k 1 = pq 1q 2 q l . 证毕2、定理 1(算术基本定理 ) 任何大于 1 的整数 n 可以唯一地表示成1 2kp 1 p 2 p k ， (2)n = 其中 , p k 是素数， p 1 < p k ， k 是正整数 .p 1, p 2, < p 2 < 1, 2, , 证明 由引理 1，任何大于 1 的整数 n 可以表示成式 (2)的形式，因此，只需证明表示式 (2)的唯一性 .假设 p i （ 1 i k ）与 q j （ 1 j l ）都是素数，p k ，q 1 q l ， (3)p 1 p 2 q 2 并且， (4)n = p 1p 2 p k = q 1q 2 q l 则必有某个 q j （ 1 j l ），使得 q j ，所以 p 1 = q j ；又有某个 p i （ 1p 1 p i ，所以 q 1 = q 1，从而由k ），使得 q 1 p i . 于是，由式 (3)可知 p 1 i = 式 (4)得到p 2 = q 2 .p k q l 重复上述这一过程，得到， 1 k = l ，p i = q i i k . 证毕3、定义 1 使用定理 1 中的记号，称p 1 1p 2p k kn = 2 是 n 的标准分解式，其中 p i （1 k ）是素数， < p k ，i p 1 < p 2 < i （1 k ）是正整数 .i 推论 1 使用式 (2)中的记号，有(ⅰ ) n 的正因数 d 必有形式， i ， 1 k ；Z ，0 i d = k1 2 p p p i i 1 2 k (ⅱ ) n 的正倍数 m 必有形式i ，1 M ， M N ， N ， i k.m = p 1 2 k p p i i 1 2 k 证明：留作习题 .推论 2 设正整数 a 与 b 的标准分解式是1 k 1q l ， b l 1 k 1sa p 1 p k q 1 p 1 p k r 1 r s ，其中 p i （1 k ）， q i （1 l ）与 r i （ 1 s ）是两两不相同的素i i i 数， i ， i （ 1 i k ）， i （ 1 l ）与 i （1 i s ）都是非负整数，i 则 (a, b) = p ， }， 1 i k ，= min{ , 1kp i i i 1 k ， i }，1 [a, b] = = max{ i , i k.1 k q 1 l 1 s p p q r r i 1 k 1 l 1 s 证明：留作习题 .为了方便，推论 2 常叙述为下面的形式：推论 2 设正整数 a 与 b 的标准分解式是，1 2k 1 1kp k ， b a p 1 p 2 p 1 p 2 p k 其中 是互不相同的素数， i ， i （ 1 k ）都是非负整p 1, p 2, i , p k 数，则， ， i }， 1 i }， 1 k ，.( a, b) [a, b] p 1 p 2 1 1p k p k kmin{ i , i , i i p 1 p 2 max{ i k 1 1ki 推论 3 设 a ， b ， c ， n 是正整数，ab = c n ， (a, b) = 1， (5)则存在正整数 u ，v ，使得a = u n ，b = v n ，c = uv ， (u, v) = 1.证明 : 设 c = ，其中 是互不相同的素数， p , p , , p 1 1 k p p p 1 2 k i1 2 k （ 1 i k ）是正整数 .又设p k ，1 2k 1 1kp k ， b a p 1 p 2 p 1 p 2 其中 I ， i （ 1 i k ）都是非负整数 . 由式 (5)及推论 2 可知i ，1 i k ，i } = 0， min{ i , = n i i 因此，对于每个 i （1 i k ），等式， = 0 与 = 0， = n = n i i i i i i有且只有一个成立 .这就证明了推论 证毕. 例 1 写出 51480 的标准分解式 .解 : 我们有2 3 51480 = 225740 = 2 12870 = 2 6435= 23 5 1287 = 23 5 3 429= 23 5 32 143 = 23 32 5 11 13.例 2 设 a ，b ，c 是整数，证明：(ⅰ ) (a, b)[a, b] = ab ；(ⅱ ) (a, [b, c]) = [( a, b), (a, c)].解：为了叙述方便，不妨假定 a ， b ， c 是正整数 .(ⅰ ) 设p k ，k k1 2 1 1p k ， b a p 1 p 2 p 1 p 2 其中 , p k 是互不相同的素数， i ， i （1 k ）都是非负整p 1, p 2, i 数 .由定理 1 推论 2 ，有， ， i }， k ，k 。
