高中數(shù)學(xué)競(jìng)賽標(biāo)準(zhǔn)講義：第十七章：整數(shù)問題新人教A版（通用）

1、第十七章 整數(shù)問題一、常用定義定理1整除：設(shè)a,bZ,a0，如果存在qZ使得b=aq，那么稱b可被a整除，記作a|b，且稱b是a的倍數(shù),a是b的約數(shù)。b不能被a整除，記作a b.2.帶余數(shù)除法：設(shè)a,b是兩個(gè)給定的整數(shù)，a0，那么，一定存在唯一一對(duì)整數(shù)q與r，滿足b=aq+r,0r|a|，當(dāng)r=0時(shí)a|b。3輾轉(zhuǎn)相除法：設(shè)u0,u1是給定的兩個(gè)整數(shù)，u10，u1 u0,由2可得下面k+1個(gè)等式：u0=q0u1+u2,0u2|u1|；u1=q1u2+u3,0u3u2；u2=q2u3+u4,0u4u3；uk-2=qk-2u1+uk-1+uk,0ukuk-1；uk-1=qk-1uk+1,0uk+11

2、且n為整數(shù)，則，其中pj(j=1,2,k)是質(zhì)數(shù)（或稱素?cái)?shù)），且在不計(jì)次序的意義下，表示是唯一的。6同余：設(shè)m0,若m|(a-b)，即a-b=km，則稱a與b模同m同余，記為ab(modm)，也稱b是a對(duì)模m的剩余。7完全剩余系：一組數(shù)y1,y2,ys滿足：對(duì)任意整數(shù)a有且僅有一個(gè)yj是a對(duì)模m的剩余，即ayj(modm)，則y1,y2,ys稱為模m的完全剩余系。8Fermat小定理：若p為素?cái)?shù)，pa,(a,p)=1，則ap-11(modp)，且對(duì)任意整數(shù)a,有apa(modp).9若(a,m)=1，則1(modm),(m)稱歐拉函數(shù)。10（歐拉函數(shù)值的計(jì)算公式）若，則(m)=11（孫子定理）

3、設(shè)m1,m2,mk是k個(gè)兩兩互質(zhì)的正整數(shù)，則同余組：xb1(modm1),xb2(modm2),xbk(modmk)有唯一解，xM1b1+M2b2+Mkbk(modM)，其中M=m1m2mk；=，i=1,2,k；1(modmi),i=1,2,k.二、方法與例題1奇偶分析法。例1 有n個(gè)整數(shù)，它們的和為0，乘積為n，（n1），求證：4|n。證明 設(shè)這n個(gè)整數(shù)為a1,a2,an，則a1,a2,an=n， a1+a2+an=0。 首先n為偶數(shù)，否則a1,a2,an均為奇數(shù)，奇數(shù)個(gè)奇數(shù)的和應(yīng)為奇數(shù)且不為0，與矛盾，所以n為偶數(shù)。所以a1,a2,an中必有偶數(shù)，如果a1,a2,an中僅有一個(gè)偶數(shù)，則a1

4、,a2,an中還有奇數(shù)個(gè)奇數(shù)，從而a1+a2+an也為奇數(shù)與矛盾，所以a1,a2,an中必有至少2個(gè)偶數(shù)。所以4|n.2不等分析法。例2 試求所有的正整數(shù)n，使方程x3+y3+z3=nx2y2z2有正整數(shù)解。解 設(shè)x,y,z為其正整數(shù)解，不妨設(shè)xyz，則由題設(shè)z2|(x3+y3)，所以z2x3+y3，但x3xz2,y3yz2，因而z=nx2y2-nx2y2-(x+y)，故x3+y3z2nx2y2-(x+y)2，所以n2x4y42nx2y2(x+y)+x3+y3，所以nxy。若x2，則4nxy3，矛盾。所以x=1，所以nya1,2kb1,2kc1，從而不是整數(shù)，矛盾。所以該方程僅有一組整數(shù)解(0

5、,0,0).4特殊模法。例4 證明：存在無窮多個(gè)正整數(shù)，它們不能表示成少于10個(gè)奇數(shù)的平方和。證明 考慮形如n=72k+66,kN的正整數(shù)，若，其中xi為奇數(shù)，i=1,2,s且1s9。因?yàn)閚2(mod8)，又1(mod8)，所以只有s=2.所以，又因?yàn)?或0(mod3)，且3|n，所以3|x1且3|x2，所以9|n。但n=72k+663(mod9)，矛盾。所以n不能表示成少于10個(gè)奇數(shù)的平方和，且這樣的n有無窮多個(gè)。5最小數(shù)原理。例5 證明：方程x4+y4=z2沒有正整數(shù)解。證明 假設(shè)原方程有一組正整數(shù)解(x0,y0,z0)，并且z0是所有正整數(shù)解z中最小的。因此，則a2-b2,=2ab,z0

6、=a2+b2，其中(a,b)=1,a,b一奇一偶。假設(shè)a為偶數(shù)，b為奇數(shù)，那么(mod4)，而(mod4)，矛盾，所以a為奇數(shù)，b為偶數(shù)。于是，由得x0=p2-q2,b=2pq,a=p2+q2（這里(p,q)=1,pq0,p,q為一奇一偶）。從而推得，因?yàn)閜,q,p2+q2兩兩互質(zhì)，因此它們必須都是某整數(shù)的平方，即p=r2,q=s2,p2+q2=t2，從而r4+s4=t2，即(r,s,t)也是原方程的解，且有tt2=p2+q2=a1，n1，因?yàn)槭钦麛?shù)，所以也是整數(shù)，所以m,n是對(duì)稱的，不妨設(shè)mn，）若m=n，則為整數(shù)，所以n=2,m=2.）若mn，因?yàn)閚3+11(modn),mn-1-1(mo

7、dn)，所以-1(modn).所以存在kN，使kn-1=,又kn-1=所以(k-1)n1+,所以k=1，所以n=1=,所以所以n-1=1或2，所以(m,n)=(5,3)或(5,2).同理當(dāng)mn時(shí)，有(m,n)=(2,5),(3,5).綜上(m,n)=(1,2),(2,1),(1,3),(3,1),(2,2),(2,5),(5,2),(3,5),(5,3).7進(jìn)位制的作用例7 能否選擇1983個(gè)不同的正整數(shù)都不大于105，且其中沒有3個(gè)正整數(shù)是等差數(shù)列中的連續(xù)項(xiàng)？證明你的結(jié)論。解 將前105個(gè)自然數(shù)都表示為三進(jìn)制，在這些三進(jìn)制數(shù)中只選取含數(shù)字0或1（而不含數(shù)字2）的數(shù)組成數(shù)集T，下證T中的數(shù)符合要求。（1）因?yàn)?101051983（個(gè)）。這是因?yàn)門中的k位數(shù)的個(gè)數(shù)相當(dāng)于用0，1這