數(shù)論試題中的概念和方法

1、數(shù)論試題中的概念和方法,競賽中常用的定理：歐拉定理 費馬小定理 中國剩余定理 ……,基本研究對象： 整數(shù),涉及的范圍：整除問題 同余問題 不定方程 ……,1、已知a、b、c為正整數(shù)，且 是有理數(shù). 求證：

2、 是整數(shù).,證明：因為 為無理數(shù)，故 b－c≠0， 于是,上式表示有理數(shù)，則有b2-ac=0.從而a2+b2+c2=(a+b+c)2-2ab-2bc-2ca =(a+b+c)2-2(ab+bc+b2) =(a+b+c)(a-b+c).故,整除有如下的一些性質：①若a | b，b | c，則a | c ；②若c | a，d | b，則cd

3、 | ab；③若c | a，c | b，則c |（ma＋nb）； ④若a | b，則ma | mb，反之亦成立； ⑤a、b互質，若a | c，b | c，則ab | c；⑥p為質數(shù)，若p|a1a2…an，則p必能整除a1，a2，…， 　　　an中的某一個； 特別地，若p為質數(shù)，p|an，則p|a.,2、證明：當n為任何整數(shù)時，36|(2n6 – n4 – n2).證明：2n6―n4―n2=n2(2n2＋1)(n2

4、－1)， 當n為偶數(shù)時，4|n2； 當n為奇數(shù)時，n2被4除余數(shù)為1，故4|(n2－1). 故4|n2(2n2＋1)(n2－1). 當n＝3k（k∈Z）時，9|n2(2n2＋1)(n2－1)； 當n＝3k±1（k∈Z）時，n2被3除余數(shù)總是1， 所以3|(n2－1)，且2n2被3除余數(shù)為

5、2， 所以3|(2n2＋1)， 于是9|(n2－1)(2n2＋1)， 故9|n2(n2－1)(2n2＋1). 所以36|(2n6 – n4 – n2).,分析： 按底數(shù)之和為（n＋2）進行配對計算. k2005＋(n＋2－k)2005 ＝(n＋2)[k2004－k2003(n＋2－k)＋…+(n＋2－k)2004]，∴k2005＋(n＋2－k)2005能被n＋2整除

6、（k＝2，3，…）.,因式分解公式：對大于1的整數(shù)n有xn－yn =(x－y)(xn-1+xn-2y+xn-3y2+……+xyn-2+yn-1)；對大于1的奇數(shù)n有xn+yn =(x+y)(xn-1－xn-2y+xn-3y2－……－xyn-2+yn-1)；對大于1的偶數(shù)n有xn－yn =(x+y)(xn-1－xn-2y+xn-3y2－……+xyn-2－yn-1).,同余問題定義:①設m是一個給定的正整數(shù).如果兩個整數(shù)a、

7、b用 m除所得的余數(shù)相同，則稱a、b對模m同余，記 為a≡b(modm) .②若m|(a－b)，則稱a、b對模m同余.③若a=b+mt(t∈Z)，則稱a、b對模m同余.,性質：①a≡a（mod m） ②若a≡b（mod m），則b≡a（mod m）③若a≡b（mod m）,b≡c（mod m）,則a≡c（mod m）④若a≡b（mod m）,c≡d（mod m）, 則a±c≡b±d

8、（mod m），ac≡bd（mod m）, a n≡b n（mod m）⑤若n|m，a≡b（mod m），則a≡b（mod n）⑥若(m，n)＝1，a≡b（mod m），a≡b（mod n）， 則a≡b（mod mn）,⑦歐拉定理：若（a,m）=1，則⑧費爾馬小定理：p是素數(shù)，則ap≡a（mod p） 若另上條件（a，p）＝1，則ap-1≡1（mod p）⑨威爾遜定理：設p素數(shù)，則（p－1）！≡-1（mo

9、d p）.,4、一個數(shù)的各位數(shù)字的和被9除的余數(shù)等于這個數(shù)被9除的余數(shù).,證明 設a=,=an×10n+an-1×10n-1+…+a1×10+a0， ∵10≡1(mod9)，∴10n≡1(mod9)， ∴an×10n+an-1×10n-1+…+a1×10+a0 ≡an+an-1+…+a1+a0(mod9),5、 試求出一切可使

