同余式與不定方程

同余式和不定方程是數論中古老而富有魅力的內容.考慮數學競賽的需要,下面介紹有關的基本內容.

1.       同余式及其應用

定義:設a、b、m為整數（m＞0），若a和b被m除得的余數相同，則稱a和b對模m同余.記為或

一切整數n可以按照某個自然數m作為除數的余數進行分類，即n=pm+r（r=0，1，…，m-1），恰好m個數類.于是同余的概念可理解為,若對n₁、n₂，有n₁=q₁m+r，n₂=q₂m+r，那么n₁、n₂

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

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

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

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

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

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

①     反身性  ；

②     對稱性，則，反之亦然.

③     傳遞性，，則；

（5）如果，，則

①；

②特別地

應用同余式的上述性質，可以解決許多有關整數的問題.

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

解∵  ∴

則2ⁿ+1

∴當n為奇數時，2ⁿ+1能被3整除；

當n為偶數時，2ⁿ+1不能被3整除.

例2         求2⁹⁹⁹最后兩位數碼.

解 考慮用100除2⁹⁹⁹所得的余數.

∵

∴

又

∴

∴

∴2⁹⁹⁹的最后兩位數字為88.

例3         求證3¹⁹⁸⁰+4¹⁹⁸¹能被5整除.

證明  ∵

∴

∴

∴

2．不定方程

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

(1)    不定方程解的判定

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

例4         證明方程2x²-5y²=7無整數解.

證明  ∵2x²=5y²+7，顯然y為奇數.

①     若x為偶數，則

∴

∵方程兩邊對同一整數8的余數不等，

∴x不能為偶數.

②     若x為奇數，則

但5y²+7

∴x不能為奇數.因則原方程無整數解.

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

例5         (第14屆美國數學邀請賽題)不存在整數x,y使方程

   ①

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

則

=知（2x+3y²）+5能被17整除.

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

例7  （第33屆美國數學競賽題）滿足方程x²+y²=x³的正整數對（x，y）的個數是（   ）.

（A）0 （B）1（C）2（D）無限個（E）上述結論都不對

解由x²+y²=x³得y²=x²（x-1），

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

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

(2)    不定方程的解法

不定方程沒有統一的解法,常用的特殊方法有:配方法、因式（質因數）分解法、不等式法、奇偶分析法和余數分析法.對方程進行適當的變形,并正確應用整數的性質是解不定方程的基本思路.

例6         求方程的整數解.

解(配方法)原方程配方得(x-2y)²+y²=13².

在勾股數中,最大的一個為13的只有一組即5,12,13,因此有8對整數的平方和等于13²即(5,12),(12,5),(-5,-12),(-12,-5),(5-,12),(12,-5),(-5,12),(-12,5).故原方程組的解只能是下面的八個方程組的解

解得

例7         (原民主德國1982年中學生競賽題)已知兩個自然數b和c及素數a滿足方程a²+b²=c².證明:這時有a＜b及b+1=c.

證明（因式分解法）∵a²+b²=c²，

∴a²=（c-b）（c+b），

又∵a為素數，∴c-b=1，且c+b=a².

于是得c=b+1及a²=b+c=2b+1＜3b，

即＜.而a≥3,∴≤1，∴＜1.∴a＜b.

例9（第35屆美國中學數學競賽題）滿足聯立方程

的正整數（a，b，c）的組數是（   ）.

（A）0  （B）1  （C）2  （D）3  （E）4

解（質因數分解法）由方程ac+bc=23得

（a+b）c=23=1×23.

∵a，b，c為正整數，∴c=1且a+b=23.將c和a=23-b代入方程ab+bc=44得

(23-b)b+b=44,即(b-2)(b-22)=0,

∴b₁=2,b₂=22.從而得a₁=21,a₂=1.故滿足聯立方程的正整數組(a,b,c)有兩個,即(21,2,1)和(1,22,1),應選(C).

例10求不定方程2(x+y)=xy+7的整數解.

解 由(y-2)x=2y-7,得

分離整數部分得

由x為整數知y-2是3的因數,

∴y-2=±1，±3，∴x=3，5，±1.

∴方程整數解為

例11         求方程x+y=x²-xy+y²的整數解.

解（不等式法）方程有整數解  必須△=（y+1）²-4（y²-y）≥0，解得

≤y≤.

滿足這個不等式的整數只有y=0，1，2.

當y=0時，由原方程可得x=0或x=1；當y=1時，由原方程可得x=2或0；當y=2時，由原方程可得x=1或2.

