--同余式與不定方程

　　同余式和不定方程是數(shù)論中古老而富有魅力的內(nèi)容.考慮數(shù)學(xué)競(jìng)賽的需要,下面介紹有關(guān)的基本內(nèi)容.

　　1. 同余式及其應(yīng)用

　　定義:設(shè)a、b、m為整數(shù)(m>0)，若a和b被m除得的余數(shù)相同，則稱(chēng)a和b對(duì)模m同余.記為 或 一切整數(shù)n可以按照某個(gè)自然數(shù)m作為除數(shù)的余數(shù)進(jìn)行分類(lèi)，即n=pm+r(r=0，1，…，m-1)，恰好m個(gè)數(shù)類(lèi).于是同余的概念可理解為,若對(duì)n1、n2，有n1=q1m+r，n2=q2m+r，那么n1、n2

　　對(duì)模m的同余，即它們用m除所得的余數(shù)相等.

　　利用整數(shù)的剩余類(lèi)表示,可以證明同余式的下述簡(jiǎn)單性質(zhì):

　　(1) 若 ,則m|(b-a).反過(guò)來(lái),若m|(b-a),則 ;

　　(2) 如果a=km+b(k為整數(shù)),則 ;

　　(3) 每個(gè)整數(shù)恰與0,1,…，m-1，這m個(gè)整數(shù)中的某一個(gè)對(duì)模m同余;

　　(4) 同余關(guān)系是一種等價(jià)關(guān)系：

　�、� 反身性 ;

　�、� 對(duì)稱(chēng)性 ，則 ，反之亦然.

　�、� 傳遞性 ， ，則 ;

　　(5)如果 ， ，則

　�、� ;

　�、� 特別地 應(yīng)用同余式的上述性質(zhì)，可以解決許多有關(guān)整數(shù)的問(wèn)題.

　　例1(1898年匈牙利奧林匹克競(jìng)賽題)求使2n+1能被3整除的一切自然數(shù)n.

　　解∵ ∴ 則2n+1 ∴當(dāng)n為奇數(shù)時(shí)，2n+1能被3整除;

　　當(dāng)n為偶數(shù)時(shí)，2n+1不能被3整除.

　　例2 求2999最后兩位數(shù)碼.

　　解 考慮用100除2999所得的余數(shù).

　　∵ ∴ 又 ∴ ∴ ∴2999的最后兩位數(shù)字為88.

　　例3 求證31980+41981能被5整除.

　　證明 ∵ ∴ ∴ ∴ 2.不定方程

　　不定方程的問(wèn)題主要有兩大類(lèi)：判斷不定方程有無(wú)整數(shù)解或解的個(gè)數(shù);如果不定方程有整數(shù)解，采取正確的方法，求出全部整數(shù)解.

　　(1) 不定方程解的判定

　　如果方程的兩端對(duì)同一個(gè)模m(常數(shù))不同余,顯然,這個(gè)方程必?zé)o整數(shù)解.而方程如有解則解必為奇數(shù)、偶數(shù)兩種，因而可以在奇偶性分析的基礎(chǔ)上應(yīng)用同余概念判定方程有無(wú)整數(shù)解.

　　例4 證明方程2x2-5y2=7無(wú)整數(shù)解.

　　證明 ∵2x2=5y2+7，顯然y為奇數(shù).

　　① 若x為偶數(shù)，則 ∴ ∵方程兩邊對(duì)同一整數(shù)8的余數(shù)不等，

　　∴x不能為偶數(shù).

　　② 若x為奇數(shù)，則 但5y2+7 ∴x不能為奇數(shù).因則原方程無(wú)整數(shù)解.

　　說(shuō)明:用整數(shù)的整除性來(lái)判定方程有無(wú)整數(shù)解,是我們解答這類(lèi)問(wèn)題的常用方法.

　　例5 (第14屆美國(guó)數(shù)學(xué)邀請(qǐng)賽題)不存在整數(shù)x,y使方程

　　①

　　證明 如果有整數(shù)x，y使方程①成立，

　　則 = 知(2x+3y2)+5能被17整除.

　　設(shè)2x+3y=17n+a，其中a是0，±1，±2，±3，±4，±5，±6，±7，±8中的某個(gè)數(shù)，但是這時(shí)(2x+3y)2+5=(17n)2+34na+(a2+5)=a2+5(mod17)，而a2+5被17整除得的余數(shù)分別是5，6，9，14，4，13，7，3，1，即在任何情況下(2x+3y)2+5都不能被17整除，這與它能被17整除矛盾.故不存在整數(shù)x，y使①成立.

　　例7 (第33屆美國(guó)數(shù)學(xué)競(jìng)賽題)滿(mǎn)足方程x2+y2=x3的正整數(shù)對(duì)(x，y)的個(gè)數(shù)是( ).

　　(A)0 (B)1(C)2(D)無(wú)限個(gè)(E)上述結(jié)論都不對(duì)

　　解由x2+y2=x3得y2=x2(x-1)，

　　所以只要x-1為自然數(shù)的平方，則方程必有正整數(shù)解.令x-1=k2(k為自然數(shù)),則 為方程的一組通解.由于自然數(shù)有無(wú)限多個(gè),故滿(mǎn)足方程的正整數(shù)對(duì)(x,y)有無(wú)限多個(gè),應(yīng)選(D).

　　說(shuō)明:可用寫(xiě)出方程的一組通解的方法,判定方程有無(wú)數(shù)個(gè)解.