同余式與不定方程

同余式和不定方程是數(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ù)相同，則稱a和b對(duì)模m同余.記為或

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

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

利用整數(shù)的剩余類表示,可以證明同余式的下述簡(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ì)稱性，則，反之亦然.

③     傳遞性，，則；

（5）如果，，則

①；

②特別地

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

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

解∵  ∴

則2ⁿ+1

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

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

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

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

∵

∴

又

∴

∴

∴2⁹⁹⁹的最后兩位數(shù)字為88.

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

證明  ∵

∴

∴

∴

2．不定方程

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

(1)    不定方程解的判定

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

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

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

①     若x為偶數(shù)，則

∴

∵方程兩邊對(duì)同一整數(shù)8的余數(shù)不等，

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

②     若x為奇數(shù)，則

但5y²+7

∴x不能為奇數(shù).因則原方程無(wú)整數(shù)解.

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

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

   ①

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

則

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

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

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

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

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

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

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

(2)    不定方程的解法

不定方程沒(méi)有統(tǒng)一的解法,常用的特殊方法有:配方法、因式（質(zhì)因數(shù)）分解法、不等式法、奇偶分析法和余數(shù)分析法.對(duì)方程進(jìn)行適當(dāng)?shù)淖冃?并正確應(yīng)用整數(shù)的性質(zhì)是解不定方程的基本思路.

例6         求方程的整數(shù)解.

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

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

解得

例7         (原民主德國(guó)1982年中學(xué)生競(jìng)賽題)已知兩個(gè)自然數(shù)b和c及素?cái)?shù)a滿足方程a²+b²=c².證明:這時(shí)有a＜b及b+1=c.

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

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

又∵a為素?cái)?shù)，∴c-b=1，且c+b=a².

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

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

例9（第35屆美國(guó)中學(xué)數(shù)學(xué)競(jìng)賽題）滿足聯(lián)立方程

的正整數(shù)（a，b，c）的組數(shù)是（   ）.

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

解（質(zhì)因數(shù)分解法）由方程ac+bc=23得

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

∵a，b，c為正整數(shù)，∴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.故滿足聯(lián)立方程的正整數(shù)組(a,b,c)有兩個(gè),即(21,2,1)和(1,22,1),應(yīng)選(C).

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

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

分離整數(shù)部分得

由x為整數(shù)知y-2是3的因數(shù),

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

∴方程整數(shù)解為

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

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

≤y≤.

滿足這個(gè)不等式的整數(shù)只有y=0，1，2.

當(dāng)y=0時(shí)，由原方程可得x=0或x=1；當(dāng)y=1時(shí)，由原方程可得x=2或0；當(dāng)y=2時(shí)，由原方程可得x=1或2.

所以方程有整數(shù)解

最后我們來(lái)看兩個(gè)分式和根式不定方程的例子.

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

解將原方程變形得

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

12-x=1，x=11，這時(shí)y=132.

故  滿足題設(shè)的方程的正整數(shù)解為

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

例13（第35屆美國(guó)中學(xué)生數(shù)學(xué)競(jìng)賽題）滿足0＜x＜y及的不同的整數(shù)對(duì)（x，y）的個(gè)數(shù)是（   ）.

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

解法1 根據(jù)題意知，0＜x＜1984，由

得  

當(dāng)且僅當(dāng)1984x是完全平方數(shù)時(shí)，y是整數(shù).而1984=2⁶·31，故當(dāng)且僅當(dāng)x具有31t²形式時(shí)，1984x是完全平方數(shù).

∵x＜1984，∵1≤t≤7.當(dāng)t=1，2，3時(shí)，得整數(shù)對(duì)分別為（31，1519）、（124，1116）和（279，775）.當(dāng)t＞3時(shí)y≤x不合題意，因此不同的整數(shù)對(duì)的個(gè)數(shù)是3，故應(yīng)選（C）.

解法2 ∵1984=∴由此可知：x必須具有31t²形式，y必須具有31k²形式，并且t+k=8（t，k均為正整數(shù)）.因?yàn)?＜x＜y，所以t＜k.當(dāng)t=1，k=7時(shí)得（31，1519）；t=2，k=6時(shí)得（124，1116）；當(dāng)t=3，k=5時(shí)得（279，775）.因此不同整數(shù)對(duì)的個(gè)數(shù)為3.

練習(xí)二十

1.       選擇題

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

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

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

（A）      3個(gè) （B）4個(gè)  （C）5個(gè)  （D）6個(gè)

2．填空題

（1）的個(gè)位數(shù)分別為_(kāi)________及_________.

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

(3)    已知整數(shù)y被7除余數(shù)為5,那么y³被7除時(shí)余數(shù)為_(kāi)_______.

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

3.(第26屆國(guó)際數(shù)學(xué)競(jìng)賽預(yù)選題)求三個(gè)正整數(shù)x、y、z滿足

.

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

5．求的整數(shù)解.

6．求證可被37整除.

7．（全俄1986年數(shù)學(xué)競(jìng)賽題）求滿足條件的整數(shù)x，y的所有可能的值.

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

9.(1988年全國(guó)初中數(shù)學(xué)競(jìng)賽題)如果p、q、、都是整數(shù)，并且p＞1，q＞1，試求p+q的值.

練習(xí)二十

1.D.C.

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

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

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

4.可仿例2解.

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

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

8.∵l²+m²=n²,∴l²=(n+m)(n-m).∵l為質(zhì)數(shù),且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)是完全平方數(shù).

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