高中數學競賽教材講義 第十七章 整數問題講義

《高中數學競賽教材講義 第十七章 整數問題講義》由會員分享，可在線閱讀，更多相關《高中數學競賽教材講義 第十七章 整數問題講義（4頁珍藏版）》請在裝配圖網上搜索。

1、 第十七章 整數問題 一、常用定義定理 1．整除：設a,b∈Z,a≠0，如果存在q∈Z使得b=aq，那么稱b可被a整除，記作a|b，且稱b是a的倍數,a是b的約數。b不能被a整除，記作a b. 2.帶余數除法：設a,b是兩個給定的整數，a≠0，那么，一定存在唯一一對整數q與r，滿足b=aq+r,0≤r<|a|，當r=0時a|b。 3．輾轉相除法：設u0,u1是給定的兩個整數，u1≠0，u1 u0,由2可得下面k+1個等式：u0=q0u1+u2,0

2、2u1+uk-1+uk,01且n為整數，則，其中pj(j=1,2,…,k)是質數（或稱素數），且在不計次序的意義下，表示是唯一的。 6．同余：設m≠0,若m|(a-b)，即a-b=km，則稱a與b模同m同余，記為a≡b(modm)，也稱b是a對模m的剩余。 7．完全剩余系：一組數y1,y2,…,ys滿足：對任意

3、整數a有且僅有一個yj是a對模m的剩余，即a≡yj(modm)，則y1,y2,…,ys稱為模m的完全剩余系。 8．Fermat小定理：若p為素數，p>a,(a,p)=1，則ap-1≡1(modp)，且對任意整數a,有ap≡a(modp). 9．若(a,m)=1，則≡1(modm),(m)稱歐拉函數。 10．（歐拉函數值的計算公式）若，則(m)= 11．（孫子定理）設m1,m2,…,mk是k個兩兩互質的正整數，則同余組： x≡b1(modm1),x≡b2(modm2),…,x≡bk(modmk)有唯一解， x≡M1b1+M2b2+…+Mkbk(modM)， 其中M=m1m2mk；=

4、，i=1,2,…,k；≡1(modmi),i=1,2,…,k. 二、方法與例題 1．奇偶分析法。 例1 有n個整數，它們的和為0，乘積為n，（n>1），求證：4|n。 [證明] 設這n個整數為a1,a2,…,an，則a1,a2,…,an=n， ① a1+a2+…+an=0。 ② 首先n為偶數，否則a1,a2,…,an均為奇數，奇數個奇數的和應為奇數且不為0，與②矛盾，所以n為偶數。所以a1,a2,…,an中必有偶數，如果a1,a2,…,an中僅有一個偶數，則a1,a2,…,an中還有奇數個奇數，從而a1+a2+…+an也為奇數與②矛盾，所以a1,a2,…,an中必有至

5、少2個偶數。所以4|n. 2．不等分析法。 例2 試求所有的正整數n，使方程x3+y3+z3=nx2y2z2有正整數解。 解 設x,y,z為其正整數解，不妨設x≤y≤z，則由題設z2|(x3+y3)，所以z2≤x3+y3，但x3≤xz2,y3≤yz2，因而z=nx2y2-≥nx2y2-(x+y)，故x3+y3≥z2≥[nx2y2-(x+y)]2，所以n2x4y4≤2nx2y2(x+y)+x3+y3，所以nxy<。若x≥2，則4≤nxy<≤3，矛盾。所以x=1，所以ny<，此式當且僅當y≤3時成立。又z2|(x3+y3)，即z2|(1+y3)，所以只有y=1,z=1或y=2,z=3，代

6、入原方程得n=1或3。 3．無窮遞降法。 例3 確定并證明方程a2+b2+c2=a2b2的所有整數解。 解 首先(a,b,c)=(0,0,0)是方程的整數解，下證該方程只有這一組整數解。假設(a1,b1,c1)是方程的另一組整數解，且a1,b1,c1不全為0，不妨設a1≥0,b1≥0,c1≥0且，由≡1或0(mod4)知a1,b1,c1都是偶數(否則(mod4))，從而是 方程x2+y2+z2=2x2y2的一組整數解，且不全為0，同理可知也都是偶數為方程x2+y2+z2=24x2y2的解。這一過程可以無限進行下去，另一方面a1,b1,c1為有限的整數，必存在k∈N,使2k>a1,2k

