《初等数论教案(7).docx》由会员分享，可在线阅读，更多相关《初等数论教案(7).docx（7页珍藏版）》请在三一文库上搜索。
1、第四节 素数、整数的唯一分解定理第五节 Eratosthenes筛法教学目的：1、掌握素数的一系列性质；2、理解并掌握唯一分解定理.教学重点：素数的性质及唯一分解定理的证明及应用教学难点：唯一分解定理的证明及应用教学课时：4课时教学过程一、素数1、定义1 大于1的整数，如果只有平凡因子，就叫素数，否则叫合数.2、引理1 设a是任意大于1的整数，则a除1以外的最小正因子p是素数，并且当a是合数时，则 .3、引理2 设p是素数，a是任意整数，则或.4、引理3 设p是素数，p|ab , 则p|a或p|b.5、定理1 素数有无穷多个.6、定理2 形如4n-1型的素数有无穷多个.例1 写出不超过100的
2、所有的素数。解 将不超过100的正整数排列如下： 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 92 93 94 95 96 97 98
3、 99 100按以下步骤进行：() 删去1，剩下的后面的第一个数是2，2是素数；() 删去2后面的被2整除的数，剩下的2后面的第一个数是3，3是素数；() 再删去3后面的被3整除的数，剩下的3后面的第一个数是5，5是素数；() 再删去5后面的被5整除的数，剩下的5后面的第一个数是7，7是素数； L L照以上步骤可以依次得到素数2, 3, 5, 7, 11, L.由引理1可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数. 例1中所使用的寻找素数的方法，称为Eratosthenes筛法. 它可以用来求出不超过任何固定整数的所有素数
4、. 在理论上这是可行的；但在实际应用中，这种方法需要大量的计算时间，是不可取的.曾经有人希望找到一个表示素数的方便的公式，例如，是否存在一个不是常数的整系数多项式f(x)，当时，f(x)都表示素数？7、定理3 对于任意给定的整数，不存在整系数多项式，其中 ,使得当时，f(x)都表示素数.二、整数唯一分解定理（算术基本定理）1、引理1 任何大于1的正整数n可以写成素数之积，即n = p1p2Lpm， (1)其中pi（1 £ i £ m）是素数.证明：当n = 2时，结论显然成立.假设对于2 £ n £ k，式(1)成立，我们来证明式(1)对于n = k +
5、 1也成立，从而由归纳法推出式(1)对任何大于1的整数n成立.如果k + 1是素数，式(1)显然成立.如果k + 1是合数，则存在素数p与整数d，使得k + 1 = pd. 由于2 £ d £ k，由归纳假定知存在素数q1, q2, L, ql，使得d = q1q2Lql，从而k + 1 = pq1q2Lql. 证毕2、定理1(算术基本定理) 任何大于1的整数n可以唯一地表示成n =， (2)其中p1, p2, L, pk是素数，p1 < p2 < L < pk，a1, a2, L, ak是正整数.证明 由引理1，任何大于1的整数n可以表示成式(2)的形式
6、，因此，只需证明表示式(2)的唯一性.假设pi（1 £ i £ k）与qj（1 £ j £ l）都是素数，p1 £ p2 £ L £ pk，q1 £ q2 £ L £ ql， (3)并且n = p1p2Lpk = q1q2Lql ， (4)则必有某个qj（1 £ j £ l），使得p1½qj，所以p1 = qj；又有某个pi（1 £ i £ k），使得q1½pi，所以q1 = pi. 于是，由式(3)可知p1 = q1，从而由式(4)得
7、到p2Lpk = q2Lql .重复上述这一过程，得到k = l，pi = qi ，1 £ i £ k . 证毕3、定义1 使用定理1中的记号，称n =是n的标准分解式，其中pi（1 £ i £ k）是素数，p1 < p2 < L < pk，a i（1 £ i £ k）是正整数.推论1 使用式(2)中的记号，有() n的正因数d必有形式d =，giÎZ，0 £ gi £ a i，1 £ i £ k；() n的正倍数m必有形式m =M，MÎN，biÎ
8、N，bi ³ a i，1 £ i £ k.证明：留作习题.推论2 设正整数a与b的标准分解式是 ，其中pi（1 £ i £ k），qi（1 £ i £ l）与ri（1 £ i £ s）是两两不相同的素数，ai，bi（1 £ i £ k），gi（1 £ i £ l）与di（1 £ i £ s）都是非负整数，则(a, b) =， li = minai, di，1 £ i £ k，a, b =，mi = maxai, di，1 &#
9、163; i £ k.证明：留作习题.为了方便，推论2常叙述为下面的形式：推论2 ¢ 设正整数a与b的标准分解式是，其中p1, p2, L, pk 是互不相同的素数，ai，bi（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 =，其中p1, p2, L, pk 是互不相同的素数，gi（1 £ i £ k）是正整数.又设，其中aI，bi（1 £ i &#
10、163; k）都是非负整数. 由式(5)及推论2 ¢可知minai, bi = 0，ai + bi = ngi，1 £ i £ k，因此，对于每个i（1 £ i £ k），等式ai = ngi ，bi = 0与ai = 0，bi = ngi有且只有一个成立.这就证明了推论. 证毕例1 写出51480的标准分解式.解: 我们有51480 = 2×25740 = 22×12870 = 23×6435= 23×5×1287 = 23×5×3×429= 23×5&
11、#215;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是正整数.() 设，其中p1, p2, L, pk是互不相同的素数，ai，bi（1 £ i £ k）都是非负整数.由定理1推论2 ¢，有由此知(a, b)a, b =ab；() 设，其中p1, p2, L, pk是互不相同的素数，ai，bi，gi（1 £ i £ k）都是非负整
12、数.由定理1推论2 ¢，有，其中，对于1 £ i £ k，有li = minai, maxbi, gi，mi = maxminai, bi, minai, gi，不妨设bi £ gi，则minai, bi £ minai, gi，所以mi = minai, gi = li ，即(a, b, c) = (a, b), (a, c).注：利用定理1可以容易地处理许多像例2这样的问题.例3 证明：（n ³ 2）不是整数.解：设3k £ 2n - 1 < 3k + 1. 对于任意的1 £ i £ n，2i - 1 ¹ 3k，记2i - 1 =Qi，QiÎZ，从而知£ k - 1. 因为3k - 1Q1Q2LQ2n - 1是整数，所以，如果N是整数，则存在整数Q，使得3k - 1Q1Q2LQ2n - 1N = Q + 3k - 1Q1Q2LQ2n -1.由于3Q1Q2LQ2n-1，所以上式右端不是整数，这个矛盾说明N不能是整数.三、小结四、作业 25页ex17、ex18、ex22、ex2326页ex32