初等数论教案第四节素数、整数的唯一分解定理

1、第四节素数、整数的唯独分解定理第五节eratosthenes筛法 教学目的： 1、把握素数的一系列性质；2、懂得并把握唯独分解定理.教学重点：素数的性质及唯独分解定理的证明及应用教学难点：唯独分解定理的证明及应用教学课时： 4 课时教学过程一、素数1、定义 1大于 1 的整数，假如只有平凡因子，就叫素数，否就叫合数.2、引理 1设 a 是任意大于 1 的整数，就 a 除 1 以外的最小正因子 p 是素数，并且当a 是合数时，就 pa.3、引理 2设 p 是素数， a 是任意整数，就 p | a 或 p, a1 .4、引理 3设 p 是素数， p|ab , 就 p|a 或 p|b.5、定理 1素

2、数有无穷多个 .6、定理 2形如 4n-1 型的素数有无穷多个 .例 1写出不超过 100 的全部的素数；解将不超过 100 的正整数排列如下：123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100按以下步骤进行： 删去 1，剩下的后面的第一个数是2， 2 是素数； 删

3、去 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筛法.它可以用来求出不超过任何固定整数的全部素数.在理论上这是可行的；但在实际应用中，这

4、种方法需要大量的运算时间，是不行取的.曾经有人期望找到一个表示素数的便利的公式，例如，是否存在一个不是常数的整系数多项式fx，当 xx0 时， fx都表示素数？7、定理 3对于任意给定的整数x0 ，不存在整系数多项式f xnia i xi 0，其中an0, n0,使得当 xx0 时， fx都表示素数 .二、整数唯独分解定理（算术基本定理）1、引理 1任何大于 1 的正整数 n 可以写成素数之积，即n = p1p2pm，1其中 pi（1im）是素数 .证明：当 n = 2 时，结论明显成立 .假设对于 2nk，式1成立， 我们来证明式 1对于 n = k1 也成立，从而由归纳法推出式1对任何大于

5、 1 的整数 n 成立.假如 k1 是素数，式 1明显成立 .假如 k1 是合数， 就存在素数 p 与整数 d，使得 k1 = pd.由于2dk，由归纳假定知存在素数q1, q2, ql，使得 d = q1q2ql ，从而 k1 = pq1q2ql.证毕2、定理 1算术基本定理 任何大于 1 的整数 n 可以唯独地表示成1p2pkkn = p12，2其中 p1, p2, pk 是素数， p1 < p2 << pk，1,2,k 是正整数 .证明由引理 1，任何大于 1 的整数 n 可以表示成式 2的形式，因此，只需证明表示式2的唯独性 .假设 pi（ 1ik）与 qj（ 1jl

6、）都是素数，p1p2pk，q1q2ql，3并且n = p1p2pk = q1q2ql ，4就必有某个 qj（ 1jl），使得 p1qj，所以 p1 = qj；又有某个 pi（ 1 ik），使得 q1pi，所以 q1 = pi.于是，由式 3可知 p1 = q1，从而由式4得到p2pk = q2ql .重复上述这一过程，得到k = l，pi = qi ， 1ik .证毕3、定义 1使用定理 1 中的记号，称1p2pkn = p12k是 n 的标准分解式，其中pi （1ik）是素数， p1 < p2 << pk，i（1ik）是正整数 .推论 1使用式 2中的记号，有 n 的正因数

7、 d 必有形式1p2d = p12p， iz ，0ii， 1ik；kkk n 的正倍数 m 必有形式m = p1 1p2 2pk km ， mn， in， ii，1ik.证明：留作习题 .qk1lp1pk1r，s推论 2设正整数 a 与 b 的标准分解式是1ap1pk1ql ， b1kr1s其中 pi（1ik）， qi（1il）与 ri（ 1is）是两两不相同的素数，i ， i（ 1ik）， i（ 1il）与 i （1is）都是非负整数，p1p，k就a, b =1ki = mini,i， 1ik，a, b =p1 1pk k q1 1ql lr1 1rs s ， i = maxi,i，1ik.

8、证明：留作习题 .k为了便利，推论2 常表达为下面的形式：推论 2设正整数 a 与 b 的标准分解式是1p2ap12k11pkpp， b12p k ，其中 p1, p2, pk 是互不相同的素数，i， i（ 1ik）都是非负整数，就pp21 a, b11p k ，mini ,i， 1ik，ki.kipp12a, b11p k ，maxi ,i ， 1ik推论 3设 a， b， c， n 是正整数，ab = cn ， a, b = 1，5就存在正整数 u，v，使得a = un，b = vn，c = uv， u, v = 1.证明 :设 c =p1 1 p 21p k k，其中 p1, p2, p

9、k 是互不相同的素数，i（ 1ik）是正整数 .又设1p2ap12p k ， bp 1 p 1kk12p，k其中i ， i（ 1ik）都是非负整数 .由式5及推论 2 可知mini,i = 0，ii = ni，1ik， 因此，对于每个i（1ik），等式i = n i ， i = 0 与i = 0， i = n i有且只有一个成立 .这就证明白推论 .证毕例 1写出 51480 的标准分解式 .解:我们有51480 = 2 25740 = 22 12870 = 23 6435= 23 5 1287 = 23 5 3 429= 23 5 32 143 = 23 32 5 11 13.例 2设 a，

10、b，c 是整数，证明： a, ba, b = ab； a, b, c = a, b, a, c.p，解：为了表达便利，不妨假定a， b， c 是正整数 . 设1p2ap12p k ， bp 1 p 1kk12k其中 p1, p2, pk 是互不相同的素数，i， i （1ik）都是非负整数.由定理 1 推论 2 ，有a, b a, bp1p21111p1p 2p k ，ikkpk ，imin maxi ,i ， 1ik，i ,i ， 1ik；由此知kpia, ba, b =iii 1kmin ipi 1i , i maxi , i kpiii =ab；i 1 设kiapi ， bi 1kkip，

11、ip i ， cii 1i 1其中 p1, p2, pk 是互不相同的素数，i， i， i（ 1ik）都是非负整数.由定理 1 推论 2 ，有 a, b, c 其中，对于 1ik，有kip i ，i 1kp，i a, b, a, cii 1i = mini , maxi,i ，i = maxmini,i, mini,i ，不妨设ii ，就mini,imini,i，所以i = mini,i =i ，即a, b, c = a, b, a, c.注：利用定理 1 可以简单地处理很多像例2 这样的问题 .例 3证明： n1113512n1（ n2）不是整数 .解：设 3k2n1 < 3k + 1.对于任意的 1in， 2i13k，记2i1 =