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

1、競賽中常用的定理：競賽中常用的定理：歐拉定理歐拉定理 費馬小定理費馬小定理 中國剩余定理中國剩余定理 基本研究對象：基本研究對象： 整數(shù)整數(shù)涉及的范圍：涉及的范圍：整除問題整除問題 同余問題同余問題 不定方程不定方程 1、已知a、b、c為正整數(shù)，且 是有理數(shù). 求證： 是整數(shù).33abbc222abcabc證明：因為 為無理數(shù)，故 bc0， 于是 33222223( 3)( 3)33()333ababbcabbcbacbcbcbc222.abca b cZa b c 上式表示有理數(shù)，則有b2-ac=0.從而a2+b2+c2=(a+b+c)2-2ab-2bc-2ca =(a+b+c)2-2(ab

2、+bc+b2) =(a+b+c)(a-b+c).故整除有如下的一些性質(zhì)：若a | b，b | c，則a | c ；若c | a，d | b，則cd | ab；若c | a，c | b，則c |（manb）； 若a | b，則ma | mb，反之亦成立； a、b互質(zhì)，若a | c，b | c，則ab | c；p為質(zhì)數(shù)，若p|a1a2an，則p必能整除a1，a2， an中的某一個； 特別地，若p為質(zhì)數(shù)，p|an，則p|a.2、證明：當(dāng)n為任何整數(shù)時，36|(2n6 n4 n2).證明：2n6n4n2=n2(2n21)(n21)， 當(dāng)n為偶數(shù)時，4|n2； 當(dāng)n為奇數(shù)時，n2被4除余數(shù)為1，故4|(

3、n21). 故4|n2(2n21)(n21). 當(dāng)n3k（kZ）時，9|n2(2n21)(n21)； 當(dāng)n3k1（kZ）時，n2被3除余數(shù)總是1， 所以3|(n21)，且2n2被3除余數(shù)為2， 所以3|(2n21)， 于是9|(n21)(2n21)， 故9|n2(n21)(2n21). 所以36|(2n6 n4 n2).3、對任意正整數(shù)n，求證：(n +2) (12005 + 22005 + +n2005). 分析：分析： 按底數(shù)之和為（n2）進行配對計算. k2005(n2k)2005 (n2)k2004k2003(n2k)+(n2k)2004，k2005(n2k)2005能被n2整除（k2

4、，3，）.因式分解公式：對大于1的整數(shù)n有xnyn =(xy)(xn-1+xn-2y+xn-3y2+xyn-2+yn-1)；對大于1的奇數(shù)n有xn+yn =(x+y)(xn-1xn-2y+xn-3y2xyn-2+yn-1)；對大于1的偶數(shù)n有xnyn =(x+y)(xn-1xn-2y+xn-3y2+xyn-2yn-1).同余問題同余問題定義定義:設(shè)m是一個給定的正整數(shù).如果兩個整數(shù)a、b用 m除所得的余數(shù)相同，則稱a、b對模m同余，記 為ab(modm) .若m|(ab)，則稱a、b對模m同余.若a=b+mt(tZ)，則稱a、b對模m同余.性質(zhì)：性質(zhì)：aa（mod m） 若ab（mod m），

5、則ba（mod m）若ab（mod m）,bc（mod m）,則ac（mod m）若ab（mod m）,cd（mod m）, 則acbd（mod m），acbd（mod m）, a nb n（mod m）若n|m，ab（mod m），則ab（mod n）若(m，n)1，ab（mod m），ab（mod n）， 則ab（mod mn）歐拉定理：若（a,m）=1，則費爾馬小定理：p是素數(shù)，則apa（mod p） 若另上條件（a，p）1，則ap-11（mod p）威爾遜定理：設(shè)p素數(shù)，則（p1）！-1（mod p）.()1(mod)mam4 4、一個數(shù)的各位數(shù)字的和被、一個數(shù)的各位數(shù)字的和被9 9除

