數(shù)學(xué)競(jìng)賽講座第三輯同余式與不定方程

1、競(jìng)賽講座03-同余式與不定方程同余式和不定方程是數(shù)論中古老而富有魅力的內(nèi)容.考慮數(shù)學(xué)競(jìng)賽的需要,下面介紹有關(guān)的基本內(nèi)容.1.       同余式及其應(yīng)用定義:設(shè)a、b、m為整數(shù)（m0），若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ì)n1、n2，有n1=q1m+r，n2=q2m+r，那么n1、n2對(duì)模m的同余，即它們用m除所得的余數(shù)相等.利用整數(shù)的剩余類表示,可以證明同余式的下述簡(jiǎn)單性質(zhì):(1)

2、    若,則m|(b-a).反過來,若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ì)，可以解決

3、許多有關(guān)整數(shù)的問題.例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不定方程不定方程的問題主要有兩大類：判斷不定方程有無

4、整數(shù)解或解的個(gè)數(shù)；如果不定方程有整數(shù)解，采取正確的方法，求出全部整數(shù)解.(1)    不定方程解的判定如果方程的兩端對(duì)同一個(gè)模m(常數(shù))不同余,顯然,這個(gè)方程必?zé)o整數(shù)解.而方程如有解則解必為奇數(shù)、偶數(shù)兩種，因而可以在奇偶性分析的基礎(chǔ)上應(yīng)用同余概念判定方程有無整數(shù)解.例4         證明方程2x2-5y2=7無整數(shù)解.證明  2x2=5y2+7，顯然y為奇數(shù).     若x為偶數(shù)，則方程兩邊對(duì)同一整數(shù)8的余數(shù)不等，x不能為偶數(shù).&#

5、160;    若x為奇數(shù)，則但5y2+7x不能為奇數(shù).因則原方程無整數(shù)解.說明:用整數(shù)的整除性來判定方程有無整數(shù)解,是我們解答這類問題的常用方法.例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，

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)賽題）滿足方程x2+y2=x3的正整數(shù)對(duì)（x，y）的個(gè)數(shù)是（   ）.（A）0 （B）1（C）2（D）無限個(gè)（E）上述結(jié)論都不對(duì)解由x2+y2=x3得y2=x2（x-1），所以只要x-1為自然數(shù)的平方，則方程必有正整數(shù)解.令x-1=k2(k為自然數(shù)),則為

7、方程的一組通解.由于自然數(shù)有無限多個(gè),故滿足方程的正整數(shù)對(duì)(x,y)有無限多個(gè),應(yīng)選(D).說明:可用寫出方程的一組通解的方法,判定方程有無數(shù)個(gè)解.(2)    不定方程的解法不定方程沒有統(tǒng)一的解法,常用的特殊方法有:配方法、因式（質(zhì)因數(shù)）分解法、不等式法、奇偶分析法和余數(shù)分析法.對(duì)方程進(jìn)行適當(dāng)?shù)淖冃?并正確應(yīng)用整數(shù)的性質(zhì)是解不定方程的基本思路.例6         求方程的整數(shù)解.解(配方法)原方程配方得(x-2y)2+y2=132.在勾股數(shù)中,最大的一個(gè)為13的只有一組即5,12,

8、13,因此有8對(duì)整數(shù)的平方和等于132即(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滿足方程a2+b2=c2.證明:這時(shí)有ab及b+1=c.證明（因式分解法）a2+b2=c2，a2=（c-b）（c+b），又a為素?cái)?shù)，c-b=1，

9、且c+b=a2.于是得c=b+1及a2=b+c=2b+13b，即.而a3,1，1.ab.例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,b1=2,b2=22.從而得a1=21,a2=1.故滿足聯(lián)立方程的正整數(shù)組(a,b,

10、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=x2-xy+y2的整數(shù)解.解（不等式法）方程有整數(shù)解  必須=（y+1）2-4（y2-y）0，解得y.滿足這個(gè)不等式的整數(shù)只有y=0，1，2.當(dāng)y=0時(shí)，由原方程可得x=0或x=1；當(dāng)y=1時(shí)，由原方程可得

11、x=2或0；當(dāng)y=2時(shí)，由原方程可得x=1或2.所以方程有整數(shù)解最后我們來看兩個(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)賽題）滿足0xy及的不同的整數(shù)對(duì)（x，y）的個(gè)數(shù)是（   ）.（A）0

12、0; （B）1  （C）3  （D）4  （E）7解法1 根據(jù)題意知，0x1984，由得   當(dāng)且僅當(dāng)1984x是完全平方數(shù)時(shí)，y是整數(shù).而1984=26·31，故當(dāng)且僅當(dāng)x具有31t2形式時(shí)，1984x是完全平方數(shù).x1984，1t7.當(dāng)t=1，2，3時(shí)，得整數(shù)對(duì)分別為（31，1519）、（124，1116）和（279，775）.當(dāng)t3時(shí)yx不合題意，因此不同的整數(shù)對(duì)的個(gè)數(shù)是3，故應(yīng)選（C）.解法2 1984=由此可知：x必須具有31t2形式，y必須具有31k2形式，并且t+k=8（t，k均為正整數(shù)）.因?yàn)?xy，所以tk.當(dāng)t=1

13、，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)方程x2-y2=105的正整數(shù)解有(   ).（A）      一組 （B）二組  （C）三組  （D）四組(2)在0,1,2,，50這51個(gè)整數(shù)中，能同時(shí)被2，3，4整除的有（   ）.（A）     

14、 3個(gè) （B）4個(gè)  （C）5個(gè)  （D）6個(gè)2填空題（1）的個(gè)位數(shù)分別為_及_.(2)滿足不等式104A105的整數(shù)A的個(gè)數(shù)是x×104+1，則x的值_.(3)    已知整數(shù)y被7除余數(shù)為5,那么y3被7除時(shí)余數(shù)為_.(4)    (全俄第14屆中學(xué)生數(shù)學(xué)競(jìng)賽試題)求出任何一組滿足方程x2-51y2=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ù)，而不是

15、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ù)，并且p1，q1，試求p+q的值. 練習(xí)二十1.D.C.2.(1)9及1.     (2)9.    (3)4.(4)原方程可變形為x2=(7y+1)2+2y(y-7)

16、,令y=7可得x=50.3.不妨設(shè)xyz,則,故x3.又有故x2.若x=2,則,故y6.又有,故y4.若y=4,則z=20.若y=5,則z=10.若y=6,則z無整數(shù)解.若x=3,類似可以確定3y4,y=3或4,z都不能是整數(shù).4.可仿例2解.5.先求出,然后將方程變形為y=5+x-2要使y為整數(shù),5x-1應(yīng)是完全平方數(shù),解得6.88888(mod37),8888222282(mod37).77777(mod37),7777333373(mod37),88882222+77773333(82+73)(mod37),而82+73=407,37|407,37|N.7.簡(jiǎn)解:原方程變形為3x2-(3y+7)x+3y2-7y=0