初等数论第一章整除14

**数论的基本内容按照研究方法的不同，数论可分为初等数论解析数论代数数论几何数论**参考书目1、南基洙主编《初等数论》；2、柯召、孙琦编著《数论讲义》，高等教育出版社；3、闵嗣鹤、严士健编《初等数论》，高等教育出版社；4、郑克明主编《初等数论》，西南师范大学出版社。**初等数论第一章整除§1自然数与整数**归纳原理设S是N的一个子集，满足条件：(ⅰ)1∈S;(ⅱ)如果n∈S，则n+1∈S,那么，S=N.**定理1 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 归纳法设P(n)是关于自然数n的一种性质或命题.如果(ⅰ)当n=1时，P(1)成立；(ⅱ)由P(n)成立必可推出P(n+1)成立，那么，P(n)对所有自然数n成立.**定理2最小自然数原理设T是N的一个非空子集.那么，必有t0∈T,使对任意的t∈T有t0≤t，即t0是T中的最小自然数.**定理3最大自然数原理设M是N的非空子集.若M有上界，即存在a∈N,使对任意的m∈M有m≤a,那么必有m0∈M，使对任意的m∈M有m≤m0，即m0是M中的最大自然数。**定理4第二数学归纳法设P(n)是关于自然数n的一种性质或命题.如果(ⅰ)当n=1时，P(1)成立；(ⅱ)设n>1.若对所有的自然数m<n,P(m)成立，则必可推出P(n)成立，那么,P(n)对所有自然数n成立.**定理5鸽巢原理设n是一个自然数.现有n个盒子和n+1个物体.无论怎样把这n+1个物体放入这n个盒子中，一定有一个盒子中被放了两个或两个以上的物体。**§2整除**定义1设a，b是整数，a0，如果存在整数q，使得b=aq，则称b可被a整除，记作ab，且称b是a的倍数，a是b的约数(因数、除数)；如果不存在整数q使得b=aq成立，则称b不被a整除，记为ab。被2整除的数称为偶数，不被2整除的称为奇数**定理1下面的结论成立：(ⅰ)a|b(-a)|ba|(-b)(-a)|(-b)|a|||b|；(ⅱ)ab，bcac；(ⅲ)ab,ac对任意x、y,有abx+cy,一般地，abi，i=1,2,,kab1x1b2x2bkxk，此处xi（i=1,2,,k）是任意的整数；(ⅳ)abacbc，c是任意的非零整数；(ⅴ)ab且baa=b；(ⅵ)ab，b0|a|≤|b|；ab且|b|<|a|b=0.**例1 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 ：若3|n且7|n，则21|n.例2设a=2t-1.若a|2n,则a|n.例3设a、b是两个给定的非零整数，且有整数x、y，使得ax+by=1.证明：若a|n且b|n,则ab|n.例4设f(x)=anxn+an-1xn-1++a1x+a0∈Z[x],其中Z[x] 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示全体一元整系数多项式组成的集合.若d|b-c,则d|f(b)-f(c).**定义2显然每个非零整数a都有约数1，a，称这四个数为a的显然因数，a的另外的因数称为非显然因数。若整数a0，1，并且只有约数1和a，则称a是素数（或质数）；否则称a为合数。以后在本书中若无特别说明，素数总是指正素数。**定理2设A={d1,d2,,dk}是n的所有约数的集合，则B=也是n的所有约数的集合。解由以下三点理由可以证得结论：(ⅰ)A和B的元素个数相同；(ⅱ)若diA，即din，则n，反之亦然；(ⅲ)若didj，则.**定理3(ⅰ)a>1是合数的充要条件是a=de,1<d<a,1<e<a;(ⅱ)若d>1,q是不可约数且d|q,则d=q.定理4若a是合数，则必有不可约数p|a.**定理5设整数a≥2,那么a一定可表为素数的乘积(包括a本身是素数)，即a=p1p2ps其中pj（1≤j≤s)是素数.证明当a=2时，结论显然成立。假设对于2≤a≤k，式(1)成立，我们来证明式(1)对于a=k1也成立，若k1是素数，式(1)显成立.如果k1是合数，则存在素数p与整数d，使得k1=pd.由于2≤d≤k，由归纳假定知存在素数q1,q2,,ql，使得d=q1q2ql，从而k1=pq1q2ql.从而由归纳法推出式(1)对任何大于1的整数a成立。证毕。**推论任何大于1的合数a必有一个不超过a1/2的素因数。证明由于a是合数，故存在整数b和c使a＝bc,其中:1<b<a,1<c<a.若b和c均大于a1/2,则a＝bc＞a1/2·a1/2＝a,这是不可能的.因此b和c中必有一个小于或等于a1/2.**例5写出不超过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,.由定理2推论可知，不超过100的合数必有一个不超过10的素约数，因此在删去7后面被7整除的数以后，就得到了不超过100的全部素数.**在例5中所使用的寻找素数的方法,称为Eratosthenes筛法.它可以用来求出不超过任何固定整数的所有素数.在理论上这是可行的；但在实际应用中，这种列出素数的方法需要大量的计算时间，是不可取的.**定理7.(Euclid)素数有无穷多个.证明：(反证法)假设素数是有限多个,共有n个,令它们是p1,p2,…,pn,并令a=p1p2…pn+1.若a是素数,则因a≠pi，其中1<i<n,故素数个数最少是n+1个,这与假设素数个数为n个矛盾.若a不是素数,则由定理4知,a的大于1的最小因数b是素数.由于pi|p1p2…pn,但pi不能整除1,故pi不能整除a,因此b≠pi,其中1≤i≤n,那么a也为素数.所以在p1,p2,…,pn,还有素数,这也与已知共有n个素数矛盾.**最大公因数与最小公倍数**定义3最大公因数设al,a2,…,ak和d都是整数,k≥2.若d|ai，1≤i≤k,则称d是al,a2,…,ak的公因数.所有公因数中最大的那一个数，称为al,a2,…,ak的最大公因数,记为(al,a2,…,ak).由于每个非零整数的约数的个数是有限的，所以最大公约数是存在的，并且是正整数。显然，(a,1)=1，(a,0)=|a|，(a,a)=|a|；**定理8下面的等式成立：(ⅰ)（a1,a2)=(a2,a1)=(-a1,a2)；一般地(a1,a2,,ai,,ak)=(ai,a2,,a1,,ak)=(-a1,a2,,ak)=(|a1|,|a2|,,|ak|)；(ⅱ)若a1|aj,j=2,,k,则（a1,a2)=(a1,a2,,ak)=(a1)=|a1|(ⅲ)对任意整数x，(a1,a2)=(a1,a2,a1x)(a1,,ak)=(a1,,ak,a1x)；(ⅳ)对任意整数x,（a1,a2)=(a1,a2+a1x)(a1,a2,a3,,ak)=(a1,a2+a1x,a3,,ak)；(ⅴ)若p是素数,则(p,a)=1或pa；一般地（p,a1,,ak)=1或pa.**例5**定义5互素如果(a1,a2,,ak)=1，则称a1,a2,,ak是互素的（或互质的）；如果(ai,aj)=1，1≤i,j≤k，ij，则称a1,a2,,ak是两两互素的（或两两互质的）.显然，a1,a2,,ak两两互素可以推出(a1,a2,,ak)=1，反之则不然，例如(2,6,15)=1，但(2,6)=2.**定理9(a1,a2,,ak)=1的充要条件是存在整数x1,x2,,xk，使得a1x1a2x2akxk=1.充分性若式(1)成立，如果(a1,a2,,ak)=d>1，那么由dai（1≤i≤k）推出da1x1a2x2akxk=1，这是不可能的.所以有(a1,a2,,ak)=1.证毕.**定理10设正整数m|(a1,a2,,ak).我们有m(a1/m,a2/m,,ak/m)=(a1,a2,,ak)特别地有=1.**定义6最小公倍数设a1,a2,,ak和m都是整数,k≥2.若ai|m,1≤i≤k,则称m是a1,a2,,ak的公倍数.在a1,a2,,ak所有公倍数中最小的那一个正整数,称为a1,a2,,ak的最小公倍数,记为[a1,a2,,ak].**定理11(ⅰ)[a1,a2]=[a2,a1]=[-a1,a2].一般地有,[a1,a2,,ai,,ak]=[ai,a2,,a1,,ak]=[-a1,a2,,ai,,ak](ⅱ)若a2|a1,则[a1,a2]=|a1|；(ⅲ)对任意的d|a1[a1,a2]=[a1,a2,d][a1,a2,,ak]=[a1,a2,,ak,d]**定理12设m>0,我们有[ma1,…,mak]=m[a1,…,ak]**§3带余除法与辗转相除法**定理1带余数除法设a与b是两个整数，a0,则存在唯一的两个整数q和r，使得b=aqr，0≤r≤|a|(1)证明存在性若ab，b=aq，qZ，可取r=0.若ab，考虑集合A={bka；kZ}，在集合A中有无限多个正整数，设最小的正整数是r=bk0a，则必有0<r<|a|，(2)否则就有r≥|a|.因为ab，所以r|a|.于是r>|a|，即bk0a>|a|，bk0a|a|>0，这样,在集合A中,又有正整数r1=bk0a|a|<r，这与r的最小性矛盾。**所以式(2)必定成立.取q=k0知式(1)成立.存在性得证.唯一性假设有两对整数q、r与q、r都使得式(1)成立，即b=qar=qar，0≤r,r≤|a|，则(qq)a=rr，|rr|<|a|，(3)因此rr=0，r=r，再由式(3)得出q=q，唯一性得证.证毕.**定理2设a与b是两个整数，a0，设d是一给定的整数.那么，一定存在唯一的两个整数q1和r1，使得b=aq1r1，d≤r1≤|a|+d(4)此外，ab的充要条件是ar1.**定义1称式(1)中的q是b被a除的商，r是b被a除的最小非负余数。式(4)中的r1统称为余数.由定理1可知，对于给定的整数a，可以按照被a除的余数将所有的整数分成a类。在同一类中的数被a除的余数相同。这就使得许多关于全体整数的问题可以归化为对有限个整数类的研究。**推论3设a>0.任一整数被a除后所得的最小非负余数是且仅是0,1,…,a-1这a个数中的一个.由此全体整数按被a除后所得的最小非负余数可分为两两不相交的a个类.0moda,1moda,…,(a-1)modaa=2时，全体整数分为两类：0mod2，1mod2**例2(ⅰ)0mod2∩0mod3=0mod6;(ⅱ)1mod2∩1mod3=1mod6；(ⅲ)0mod2∩1mod3=4mod6.例31mod2=1mod6∪3mod6∪5mod6**例4a进位表示设a≥2是给定的正整数.那么，任一正整数n必可唯一表为n=rkak+rk-1ak-1+…+r1a+r0,(4)其中整数k≥0，0≤rj≤a-1，(0≤j≤k)，rk≠0.这就是正整数的a进位表示.**例5设a>2是奇数.证明：(ⅰ)一定存在正整数d≤a-1,使得a|2d-1.(ⅱ)设d0是满足(ⅰ)的最小正整数d.那么，a|2h-1(h∈N)的充要条件是d0|h.(ⅲ)必有正整数d使得（2d-3,a)=1.**定理4(Euclid)欧几里德算法.设a,b是给定的两个整数，b≠0,ba.我们一定可以重复定理1得到下面的等式：a=bq1+r1,0＜rl＜|b|b=r1q2+r2,0＜r2＜r1r1=r2q3+r3,0＜r3＜r2…….rn-2=rn-1qn+rn,0＜rn＜rn-1rn-1=rnqn+1+0则(a,b)=rn.**证明:由于|b|＞r1＞r2＞…＞rn＞0,故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式,即rn+1=0.根据前面定理可知：(a,b)=(b,r1)=…=(rn-1,rn)=(rn,0)=rn.欧几里德算法也称辗转相除法.**在Euclid算法中,由:rn=rn-2-rn-1qn,rn-1=rn-3-rn-2qn-1,得rn=rn-2(1+qnqn-1)-rn-3qn,再将rn-2=rn-4-rn-3qn-2代入上式,如此继续下去,最后得到:rn=sa+tb,其中s和t是整数.于是有(a,b)是a和b线性组合表示定理.定理5(ⅲ)若任给整数a,b,则存在整数x和y,使得(a,b)=ax+by.容易证明下面结论．(ⅱ)a和b的公因数整除(a,b).**例6①用欧几里德算法求(1997,57).②用1997和57的线性组合表示(1997,57)．③求1997和57的所有公因数．解①用下划线标识余数．1997＝57·35+257＝2·28+12＝l·2+0因此,(1997,57)=l,即1997和57是互素的.**②1=57-2·28=57-(1997-57·35)·28=-28·1997+(57+57·35·28）=-28·1997+981·57③由于1997和57是互素的,公因数只有1和-1.**例7设m,n是正整数.证明（2m-1,2n-1)=2(m,n)-1**§4最大公因数理论**定理1aj|c(1≤j≤k)的充要条件是[a1,…,ak]|c证明：充分性显然.必要性，设[a1,…,ak]=m.c是a1,…,ak的任一公倍数,利用带余除法得:c=mq+r,0≤r<m,aj|c,aj|m,aj|r,(1≤j≤k).故a1|r,…,ak|r,即r是a1,…,ak的公倍数.但由于:1≤r＜m与m是a1,…,ak的最小公倍数发生矛盾,故:r=0,即:c＝mq.故m|c.即[a1,…,ak]|c**定理2设D是正整数.那么D=（a1,a2,,ak）的充要条件是：(ⅰ)D|aj(1≤j≤k);(ⅱ)若daj(1≤j≤k),则d(a1,a2,,ak).这个结论表明：公约数一定是最大公约数的约数。**定理3(ma1,ma2,,mak)=|m|(a1,a2,,ak).定理4(ⅰ)(a1,a2,…,ak)=((a1,a2),a3,…,ak)；(ⅱ)(a1,a2,…,ak+r)=((a1,…,ak),(ak+1,…,ak+r))；推论（a1,a2)(b1,b2)=(a1b1,a1b2,a2b1,a2b2)**定理5若(m,a)=1，则(m,ab)=(m,b).证明:(m,b)=(m,(m,a)b)=(m,mb,ab)=(m,ab).推论若(a,bi)=1,1≤i≤n,则(a,b1b2bn)=1.**定理6对于任意的整数a，b，m，下面的结论成立：(ⅰ)由mab及(m,a)=1可以推出mb；(ⅱ)由m1n，m2n及(m1,m2)=1可以推出m1m2n.一般地，若m1,m2,,mk两两互素，及mjn(1≤j≤k），则m1m2mkn.证明：(ⅰ)(m,a)=1，则(m,ab)=(m,b)，由mab，(m,ab)=|m|，故(m,b)=|m|，从而mb.(ⅱ)m1n知n=m1n1,m2n,即m2m1n1,又(m1,m2)=1,知m2n1，因而m1m2n.**定理7设a1和a2是正整数,且(a1,a2)=d,[a1,a2]=m,则a1a2＝md.**例1设p是素数.证明：(ⅰ)p|，1≤j≤p-1(ⅱ)对任意的正整数a,p|ap-a;(ⅲ)若(p,a)=1，则p|ap-1-1.例2证明：(ⅰ)(a,uv)=(a,(a,u)v);(ⅱ)(a,uv)|(a,u)(a,v)**例3设k是正整数.若一个有理数的k次方是整数，那么，这个有理数一定是整数.