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

1、第四节素数、整数的唯一分解定理第五节Eratosthenes筛法教学目的：1、掌握素数的一系列性质；2、理解并掌握唯一分解定理.教学重点：素数的性质及唯一分解定理的证明及应用教学难点：唯一分解定理的证明及应用教学课时：4课时教学过程一、素数1、定义1大于1的整数，如果只有平凡因子，就叫素数，否则叫合数.2、引理1设a是任意大于1的整数，则a除1以外的最小正因子p是素数，弁且当a是合数时，则p於.3、引理2设p是素数，a是任意整数，则p|a或（p,a）1.4、引理3设p是素数，p|ab,贝Up|a或p|b.5、定理1素数有无穷多个.6、定理2形如4n-1型的素数有无穷多个.例1写出不超过100的

2、所有的素数。解将不超过100的正整数排列如下：T23T5-67-8-91011121314151617181920212223242526272829303637383940464748495056575859606667686970767778798086878889900702QDdec313233343541424344455452535455616263646571727374758482838485Ql0202£ldQE2I7JJJJIJJ按以下步骤进行：(i)删去1,剩下的后面的第一个数是2,2是素数；(ii)删去2后面的被2整除的数，剩下的2后面的第一个数是3,3是素数

3、；(iii)再删去3后面的被3整除的数，剩下的3后面的第一个数是5,5是素数；(iv)再删去5后面的被5整除的数，剩下的5后面的第一个数是7,7是素数；照以上步骤可以依次得到素数2,3,5,7,11,.由引理1可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数.例1中所使用的寻找素数的方法，称为Eratosthenes筛法.它可以用来求出不超过任何固定整数的所有素数.在理论上这是可行的；但在实际应用中，这种方法需要大量的计算时间，是不可取的.曾经有人希望找到一个表示素数的方便的公式，例如，是否存在一个不是常数的整系数多项式f(x

4、),当XXo时，f(x)都表示素数？7、定理3对于任意给定的整数Xo,不存在整系数多项式nf(x)aiXi,其中an0,n0,i0使得当XXo时，f(x)都表示素数.二、整数唯一分解定理(算术基本定理)1、引理1任何大于1的正整数n可以写成素数之积，即n=pip2pm,(1)其中Pi(1im)是素数.证明：当n=2时，结论显然成立.假设对于2nk,式(1)成立，我们来证明式(1)对于n=k1也成立，从而由归纳法推出式(1)对任何大于1的整数n成立.如果k1是素数，式(1)显然成立.如果k1是合数，则存在素数p与整数d,使得k1=pd,由于2dk,由归纳假定知存在素数q1,q2,qi,使得d=q

5、1q2qi,从而k1=pq02qi.证毕2、定理1(算术基本定理)任何大于1的整数n可以唯一地表示成n=p11P22pJ,(2)其中p1,p2,pk是素数，p1<p2<<pk,1,2,k是正整数.证明由引理1,任何大于1的整数n可以表示成式(2)的形式，因此，只需证明表示式(2)的唯一性.假设Pi(1ik)与q(1jl)都是素数，PiP2P"qiq2qi,(3)并且n=pip2pk=qiq2qi,(4)则必有某个qj(1jl),使得piq,所以pi=qj；又有某个pi(1ik),使得qipi,所以qi=pi.于是，由式(3)可知pi=qi,从而由式(4)得到p2pk

6、=q2qi.重复上述这一过程，得到k=l,pi=qi,iik.证毕3、定义1使用定理1中的记号，称n=p11P22pkk是n的标准分解式，其中r(iik)是素数，pi<p2V<pk,i(iik)是正整数.推论1使用式(2)中的记号，有(i)n的正因数d必有形式d=p11P22Pkk,iZ,0ii,1ik;(ii)n的正倍数m必有形式m=p11P22pjM,MN,iN,ii,1ik.证明：留作习题.推论2设正整数a与b的标准分解式是八919ki4lK919k”1”sapipkqiql,bpipkrirs,其中Pi(1ik),qi(1il)与ri(1is)是两两不相同的素数，i,i(1

7、ik),i(1il)与i(1is)都是非负整数，则(a,b)=P11pj,i=mini,i,1ik,a,b=P11pjqjqh1个，i=maxi,i,1ik.证明：留作习题.为了方便，推论2常叙述为下面的形式：推论2设正整数a与b的标准分解式是12k11kaPiP2Pk，bPiP2Pk,其中P1,P2,Pk是互不相同的素数，i,i(1ik)都是非负整数，贝U(a,b)Pi1P21Pkk,imini,1ik,.a,bP11P21Pkk,imaxi,1ik推论3设a,b,c,n是正整数，ab=cn,(a,b)=1,(5)则存在正整数u,v,使得a=un,b=vn,c=uv,(u,v)=1.证明：设

8、c=p11P21Pkk,其中P1,P2,Pk是互不相同的素数，i(1ik)是正整数.又设12k11kaPiP2Pk，bPiP2Pk,其中I,i(1ik)都是非负整数.由式(5)及推论2可知mini,i=0,ii=ni,1ik,因此，对于每个i(1ik),等式i=ni,i=0i=0,i=ni有且只有一个成立.这就证明了推论.证毕例1写出51480的标准分解式.解：我们有51480=225740=2212870=236435=2351287=2353429=23532143=233251113.例2设a,b,c是整数，证明：(i)(a,b)a,b=ab;(ii)(a,b,c)=(a,b),(a,c

9、).解：为了叙述方便，不妨假定a,b,c是正整数.(i)设12k11kaP1P2Pk,bP1P2Pk,其中P1,P2,Pk是互不相同的素数，i,i(1ik)都是非负整数.由定理1推论2,有(a,b)P11P21Pkk，a,bP11P21Pkk，imini,i,1ik,imaxi,i,1ik。由此知kkk(a,b)a,b=pjipimini,imaxi,ipiii=ab；i1i1i1(ii)设kaPii，i1kbPii，i1kcPii)i1其中pi,p2,pk是互不相同的素数，i,i,i(1ik)都是非负整数.由定理1推论2,有(a,b,c)pj,(a,b),(a,c)pii1i1其中，对于1ik,有i=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证明：n111，(n2)不是整数.352n1解：设3k2n1<3k+1.对于任意的1in,2i13k,记2i