10、 被3整除的自然數(shù).,,,,,6、求 除以13的余數(shù).,,解：103≡－1（mod13） 106≡1（mod13） 102≡16≡10（mod6） 103≡102≡10（mod6） 10n≡10n-1≡…≡10≡4（mod6） 10n＝6k＋4∴ ≡106k+4≡(106)k×104≡1k×104≡104≡3（mod13）,不定方程

11、 不定方程是指未知數(shù)的個數(shù)多于方程的個數(shù)，且未知數(shù)的取值范圍是受某些限制（如整數(shù)、正整數(shù)或有理數(shù)）的方程.,對于二元一次不定方程問題，我們有兩個定理：①二元一次不定方程ax+by=c (a，b，c為整數(shù))有整數(shù)解的充分必要條件是(a,b)|c.②若(a,b)=1，且x0，y0為上述方程的一組解，則方程的全部解為x=x0+bt，y=y0-at(t為整數(shù)).對于非二元一次不定方程問題，常用的求解方法有：①恒等變形;②構造法;③奇偶

12、分析法; ④不等式估計法.,7、求滿足方程2x2+5y2=11(xy－11)的正整數(shù)數(shù)組(x，y).,(2x－y) (x－5y)=－112.,8、求不定方程14x2－24 xy+21y2+4x－12y－18=0的整數(shù)解.,解 原式變形為：2(x－3y+1)2+3(2x－y)2=20，故 3(2x－y)2≤20， 即平方數(shù)(2x－y)2≤4，當 (2x－y)2=0，1時，(x－3y+1)2=10或2(x－3y+1)2=17，均

13、不可能，故(2x－y)2=4，從而 (x－3y+1)2=4，由此得方程有唯一整數(shù)解：（1，0）.,證明由于2×5－1=32，2×13－1=52，5×13－1=82， 因此，只需證明2d－1，5d－1，13d－1中 至少有一個不是完全平方數(shù). 假設它們都是完全平方數(shù)，令 2d－1=x2 ① 5d－1=y2 ② 13d－1=z2

14、 ③ x,y,z∈N* 由①知，x是奇數(shù)，設x=2k－1， 于是2d－1=(2k－1)2，即d=2k2－2k+1， 這說明d也是奇數(shù). 因此，再由②，③知，y,z均是偶數(shù).,9、（第27屆IMO試題）設正整數(shù)d不等于2，5，13.證明在集合｛2，5，13，d｝中可以找到兩個元素a,b，使得ab－1不是完全平方數(shù).,,反證法,設y=2m，z=2n，代入②，③，相減，除以4得，2d=n2－m2=

15、(n+m)(n－m)，從而n2－m2為偶數(shù)，n，m必同是偶數(shù)或同是奇數(shù)，于是m+n與m－n都是偶數(shù)，這樣2d就是4的倍數(shù)，即d為偶數(shù)，這與上述d為奇數(shù)矛盾.故命題得證.,2d－1=x2 ①5d－1=y2 ② 13d－1=z2 ③,d是奇數(shù)，y,z均是偶數(shù),解 5×2m=n2－1=(n+1)(n-1)， 其中n+1與n-1同為偶數(shù)， 則n為奇數(shù)，設n=2k

16、-1(k∈N+)，,10、（2006澳大利亞數(shù)學奧林匹克）求所有的正整數(shù)m、n，使得1+5×2m=n2.,所以5×2m=4k(k-1),即5×2m-2=k(k-1),故m≥2,k＞1，因k與k-1一奇一偶，故,解得k=5，m=4，所以m=4，n=9滿足條件.,11、（2004年中國西部數(shù)學奧林匹克）求所有的整數(shù)n，使得n4+6n3+11n2+3n+31是完全平方數(shù)．,解 設A＝n4+6n3+11n2+

17、3n+31是完全平方數(shù)， 則配方后A＝(n2+3n+1)2―3(n―10)是完全平方數(shù)． 當n=10時，A＝(102+3×10+1)2=1312是完全平方數(shù). 當n＞10時，A＜(n2+3n+1)2， 所以A≤(n2+3n)2， ∴A―(n2+3n)2＝ (n2+3n+1)2―3(n―10)―(n2+3n)2≤0， 即(n2+3n+1)2―(n2+3n)2≤