6、的余數(shù)等于這個數(shù)除的余數(shù)等于這個數(shù)被被9 9除的余數(shù)除的余數(shù). . 證明證明 設(shè)設(shè)a= =110nna aa a = =an1010n+ +an-1-11010n-1-1+ + +a1 110+10+a0 0， 101(101(mod9)9)，1010n1(1(mod9)9)， an1010n+ +an-1-11010n-1-1+ + +a1 110+10+a0 0 an+ +an-1-1+ + +a1 1+ +a0 0( (mod9)9)5、 試求出一切可使 被3整除的自然數(shù).21nnnn6136233|n 21n 22(mod3)261(0 1 2)2(61) 2(122) (3 1)2(

7、mod3)62(0 1 2)2(62) 2(248) (3 1)2(mod3)nnkknkknnkknkknkknkk解：若，則考慮到 及，則當(dāng)時，、 、當(dāng)時，、 、6364363(0 1 2)2(63) 20(mod3)64(0 1 2)2(64) 2(9664) (3 1)1(mod3)nknkknkknknkknkk當(dāng)時，、 、當(dāng)時，、 、6536665(0 1 2)2(65) 2(6 32160) (3 1)1(mod3)66(0 1 2)2(66) 20(mod3)616223nkknknnkknkknkknknkkn當(dāng)時，、 、當(dāng)時，、 、由上可知當(dāng)且僅當(dāng)，時，+1能被 整除；10

8、10n6、求 除以13的余數(shù).1010n解：解：1031（mod13） 1061（mod13） 1021010（mod6） 10310210（mod6） 10n10n-1104（mod6） 10n6k4 106k+4(106)k1041k1041043（mod13）1010n不定方程不定方程 不定方程是指未知數(shù)的個數(shù)多于方程的個數(shù)，且未知數(shù)的取值范圍是受某些限制（如整數(shù)、正整數(shù)或有理數(shù)）的方程.對于二元一次不定方程問題，我們有兩個定理：二元一次不定方程ax+by=c (a，b，c為整數(shù))有整數(shù)解的充分必要條件是(a,b)|c.若(a,b)=1，且x0，y0為上述方程的一組解，則方程的全部解為x

9、=x0+bt，y=y0-at(t為整數(shù)).對于非二元一次不定方程問題，常用的求解方法有：恒等變形;構(gòu)造法;奇偶分析法; 不等式估計法.7、求滿足方程2x2+5y2=11(xy11)的正整數(shù)數(shù)組(x，y).(2xy) (x5y)=112.8、求不定方程14x224 xy+21y2+4x12y18=0的整數(shù)解.解解 原式變形為：2(x3y+1)2+3(2xy)2=20，故 3(2xy)220， 即平方數(shù)(2xy)24，當(dāng) (2xy)2=0，1時，(x3y+1)2=10或2(x3y+1)2=17，均不可能，故(2xy)2=4，從而 (x3y+1)2=4，由此得方程有唯一整數(shù)解：（1，0）.證明由于2

10、51=32，2131=52，5131=82， 因此，只需證明2d1，5d1，13d1中 至少有一個不是完全平方數(shù). 假設(shè)它們都是完全平方數(shù)，令 2d1=x2 5d1=y2 13d1=z2 x,y,zN* 由知，x是奇數(shù)，設(shè)x=2k1， 于是2d1=(2k1)2，即d=2k22k+1， 這說明d也是奇數(shù). 因此，再由，知，y,z均是偶數(shù).9、（第27屆IMO試題）設(shè)正整數(shù)d不等于2，5，13.證明在集合2，5，13，d中可以找到兩個元素a,b，使得ab1不是完全平方數(shù).反證法反證法設(shè)y=2m，z=2n，代入，相減，除以4得，2d=n2m2=(n+m)(nm)，從而n2m2為偶數(shù)，n，m必同是偶數(shù)

11、或同是奇數(shù)，于是m+n與mn都是偶數(shù)，這樣2d就是4的倍數(shù)，即d為偶數(shù)，這與上述d為奇數(shù)矛盾.故命題得證.2d1=x2 5d1=y2 13d1=z2 d是奇數(shù)，y,z均是偶數(shù)解 52m=n21=(n+1)(n-1)， 其中n+1與n-1同為偶數(shù)， 則n為奇數(shù)，設(shè)n=2k-1(kN+)，10、（2006澳大利亞數(shù)學(xué)奧林匹克）求所有的正整數(shù)m、n，使得1+52m=n2.所以52m=4k(k-1),即52m-2=k(k-1),故m2,k1，因k與k-1一奇一偶，故25 2,11,mkk 25,12,mkk 22,15,mkk 或或解得k=5，m=4，所以m=4，n=9滿足條件.11、（2004年中國

