--同余式與不定方程

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

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

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

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

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

　　(1) 若 ,則m|(b-a).反過來,若m|(b-a),則 ;

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

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

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

　�、� 反身性 ;

　�、� 對稱性 ，則 ，反之亦然.

　�、� 傳遞性 ， ，則 ;

　　(5)如果 ， ，則

　�、� ;

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

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

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

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

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

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

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

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

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

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

　　(1) 不定方程解的判定

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

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

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

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

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

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

　　說明:用整數(shù)的整除性來判定方程有無整數(shù)解,是我們解答這類問題的常用方法.

　　例5 (第14屆美國數(shù)學(xué)邀請賽題)不存在整數(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中的某個數(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屆美國數(shù)學(xué)競賽題)滿足方程x2+y2=x3的正整數(shù)對(x，y)的個數(shù)是( ).

　　(A)0 (B)1(C)2(D)無限個(E)上述結(jié)論都不對

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

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

　　說明:可用寫出方程的一組通解的方法,判定方程有無數(shù)個解.