18、3(n―10)， ∴2n2+3n+31≤0，這不可能．,于是A≥(n2+3n+2)2，化簡得2n2+9n－27≤0，,∴ n=－6，－5，－4，－3， －2，－1， 0，1，2，此時對應的A=409，166，67，40， 37，34， 31，52，145都不是完全平方數(shù)．,A＝(n2+3n+1)2―3(n―10),當n＜10時，A＞(n2+3n+1)2，,所以，只有當n=10時，A是完全平方數(shù)．,(1)平方數(shù)的個位數(shù)字只可能是0

19、，1，4，5，6，9；(2)偶數(shù)的平方數(shù)是4的倍數(shù)，奇數(shù)的平方數(shù)被8除余1， 即任何平方數(shù)被4除的余數(shù)只能是0或1；(3)奇數(shù)平方的十位數(shù)字是偶數(shù)；(4)十位數(shù)字是奇數(shù)的平方數(shù)的個位數(shù)一定是6；(5)不能被3整除的數(shù)的平方被3除余1， 能被3整除的數(shù)的平方能被3整除， 因而，平方數(shù)被9除的余數(shù)為0，1，4，7；(6)平方數(shù)的約數(shù)的個數(shù)為奇數(shù)；(7)任何四個連續(xù)整數(shù)的乘積加1，必定是一個平方數(shù)；(8)在兩個

20、相鄰的整數(shù)的平方數(shù)之間的所有整數(shù)都不是完 　　全平方數(shù).,完全平方數(shù)的性質,d是a的正因數(shù),其中0≤βi≤αi，i=l，2，…，s,a的正因數(shù)的個數(shù)為d(a)=(α1+1)(α2+1)…(αs+1),,a的正因數(shù)的和,12、（2003年泰國數(shù)學奧林匹克）求所有使p2+2543具有少于16個不同正因數(shù)的質數(shù)p.,解 當p=2時，p2+2543=2547=32×283，283是質數(shù)， 此時共有正因數(shù)(2+1)×

21、(1+1)=6個，滿足條件； 當p=3時，p2+2543=2552=23×11×19， 此時共有正因數(shù)(3+1)×(1+1)×(1+1)=16個，不滿足條件； 當p＞3時，p2+2543=(p-1)(p+1)+2400+144， … (p-1)(p+1)是24的倍數(shù)，所以p2+2543是24的倍數(shù)， p2+2543=23+i×31+j×

22、;m， 若m＞1，共有正因數(shù)(3+i+1)×(1+j+1)×(k+1)≥16個， 若m=1，2i×3j＞106， 當j＞1，正因數(shù)個數(shù)不少于16， 當j=1，i＞4，正因數(shù)個數(shù)不少于24， 當j=0，i＞5，正因數(shù)個數(shù)不少于18， 所以 p＞3不滿足條件. 綜上所述，p≥2時，正因數(shù)個數(shù)至少有16個，