12、西部數(shù)學(xué)奧林匹克）求所有的整數(shù)n，使得n4+6n3+11n2+3n+31是完全平方數(shù) 解 設(shè)An4+6n3+11n2+3n+31是完全平方數(shù)， 則配方后A(n2+3n+1)23(n10)是完全平方數(shù) 當(dāng)n=10時，A(102+310+1)2=1312是完全平方數(shù). 當(dāng)n10時，A(n2+3n+1)2， 所以A(n2+3n)2， A(n2+3n)2 (n2+3n+1)23(n10)(n2+3n)20， 即(n2+3n+1)2(n2+3n)23(n10)， 2n2+3n+310，這不可能 于是A(n2+3n+2)2，化簡得2n2+9n270， n=6，5，4，3， 2，1， 0，1，2，此時對應(yīng)的

13、A=409，166，67，40， 37，34， 31，52，145都不是完全平方數(shù)A(n2+3n+1)23(n10)當(dāng)n10時，A(n2+3n+1)2，3( 333)3( 333)73,44n 所以，只有當(dāng)n=10時，A是完全平方數(shù)(1)平方數(shù)的個位數(shù)字只可能是0，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ù)

14、為奇數(shù)；(7)任何四個連續(xù)整數(shù)的乘積加1，必定是一個平方數(shù)；(8)在兩個相鄰的整數(shù)的平方數(shù)之間的所有整數(shù)都不是完 全平方數(shù).完全平方數(shù)的性質(zhì)完全平方數(shù)的性質(zhì) 1212iSiSpppp12,nippppi算術(shù)基本定理：算術(shù)基本定理：任何一個大于任何一個大于1 1的整數(shù)均可分解為素數(shù)的整數(shù)均可分解為素數(shù)的乘積，若不考慮素數(shù)相乘的前后順序，則分解式是惟的乘積，若不考慮素數(shù)相乘的前后順序，則分解式是惟一的即大于一的即大于1 1的整數(shù)的整數(shù)a可以表示為：可以表示為：a= =，其中，其中i=li=l，2 2，s s為質(zhì)數(shù)，為質(zhì)數(shù)， 為非負整數(shù)為非負整數(shù). .d是是a的正因數(shù)的正因數(shù)1212iSiSdppp

15、p其中其中00ii，i=l=l，2 2，sa的正因數(shù)的個數(shù)的正因數(shù)的個數(shù)為為d( (a)=()=(1 1+1)(+1)(2 2+1)+1)( (s+1) ) a的正因數(shù)的和的正因數(shù)的和1111( )(1)1iinniiiiipappp12、（2003年泰國數(shù)學(xué)奧林匹克）求所有使p2+2543具有少于16個不同正因數(shù)的質(zhì)數(shù)p.解 當(dāng)p=2時，p2+2543=2547=32283，283是質(zhì)數(shù)， 此時共有正因數(shù)(2+1)(1+1)=6個，滿足條件； 當(dāng)p=3時，p2+2543=2552=231119， 此時共有正因數(shù)(3+1)(1+1)(1+1)=16個，不滿足條件； 當(dāng)p3時，p2+2543=(

16、p-1)(p+1)+2400+144， (p-1)(p+1)是24的倍數(shù)，所以p2+2543是24的倍數(shù)， p2+2543=23+i31+jm， 若m1，共有正因數(shù)(3+i+1)(1+j+1)(k+1)16個， 若m=1，2i3j106， 當(dāng)j1，正因數(shù)個數(shù)不少于16， 當(dāng)j=1，i4，正因數(shù)個數(shù)不少于24， 當(dāng)j=0，i5，正因數(shù)個數(shù)不少于18， 所以 p3不滿足條件. 綜上所述，p2時，正因數(shù)個數(shù)至少有16個， 而p=2時正因數(shù)個數(shù)為6，故所求的質(zhì)數(shù)p是2.13、（2004土耳其數(shù)學(xué)奧林匹克）(1)對于每一個整數(shù)k=1,2,3，求一個整數(shù)n，使n2-k的正 因數(shù)個數(shù)為10.(2)證明：對于