7、>b1,2k>c1，從而不是整數，矛盾。所以該方程僅有一組整數解(0,0,0). 4．特殊模法。 例4 證明：存在無窮多個正整數，它們不能表示成少于10個奇數的平方和。 [證明] 考慮形如n=72k+66,k∈N的正整數，若，其中xi為奇數，i=1,2,…,s且1≤s≤9。因為n≡2(mod8)，又≡1(mod8)，所以只有s=2.所以，又因為≡2或0(mod3)，且3|n，所以3|x1且3|x2，所以9|n。但n=72k+66≡3(mod9)，矛盾。所以n不能表示成少于10個奇數的平方和，且這樣的n有無窮多個。 5．最小數原理。 例5 證明：方程x4+y4=z2沒有正整數解。

8、 [證明] 假設原方程有一組正整數解(x0,y0,z0)，并且z0是所有正整數解z中最小的。因此，，則a2-b2,=2ab,z0=a2+b2，其中(a,b)=1,a,b一奇一偶。假設a為偶數，b為奇數，那么(mod4)，而(mod4)，矛盾，所以a為奇數，b為偶數。于是，由得x0=p2-q2,b=2pq,a=p2+q2（這里(p,q)=1,p>q>0,p,q為一奇一偶）。從而推得，因為p,q,p2+q2兩兩互質，因此它們必須都是某整數的平方，即p=r2,q=s2,p2+q2=t2，從而r4+s4=t2，即(r,s,t)也是原方程的解，且有t

9、小性矛盾，故原方程無正整數解。 6．整除的應用。 例6 求出所有的有序正整數數對(m,n)，使得是整數。 解 （1）若n=1,則是整數，所以m-1=1或2，所以(m,n)=(2,1),(3,1). （2）若m=1,則，所以n-1=1或2，所以(m,n)=(1,2),(1,3). （3）若m>1，n>1，因為是整數，所以也是整數，所以m,n是對稱的，不妨設m≥n， ?。┤鬽=n，則為整數，所以n=2,m=2. ⅱ）若m>n，因為n3+1≡1(modn),mn-1≡-1(modn)，所以≡-1(modn). 所以存在k∈N，使kn-1=,又kn-1= 所以(k-1)n<1+,所

10、以k=1，所以n=1=,所以 所以n-1=1或2，所以(m,n)=(5,3)或(5,2). 同理當m

11、數的三進制至多由11個數字組成，因而T中的元素個數共有1+2+22+…+210=211-1=2047>1983（個）。這是因為T中的k位數的個數相當于用0，1這兩個數在k-1個位置上可重復的全排列數（首位必須是1），即2k-1,k=1,2,…,11. （2）T中最大的整數是1+3+32+…+310=88573<105。 （3）T中任意三個數不組成等差排列的三個連續(xù)項。否則，設x,y,z∈T,x+z=2y，則2y必只含0和2，從而x和z必定位位相同，進而x=y=z，這顯然是矛盾的。 三、習題精選 1．試求所有正整數對(a,b)，使得(ab-a2+b+1)|(ab+1). 2．設a,b,

12、c∈N+，且a2+b2-abc是不超過c+1的一個正整數，求證：a2+b2-abc是一個完全平方數。 3．確定所有的正整數數對(x,y)，使得x≤y，且x2+1是y的倍數，y2+1是x的倍數。 4．求所有的正整數n，使得存在正整數m,(2n-1)|(m2+9). 5．求證：存在一個具有如下性質的正整數的集合A，對于任何由無限多個素數組成的集合，存在k≥2及正整數m∈A和nA，使得m和n均為S中k個不同元素的乘積。 6．求最小的正整數n(≥4)，滿足從任意n個不同的整數中能選出四個不同的數a,b,c,d使20|(a+b-c-d). 7.對于正整數a,n,定義Fn(a)=q+r，其中q,r為非負整數，a=qn+r且0≤r≤n，求最大正整數A，使得存在正整數n1,n2,…,n6，對任意正整數a≤A，都有=1，并證明你的結論。 8．設x是一個n位數，問：是否總存在非負整數y≤9和z使得10n+1z+10x+y是一個完全平方數？證明你的結論。 9．設a,b,c,d∈N+,且a>b>c>d,ac+bd=(b+d+a-c)(b+d-a+c)。證明：ab+cd不是素數。 高考資源網() 來源：高考資源網 版權所有：高考資源網(www.k s 5 )