23、而p=2時正因數(shù)個數(shù)為6，故所求的質數(shù)p是2.,13、（2004土耳其數(shù)學奧林匹克）(1)對于每一個整數(shù)k=1,2,3，求一個整數(shù)n，使n2-k的正 因數(shù)個數(shù)為10.(2)證明：對于所有整數(shù)n，n2-4的正因數(shù)個數(shù)不是10.,(1)解： k=1,24×3+1=72 k=2,74×23+2=2352 k=3,374×13+3=49362,(

24、2)證明：假設存在n，使n2-4有10個因數(shù).ⅰ若n2-4=p9(p為質數(shù))，即(n-2)(n+2)= p9,令n-2=pi,n+2=pj (i4,所以無解.ⅱ若n2-4=p14 p2，（p1,p2為質數(shù)，且p1≠p2）， 即(n-2)(n+2) =p14 p2， 當(n-2,n+2)=1時， ①n-2=1，則n+2=5，無解. ②n-2= p14，n+2= p2，則p2 -p14=4.,如果

25、p1=5，則p2=629=17×37，矛盾.如果p1≠5，則p14≡1(mod5),p2≡p14+4≡0(mod5).故p2=5，p14=1無解.③n-2= p2, n+2= p14，則p14-p2 =4，所以(p12-2)(p12+2)= p2所以，p12-2=1，p12=3，無解.當(n-2,n+2)>1時,又(n+2)-(n-2)=4，則p1=2，所以p2為奇數(shù).故n2=16 p2+4，所以2|n.

26、設n=2m，則m2=4p2+1≡5(mod8)，矛盾.因此，不存在整數(shù)n，使得n2-4的正因數(shù)個數(shù)是10.,14、（2006澳大利亞數(shù)學奧林匹克）對于任意正整數(shù)n， 設a(n)是n的各位數(shù)的乘積.(1)證明：對所有正整數(shù)n，有n≥a(n) ；(2)求所有的n，使得n2-17n+56=a(n)成立.,(1)證明 令,則,(2)解 由n2-17n+56=a(n),及a(n)≤n 得n2-17n+56≤n，即n2

27、-18n+56≤0， 解得 4≤n≤14. 又由n2-17n+56≥0,得n≤4,或n≥13, 則n∈｛4,13,14｝ 逐一檢驗得 n＝4.,15、（2005德國數(shù)學奧林匹克）設Q(n)表示正整數(shù)n的各位數(shù)字之和，證明：Q(Q(Q(20052005)))=7.,證明 因為Q(n)≡n(mod9)， 而20052005≡(9×222+7)2005≡72005(mod9)

28、， 由歐拉定理,所以20052005≡72005=76×334+1(mod9)≡7(mod9)，故Q(Q(Q(20052005))) ≡20052005≡7(mod9).又20052005＜(104)2005=108020，所以，20052005至多有8020位，故Q(20052005)≤9×8020=72180于是Q(20052005)至多只有5位，因此Q(Q(20052005))≤9

29、5;5=45,從而Q(Q(Q(20052005)))≤3+9=12,又Q(Q(Q(20052005)))≡7(mod9)，所以Q(Q(Q(20052005)))＝7.,16、(2004年西部數(shù)學奧林匹克)設n∈N*，用d(n)表示n的所有正約數(shù)的個數(shù)，φ(n)表示1，2，…，n中與n互質的數(shù)的個數(shù)．求所有的非負整數(shù)c，使得存在正整數(shù)n，滿足 d(n)＋φ(n)＝n＋c，并且對這樣的每一個c，求出所有滿足上式的正整數(shù)n.,分析 d(

30、n)表示n的所有正約數(shù)的個數(shù)， φ(n)是1，2，…，n中與n互質的數(shù)的個數(shù)，兩類數(shù)中的公共部分只有1，如果1，2，…，n中的數(shù)恰好是大于1的正約數(shù)與第二類中大于1的某數(shù)的乘積，該數(shù)不在這兩類數(shù)中，把這種數(shù)稱為第三類數(shù).當沒有第三類數(shù)時．c=1；當有1個第三類數(shù)時．c=0；當?shù)谌悢?shù)的個數(shù)大于1時．c＜0.,17、(2004-2005匈牙利數(shù)學奧林匹克)已知n是正整數(shù)，如果存在整數(shù)a1,a2,…,an（不一定是不同的），使得a

31、1+a2+…+an=a1a2…an=n，則稱n是“迷人的”.求迷人的整數(shù).,解：若k=4t+1,t∈N，顯然滿足要求， 取4t+1及2t個1，2t個-1即可.若k=4，則a1a2 a3a4=4，只可能a4=4或a4=a3=2，顯然無解.若k=4t，t≥2，分兩種情況討論.當t為奇數(shù)時，取2t，-2，x個1，y個-1（x，y待定）.則x+y=4t-2，x-y+2t-2=4t.解得x=3t，y=t-2.顯然這樣一組數(shù)滿足題

32、設要求.,當t為偶數(shù)時，類似地取2t，2，x個 1，y個-1，則x+y=4t-2，x-y=2t-2.解得x=3t-2，y=t.這一組數(shù)比滿足題設要求.綜上，4t(t≥2)型數(shù)是迷人的.下面證明4t+2，4t+3型數(shù)是不迷人的.若4t+2型數(shù)是迷人的，設4t+2= a1+a2+…+a4t+2=a1a2…a4t+2.易知，ai中有且僅有一個偶數(shù)，其余4t+1個數(shù)均為奇數(shù)，故a1+a2+…+a4t+2必為奇數(shù)，矛盾.因此4t+2