17、所有整數(shù)n，n2-4的正因數(shù)個數(shù)不是10.(1)解： k=1,243+1=72 k=2,7423+2=2352 k=3,37413+3=49362(2)證明：假設(shè)存在n，使n2-4有10個因數(shù).若n2-4=p9(p為質(zhì)數(shù))，即(n-2)(n+2)= p9,令n-2=pi,n+2=pj (i4,所以無解.若n2-4=p14 p2，（p1,p2為質(zhì)數(shù)，且p1p2）， 即(n-2)(n+2) =p14 p2， 當(dāng)(n-2,n+2)=1時， n-2=1，則n+2=5，無解. n-2= p14，n+2= p2，則p2 -p14=4.如果p1=5，則p2=629=1737，矛盾.如果p15，則p141(m

18、od5),p2p14+40(mod5).故p2=5，p14=1無解.n-2= p2, n+2= p14，則p14-p2 =4，所以(p12-2)(p12+2)= p2所以，p12-2=1，p12=3，無解.當(dāng)(n-2,n+2)1時,又(n+2)-(n-2)=4，則p1=2，所以p2為奇數(shù).故n2=16 p2+4，所以2|n.設(shè)n=2m，則m2=4p2+15(mod8)，矛盾.因此，不存在整數(shù)n，使得n2-4的正因數(shù)個數(shù)是10.14、（2006澳大利亞數(shù)學(xué)奧林匹克）對于任意正整數(shù)n， 設(shè)a(n)是n的各位數(shù)的乘積.(1)證明：對所有正整數(shù)n，有na(n) ；(2)求所有的n，使得n2-17n+5

19、6=a(n)成立.110101010kkkkkkna aaaaa(1)證明 令100109( )kkkkkkkiiiinaaaaaa n則(2)解 由n2-17n+56=a(n),及a(n)n 得n2-17n+56n，即n2-18n+560， 解得 4n14. 又由n2-17n+560,得n4,或n13, 則n4,13,14 逐一檢驗得 n4.15、（2005德國數(shù)學(xué)奧林匹克）設(shè)Q(n)表示正整數(shù)n的各位數(shù)字之和，證明：Q(Q(Q(20052005)=7.證明 因為Q(n)n(mod9)， 而20052005(9222+7)200572005(mod9)， 由歐拉定理(9)6771(mod9)

20、所以2005200572005=76334+1(mod9)7(mod9)，故Q(Q(Q(20052005) 200520057(mod9).又20052005(104)2005=108020，所以，20052005至多有8020位，故Q(20052005)98020=72180于是Q(20052005)至多只有5位，因此Q(Q(20052005)95=45,從而Q(Q(Q(20052005)3+9=12,又Q(Q(Q(20052005)7(mod9)，所以Q(Q(Q(20052005)7.16、(2004年西部數(shù)學(xué)奧林匹克)設(shè)nN*，用d(n)表示n的所有正約數(shù)的個數(shù)，(n)表示1，2，n中與n互質(zhì)的數(shù)的個數(shù)求所有的非負整數(shù)c，使得存在正整數(shù)n，滿足 d(n)(n)nc，并且對這樣的每一個c，求出所有滿足上式的正整數(shù)n.分析分析 d(n)表示n的所有正約數(shù)的個數(shù)， (n)是1，2，n中與n互質(zhì)的數(shù)的個數(shù)，兩類數(shù)中的公共部分只有1，如果1，2，n中的數(shù)恰好是大于1的正約數(shù)與第二類中大于1的某數(shù)的乘積，該數(shù)不在這兩類數(shù)中，把這種數(shù)稱為第三類數(shù).當(dāng)沒有第三類數(shù)時c=1；當(dāng)有1