4质数算术基本定理

1、4 质数算术基本定理一、教学目标：通过本节内容的学习，达到以下教学目标与要求： 一级目标：掌握算术基本定理；二级目标：掌握质数和合数的概念。二、教学内容和重、难点：1. 质数和合数2. 算术基本定理3标准分解式重点：算术基本定理难点：算术基本定理的证明三、教学方法和教具使用：讲授法。四、教学过程：定义 如果一个大于1的整数的正因数只有 1和它本身，那么就把这个整数叫做质数否则就叫合数定理1设a是任何一个大于1的整数，贝U a的除1以外的最小正因数 q是质数，且当a 是合数时，证 假设q不是质数，由质数的定义得，q除1和它本身外还有一个正因数q1，因而1 ： q： q .但q | a，故q |

2、a，这与q是a的最小正因数矛盾故q是质数当 a是合数时， a ncq,且 1- a1，故 anaQ _q2,q 一 . a.定理2若p是一质数，a为任一整数，则 p| a或p,a=1.证因 p,a | p , p为质数，故 p,a = 1或 p,a二p.而当 p, a =1时，p | a,故p,a =1 或 p|a.推论 2/ 设 a,a2,IH,an 是n个整数，p是质数.若p | a1al an，则p整除某个ak.证若 p/ aj =1,2,|H，n，则 p,a =1,i=1,2|,n于是 卩,时2|咼=1，这与PlaiaJHan矛盾.定理3（算术基本定理）任意大于1的整数都能表示成质数的

3、乘积，即对任一整数a 1 ,有a 二 Pi P2 |Pn，Pi 乞 P2 -|1| - Pn（ 1）其中5，卩2,川，Pn是质数，并且若a川qm,q “2川-qm（2）其中qq,川,qm是质数，则m=n, q = P,i =1,2川1, n.证首先用数学归纳法证明（1）式成立.当a = 2时，显然（1）式成立.假设对于一切小于a的正整数（1）式成立.下面根据此归纳假推出（1）式对正整数a也成立.当a为质数时，显然（1）式成立.当a为合数时，存在两个正整数 b,c满足条件由归纳假设，b和c都分别能表示为质数的乘积，故a能表示成质数的乘积，即（1）式成立.其次，证明表示的唯一性.若对a同时有（1

4、），（2）两式成立，则P1P2 HlPn =qq2lliqm（ 3）由定理3知，分别有质数Pk,qj使得p1 |qj, cn | Pk.但qj, pk都是质数，故p =qj,q =Pk.又Pk - P1，qj -q，故同时有 q -山和P1 -q,因而q = 由（3）式得P2 HlPn =qJUqn.同理可得q2二P2,q3 = P3H,依此类推下去，最后得 m = nq = Pn.推论3.1任意一个大于1的整数a都能唯一地表为a 二 Pi：1P2 HlPk k/ i 0,i =1,2，山,k（4）其中Pi ： Pj i j是质数.（4）叫做a的标准分解式.推论3.2设a是一个大于1的整数，且

5、则a的正因数d可以表示为d 二Pi 0 2 lHp，：i 一 匚0,i =1,2jll,k.（5）且当正整数d可以由上式表示时，d为a的正因数.证设d为a的一个正因数，则当d =1时，d可以表示为d = 口0 p2丨丨I pk .当d 1时，因d|a,故d的质因数必为a的质因数.而p/1p/MHpk：k,ai 0,1,2jll,k,从 而d可以表示为下面证明? _ ai ,i =1,2,川,k.因 p|d,d|a，故 Pi 1 1 a.但因 a = pp?：2 川 pk ,故 p | “乜川 pk .而 （pP, pHlPi严Pi严川 Pk ）=1，故 pP I pa, Pjp 兰岸,0 i“

6、 i,i= 1,2，H ,k故 a 的每个正因数d都可以由（5）表示出来.反之，当正整数d可以由（5）式表示出来时，显然 d为a的一个正因数.附记 如把推论2中的条件“ ai 0,i =1,2川|,k ”改为“ a 2 0,i =1,2，川，k ”，结论 仍然成立.推论3.3设a,b是任意两个正整数，且a 二 口乜：2 |“Pk：k,： i -0,i =1,2|,k,Pi1P2MHPk k, 0,i ,2,川,k,则a,b = P11 P2Pkk,a,b 1二 pjpJh Pkk,）其中 i 二 min : ,、i 二 max : ,i =1,2,|）,k.证 由（6）式易知p11 p2| p

