數(shù)學(xué)奧林匹克競(jìng)賽講座 03同余式與不定方程

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ù)相同，則稱(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)

2、,若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

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ù)

4、不同余,顯然,這個(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+7x不能為奇數(shù).因則原方程無(wú)整數(shù)解.說(shuō)明:用整數(shù)的整除性來(lái)判定方程有無(wú)整數(shù)解,是我們解答這類(lèi)問(wèn)題

5、的常用方法.例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，1

6、3，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è)解.(2  

7、;  不定方程的解法不定方程沒(méi)有統(tǒng)一的解法,常用的特殊方法有:配方法、因式（質(zhì)因數(shù)）分解法、不等式法、奇偶分析法和余數(shù)分析法.對(duì)方程進(jìn)行適當(dāng)?shù)淖冃?并正確應(yīng)用整數(shù)的性質(zhì)是解不定方程的基本思路.例6  求方程的整數(shù)解.解(配方法原方程配方得(x-2y2+y2=132.在勾股數(shù)中,最大的一個(gè)為13的只有一組即5,12,13,因此有8對(duì)整數(shù)的平方和等于132       解得  例7         (原民主德國(guó)1982年中學(xué)生競(jìng)賽題已知兩個(gè)

8、自然數(shù)b和c及素?cái)?shù)a滿(mǎn)足方程a2+b2=c2.證明:這時(shí)有ab及b+1=c.證明（因式分解法）a2+b2=c2，a2=（c-b）（c+b），又a為素?cái)?shù)，c-b=1，且c+b=a2.于是得c=b+1及a2=b+c=2b+13b，即.而a3,1，1.ab.例9（第35屆美國(guó)中學(xué)數(shù)學(xué)競(jìng)賽題）滿(mǎn)足聯(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代

9、入方程ab+bc=44得(23-bb+b=44,即(b-2(b-22=0,b1=2,b2=22.從而得a1=21,a2=1.故滿(mǎn)足聯(lián)立方程的正整數(shù)組(a,b,c有兩個(gè),即(21,2,1和(1,22,1,應(yīng)選(C.例10求不定方程2(x+y=xy+7的整數(shù)解.解 由(y-2x=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ù)解  必須

10、=（y+1）2-4（y2-y）0，解得y.滿(mǎn)足這個(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  求滿(mǎn)足方程且使y是最大的正整數(shù)解（x，y）.解將原方程變形得由此式可知，只有12-x是正的且最小時(shí)，y才能取大值.又12-x應(yīng)是144的約數(shù)，所以，12-x=1，x=11，這時(shí)y=132.故  滿(mǎn)足題設(shè)的方程的正整數(shù)解為（x，y）=（11，132）.例13（第35屆美國(guó)中學(xué)生數(shù)學(xué)競(jìng)賽題）滿(mǎn)足0xy及的不同的

11、整數(shù)對(duì)（x，y）的個(gè)數(shù)是（   ）.（A）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

12、+k=8（t，k均為正整數(shù)）.因?yàn)?xy，所以tk.當(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方程x2-y2=105的正整數(shù)解有(   .（A）      一組 （B）二組  （C）三組  （D）四組(2在0,1,2,，50這51個(gè)整數(shù)中，能同時(shí)被2，3，4整除的有（   ）.（A）    

13、0; 3個(gè) （B）4個(gè)  （C）5個(gè)  （D）6個(gè)2填空題（1）的個(gè)位數(shù)分別為_(kāi)及_.(2滿(mǎn)足不等式104A105的整數(shù)A的個(gè)數(shù)是x×104+1，則x的值_.(3    已知整數(shù)y被7除余數(shù)為5,那么y3被7除時(shí)余數(shù)為_(kāi).(4    (全俄第14屆中學(xué)生數(shù)學(xué)競(jìng)賽試題求出任何一組滿(mǎn)足方程x2-51y2=1的自然數(shù)解x和y_.3.(第26屆國(guó)際數(shù)學(xué)競(jìng)賽預(yù)選題求三個(gè)正整數(shù)x、y、z滿(mǎn)足.4（1985年上海數(shù)學(xué)競(jìng)賽題）在數(shù)列4，8，17，77，97，106，125，238中相鄰若干個(gè)數(shù)之和是3的倍數(shù)，而不是9的倍

14、數(shù)的數(shù)組共有多少組？5求的整數(shù)解.6求證可被37整除.7（全俄1986年數(shù)學(xué)競(jìng)賽題）求滿(mǎn)足條件的整數(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.(19及1.     (29.    (34.(4原方程可變形為x2=(7y+12+2y(y-7,令y=7可得x=50.3.不妨設(shè)xyz,則故x2.若x=2,則,故y4.若y=4,則z=20.若y=5,則z=10.若y=6,則z無(wú)整數(shù)解.若x=3,類(lèi)似可以確定3y4,y=3或4,z都不能是整數(shù).4.可仿例2解.,然后將方程變形為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-(