所以方程有整數解

最后我們來看兩個分式和根式不定方程的例子.

例12         求滿足方程且使y是最大的正整數解（x，y）.

解將原方程變形得

由此式可知，只有12-x是正的且最小時，y才能取大值.又12-x應是144的約數，所以，

12-x=1，x=11，這時y=132.

故  滿足題設的方程的正整數解為

（x，y）=（11，132）.

例13（第35屆美國中學生數學競賽題）滿足0＜x＜y及的不同的整數對（x，y）的個數是（   ）.

（A）0  （B）1  （C）3  （D）4  （E）7

解法1 根據題意知，0＜x＜1984，由

得  

當且僅當1984x是完全平方數時，y是整數.而1984=2⁶·31，故當且僅當x具有31t²形式時，1984x是完全平方數.

∵x＜1984，∵1≤t≤7.當t=1，2，3時，得整數對分別為（31，1519）、（124，1116）和（279，775）.當t＞3時y≤x不合題意，因此不同的整數對的個數是3，故應選（C）.

解法2 ∵1984=∴由此可知：x必須具有31t²形式，y必須具有31k²形式，并且t+k=8（t，k均為正整數）.因為0＜x＜y，所以t＜k.當t=1，k=7時得（31，1519）；t=2，k=6時得（124，1116）；當t=3，k=5時得（279，775）.因此不同整數對的個數為3.

練習二十

1.       選擇題

(1)方程x²-y²=105的正整數解有(   ).

（A）      一組 （B）二組  （C）三組  （D）四組

(2)在0,1,2,…，50這51個整數中，能同時被2，3，4整除的有（   ）.

（A）      3個 （B）4個  （C）5個  （D）6個

2．填空題

（1）的個位數分別為_________及_________.

(2)滿足不等式10⁴≤A≤10⁵的整數A的個數是x×10⁴+1，則x的值________.

(3)    已知整數y被7除余數為5,那么y³被7除時余數為________.

(4)    (全俄第14屆中學生數學競賽試題)求出任何一組滿足方程x²-51y²=1的自然數解x和y_________.

3.(第26屆國際數學競賽預選題)求三個正整數x、y、z滿足

.

4．（1985年上海數學競賽題）在數列4，8，17，77，97，106，125，238中相鄰若干個數之和是3的倍數，而不是9的倍數的數組共有多少組？

5．求的整數解.

6．求證可被37整除.

7．（全俄1986年數學競賽題）求滿足條件的整數x，y的所有可能的值.

8．（1985年上海初中數學競賽題）已知直角三角形的兩直角邊長分別為l厘米、m厘米，斜邊長為n厘米，且l，m，n均為正整數，l為質數.證明：2（l+m+n）是完全平方數.

9.(1988年全國初中數學競賽題)如果p、q、、都是整數，并且p＞1，q＞1，試求p+q的值.

練習二十

1.D.C.

2.(1)9及1.     (2)9.    (3)4.

(4)原方程可變形為x²=(7y+1)²+2y(y-7),令y=7可得x=50.

3.不妨設x≤y≤z,則,故x≤3.又有故x≥2.若x=2,則,故y≤6.又有,故y≥4.若y=4,則z=20.若y=5,則z=10.若y=6,則z無整數解.若x=3,類似可以確定3≤y≤4,y=3或4,z都不能是整數.

4.可仿例2解.

5.先求出,然后將方程變形為y=5+x-2要使y為整數,5x-1應是完全平方數,…,解得

6.8888≡8(mod37),∴8888²²²²≡8²(mod37).

7777≡7(mod37),7777³³³³≡7³(mod37),8888²²²²+7777³³³³≡(8²+7³)(mod37),而8²+7³=407,37|407,∴37|N.

7.簡解:原方程變形為3x²-(3y+7)x+3y²-7y=0由關于x的二次方程有解的條件△≥0及y為整數可得0≤y≤5,即y=0,1,2,3,4,5.逐一代入原方程可知,原方程僅有兩組解(4,5)、(5,4).

8.∵l²+m²=n²,∴l²=(n+m)(n-m).∵l為質數,且n+m＞n-m＞0,∴n+m=l²,n-m=1.于是l²=n+m=(m+1)+m=2m+1,2m=l²-1,2(l+m+1)=2l+2+2m=l²+2l+1=(l+1)².即2(l+m+1)是完全平方數.

9.易知p≠q,不妨設p＞q.令=n,則m＞n由此可得不定方程(4-mn)p=m+2,解此方程可得p、q之值.