7、k k为a,b的一个公因数，pj1 p22111 pkk为a, b的一个公倍数（其中 i =min 冷，=max 冷，i=1,2,i|l,k）.设d为a,b的任意一个正公因数，则由推论2及其附记得，d可以表示为其中0乞弓乞:i,0 - ： 1=1,2,|l,k.故0乞弓乞i,i =1,2,III,k.于是d乞口 1 p2 2川Pk k.于是，P1 1P2 I Pk k为a,b的最大公因数.设m为a, b的任意一个正的公倍数，则a | m,b | m.因pF | a, Pi T a,i =1,2,|,k，故pi L |m,i =1,2,ll）,k.但 p/, p2 2,川,pk k 两两互质，故

8、P11 P2 l|pk k| m, P1 1 p2 Mllpk m.于是 pp2IPkk 为 a,b的最小公倍数. 故（7）式成立.根据定理1，可以构造质数表.下面构造50以内的质数表，当然，需要知道不超过50的所有质数2,3,5,7.不超过 50的所有质数为2,3,5,7.把不超过50的所有正整数，首先划去1.保留2,3,5,7.除2,3,5,7夕卜，把2,3,5,7中每一个数的其他倍数都划去：没有被划过的数就是不超过50的全部质数.由此可知，不超过 50的所有质数为 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.定理4质数的个数是无穷的.证 如果质数的个

9、数是有限的，可以设共有k个质数，p1, p2|,pk是全体实数.令p = p1P2|pk 1，因P 1，故P有质因数，设 p为P的一个质因数，因所有的质数为 Pi,P2,IH,Pk，故P为其中的某一个，设p = Pj1 ik ，则由p| P得，P | P1P2“|Pk +1, P |1，矛盾习题解答1. 试构造不超过100的质数表解 不超过、100=：10的所有质数为2,3,5,7.写出不超过100的所有正整数，首先划去1.保留2,3,5,7.除2,3,5,7夕卜，把2,3,5,7中每一个数的其他倍数都划去：没有被划过的数就是不超过100的全部质数.2. 求 82 798 848 即 81 0

10、57 226 635 000 的标准分解式.解因为所以，82 798 848的标准分解式为82 798 848 = 28 35 113同理可得81 057 226 635 000的标准分解式为3. 证明推论3.3并推广到n个正整数的情形.推论3.3的推广 设a,a2,lil,an是n个正整数，且a P2 lPk ik,i =1,2,IH,n，（8）其中:j 0,i =1,2, |,n, j =1,2，川,k, P1,P2,lll,Pk为互不相同的质数，则6,a2, Man = P11 P2 MH Pkk,l-a1,a2JI|,aJ - P11P2 Pkk,）其中 j =min ，：宓，nj ,

11、=max “，,川，nj , j =1,2,1 ,k.ai,a2,HI,an的一个公倍数（其中 j =min 仆：，|l|,可，“ =max仆：勺川丨八可, j =12 川,k ）.设d为a1,a2l,ak的任意一个正公因数，则由推论2及其附记得，d可以表示为其中 0乞可j,i =1,2,川,n, j =1,2,川，k.故 0 岂齐乞 j, j =1,2,|,k.于是d乞R/P22川Pkk.于是，Pi1P22ll|Pkk为a,b的最大公因数.设m为a,b的任意一个正的公倍数，则a1 |m, a2 |m|,ak |m.因 Pj：1j |a1,Pj：2j |a2J|, jnj |an,j “,2H

12、,k.故于是 Pi 1 |m,i = 1,2,II）,k.但 p/, P22，川,Pkk 两两互质，故于是P11 p2pk k为a, b的最小公倍数.故（ 9）式成立.4. 应用推论3.3证明 3的定理4 （ii）. 3的定理4（ii）设a,b是任意两个正整数，则 a,b的最小公倍数等于它们的最大公因数除它们的乘积所得的商，即（a,b）证 因为a,b是两个正整数，故可设则由推论3.3得，其中匚二min : i, i , = max :匚，i =1,2j|,k.于是，易知，对任意实数：，： 有 min 二， f maxi*, ：=* ： 于是，i i =min :-, max：i 、, i =1,2,IH,k.故5. 若2n是质数n1，则n