大學(xué)初等數(shù)論

800門大學(xué)各類科目考試資料，盡在微信公眾號：大學(xué)資源庫，備用公眾號：大學(xué)學(xué)習(xí)庫，微信：snsgkf不定方程所謂不定方程，是指未知數(shù)的個數(shù)多于方程個數(shù)，且未知數(shù)受到某些（如要求是有理數(shù)、整數(shù)或正整數(shù)等等）的方程或方程組。不定方程也稱為丟番圖方程，是數(shù)論的重要分支學(xué)科，也是歷史上最活躍的數(shù)學(xué)領(lǐng)域之一。不定方程的內(nèi)容十分豐富，與代數(shù)數(shù)論、幾何數(shù)論、集合數(shù)論等等都有較為密切的聯(lián)系。不定方程的重要性在數(shù)學(xué)競賽中也得到了充分的體現(xiàn)，每年世界各地的數(shù)學(xué)競賽吉，不定方程都占有一席之地；另外它也是培養(yǎng)學(xué)生思維能力的好材料，數(shù)學(xué)競賽中的不定方程問題，不僅要求學(xué)生對初等數(shù)論的一般理論、方法有一定的了解，而且更需要講究思想、方法與技巧，創(chuàng)造性的解決問題。在本節(jié)我們來看一看不定方程的基礎(chǔ)性的題目?；A(chǔ)知識1．不定方程問題的常見類型：（1）求不定方程的解；（2）判定不定方程是否有解；（3）判定不定方程的解的個數(shù)（有限個還是無限個）。2．解不定方程問題常用的解法：（1）代數(shù)恒等變形：如因式分解、配方、換元等；（2）不等式估算法：利用不等式等方法，確定出方程中某些變量的范圍，進(jìn)而求解；（3）同余法：對等式兩邊取特殊的模（如奇偶分析），縮小變量的范圍或性質(zhì)，得出不定方程的整數(shù)解或判定其無解；（4）構(gòu)造法：構(gòu)造出符合要求的特解，或構(gòu)造一個求解的遞推式，證明方程有無窮多解；（5）無窮遞推法。以下給出幾個關(guān)于特殊方程的求解定理：（一）二元一次不定方程（組）定義1.形如(不同時為零)的方程稱為二元一次不定方程。定理1.方程有解的充要是；定理2.若，且為的一個解，則方程的一切解都可以表示成為任意整數(shù))。定理3.元一次不定方程，()有解的充要條件是.方法與技巧：1．解二元一次不定方程通常先判定方程有無解。若有解，可先求一個特解，從而寫出通解。當(dāng)不定方程系數(shù)不大時，有時可以通過觀察法求得其解，即引入變量，逐漸減小系數(shù)，直到容易得其特解為止；2．解元一次不定方程時，可先順次求出，……，.若，則方程無解；若|，則方程有解，作方程組：求出最后一個方程的一切解，然后把的每一個值代入倒數(shù)第二個方程，求出它的一切解，這樣下去即可得方程的一切解。3．個元一次不定方程組成的方程組，其中，可以消去個未知數(shù)，從而消去了個不定方程，將方程組轉(zhuǎn)化為一個元的一次不定方程。（二）高次不定方程（組）及其解法1．因式分解法：對方程的一邊進(jìn)行因式分解，另一邊作質(zhì)因式分解，然后對比兩邊，轉(zhuǎn)而求解若干個方程組；2．同余法：如果不定方程有整數(shù)解，則對于任意，其整數(shù)解滿足，利用這一條件，同余可以作為探究不定方程整數(shù)解的一塊試金石；3．不等式估計法：利用不等式工具確定不定方程中某些字母的范圍，再分別求解；4．無限遞降法：若關(guān)于正整數(shù)的命題對某些正整數(shù)成立，設(shè)是使成立的最小正整數(shù)，可以推出：存在，使得成立，適合證明不定方程無正整數(shù)解。方法與技巧：1．因式分解法是不定方程中最基本的方法，其理論基礎(chǔ)是整數(shù)的唯一分解定理，分解法作為解題的一種手段，沒有因定的程序可循，應(yīng)具體的例子中才能有深刻地體會；2．同余法主要用于證明方程無解或?qū)С鲇薪獾谋匾獥l件，為進(jìn)一步求解或求證作準(zhǔn)備。同余的關(guān)鍵是選擇適當(dāng)?shù)哪＃枰?jīng)過多次嘗試；3．不等式估計法主要針對方程有整數(shù)解，則必然有實數(shù)解，當(dāng)方程的實數(shù)解為一個有界集，則著眼于一個有限范圍內(nèi)的整數(shù)解至多有有限個，逐一檢驗，求出全部解；若方程的實數(shù)解是無界的，則著眼于整數(shù)，利用整數(shù)的各種性質(zhì)產(chǎn)生適用的不等式；4．無限遞降法論證的核心是設(shè)法構(gòu)造出方程的新解，使得它比已選擇的解“嚴(yán)格地小”，由此產(chǎn)生矛盾。（三）特殊的不定方程1．利用分解法求不定方程整數(shù)解的基本思路：將轉(zhuǎn)化為后，若可分解為，則解的一般形式為，再取舍得其整數(shù)解；2．定義2：形如的方程叫做勾股數(shù)方程，這里為正整數(shù)。對于方程，如果，則，從而只需討論的情形，此時易知兩兩互素，這種兩兩互素的正整數(shù)組叫方程的本原解。定理3.勾股數(shù)方程滿足條件的一切解可表示為：，其中且為一奇一偶。推論：勾股數(shù)方程的全部正整數(shù)解（的順序不加區(qū)別）可表示為：其中是互質(zhì)的奇偶性不同的一對正整數(shù)，是一個整數(shù)。

勾股數(shù)不定方程的整數(shù)解的問題主要依據(jù)定理來解決。3．定義3.方程且不是平方數(shù))是的一種特殊情況，稱為沛爾(Pell)方程。這種二元二次方程比較復(fù)雜，它們本質(zhì)上歸結(jié)為雙曲線方程的研究，其中都是整數(shù)，且非平方數(shù)，而。它主要用于證明問題有無數(shù)多個整數(shù)解。對于具體的可用嘗試法求出一組成正整數(shù)解。如果上述pell方程有正整數(shù)解，則稱使的最小的正整數(shù)解為它的最小解。定理4.Pell方程且不是平方數(shù))必有正整數(shù)解，且若設(shè)它的最小解為，則它的全部解可以表示成：.上面的公式也可以寫成以下幾種形式：（1）；（2）；（3）.定理5.Pell方程且不是平方數(shù))要么無正整數(shù)解，要么有無窮多組正整數(shù)解，且在后一種情況下，設(shè)它的最小解為，則它的全部解可以表示為定理6.（費(fèi)爾馬（Fermat）大定理）方程為整數(shù))無正整數(shù)解。費(fèi)爾馬（Fermat）大定理的證明一直以來是數(shù)學(xué)界的難題，但是在1994年6月，美國普林斯頓大學(xué)的數(shù)學(xué)教授A.Wiles完全解決了這一難題。至此，這一困擾了人們四百多年的數(shù)學(xué)難題終于露出了廬山真面目，脫去了其神秘面紗。典例分析例1．求不定方程的整數(shù)解。解：先求的一組特解，為此對37，107運(yùn)用輾轉(zhuǎn)相除法：，，將上述過程回填，得：由此可知，是方程的一組特解，于是，是方程的一組特解，因此原方程的一

切整數(shù)解為：。例2．求不定方程的所有正整數(shù)解。解：用原方程中的最小系數(shù)7去除方程的各項，并移項得：因為是整數(shù)，故也一定是整數(shù)，于是有，再用5去除比式的兩邊，得，令為整數(shù)，由此得。經(jīng)觀察得是最后一個方程的一組解，依次回代，可求得原方程的一組特解：，所以原方程的一切整數(shù)解為：。例3．求不定方程的正整數(shù)解。解：顯然此方程有整數(shù)解。先確定系數(shù)最大的未知數(shù)的取值范圍，因為的最小值為1，所以。當(dāng)時，原方程變形為，即，由上式知是偶數(shù)且故方程組有5組正整數(shù)解，分別為，，，，；當(dāng)時，原方程變形為，即，故方程有3組正整數(shù)解，分別為：，，；當(dāng)時，原方程變形為，即，故方程有2組正整數(shù)解，分別為：，；當(dāng)時，原方程變形為，即，故方程只有一組正整數(shù)解，為。故原方程有11組正整數(shù)解（如下表）：246810246242131074196352111111222334例4．求出方程的所有正整數(shù)解。解：先求最小解。令當(dāng)時，；當(dāng)時，；當(dāng)時，。所以的最小解為，于是：例5．在直角坐標(biāo)平面上，以（199，0）為圓心，以199為半徑的圓周上的整點(diǎn)的個數(shù)為多少個？解：設(shè)為圓上任一整點(diǎn)，則其方程為：；顯然為方程的4組解。但當(dāng)時，（因為199是質(zhì)數(shù)），此時，是一組勾股數(shù)，故199可表示為兩個正整數(shù)的平方和，即。因為，可設(shè)，則這與199為型的質(zhì)數(shù)矛盾！因而圓O上只有四個整點(diǎn)。例6．求所有滿足的正整數(shù)三元組。解：兩邊取，得，所以是偶數(shù)，再得，所以也是偶數(shù)。此時令于是，由可知：；由唯一分解定理：，，從而注意到17是奇數(shù)，所以要使成立，一定有。于是。當(dāng)時，在的兩邊取，得，這顯然是不成立的，所以，從而。故方程只有唯一的一組解（2，2，2）。例7．是一個給定的整數(shù)，當(dāng)為何值時，的方程有正整數(shù)解？在有正整數(shù)解時，求解該不定方程。解；若有質(zhì)數(shù)，，則，從而，矛盾！所以。因此當(dāng)且僅當(dāng)。因為，顯然，所以當(dāng)且僅當(dāng)。（*）（1）若時，，所以或，或；（2）類似地，若，則，所以或，或；（3）由于條件（*），不妨設(shè)；

若，則，所以；

若，則因為，所以存在，使得：，所以，。因為，所以必有。所以，故所以，所以或當(dāng)時，；當(dāng)時，，對應(yīng)的為1或2。由條件（*）知以及也是原方程的解，對應(yīng)的整數(shù)為14或9。綜上，當(dāng)時原方程有整數(shù)解，它們分別是：（3，1），（5，2）；（2，1），（5，3），（2，2）；（1，2），（3，5）；（1，3），（2，5）。例8．求證：邊長為整數(shù)的直角三角形的面積不可能是完全平方數(shù)。證明：假設(shè)結(jié)論不成立，在所有的面積為平方數(shù)勾股三角形中選取一個面積最小的，設(shè)其邊長為，則是平方數(shù)，則必有。因為，故存在整數(shù)中一奇一偶，，使得（不妨設(shè)是偶數(shù)）。由于是完全平方數(shù)，而知兩兩互素，故它們是平方數(shù)，即，所以即因為是奇數(shù)，易知，于是與中有一個是，另一個是，而；另一方面，得所以，以為邊的三角形都是直角三角形，其面積等于是平方數(shù)，但是，于是構(gòu)造出了一個面積更小的勾股三角形，矛盾！初等數(shù)論中的幾個重要定理基礎(chǔ)知識定義（歐拉(Euler)函數(shù)）一組數(shù)稱為是模的既約剩余系，如果對任意的，且對于任意的，若＝1，則有且僅有一個是對模的剩余，即。并定義中和互質(zhì)的數(shù)的個數(shù)，稱為歐拉（Euler）函數(shù)。這是數(shù)論中的非常重要的一個函數(shù)，顯然，而對于，就是1,2，…，中與互素的數(shù)的個數(shù)，比如說是素數(shù)，則有。引理：；可用容斥定理來證（證明略）。定理1：（歐拉（Euler）定理）設(shè)＝1，則。分析與解答：要證，我們得設(shè)法找出個相乘，由個數(shù)我們想到中與互質(zhì)的的個數(shù)：，由于＝1，從而也是與互質(zhì)的個數(shù)，且兩兩余數(shù)不一樣，故（），而（）＝1，故。證明：取模的一個既約剩余系，考慮，由于與互質(zhì)，故仍與互質(zhì)，且有，于是對每個都能找到唯一的一個，使得，這種對應(yīng)關(guān)系是一一的，從而，。，，故。證畢。這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個數(shù)組組成另外一組剩余系來解決問題。定理2：（費(fèi)爾馬（Fermat）小定理）對于質(zhì)數(shù)及任意整數(shù)有。設(shè)為質(zhì)數(shù)，若是的倍數(shù)，則。若不是的倍數(shù)，則由引理及歐拉定理得，，由此即得。定理推論：設(shè)為質(zhì)數(shù)，是與互質(zhì)的任一整數(shù)，則。定理3：（威爾遜（Wilson）定理）設(shè)為質(zhì)數(shù)，則。分析與解答：受歐拉定理的影響，我們也找個數(shù)，然后來對應(yīng)乘法。證明：對于，在中，必然有一個數(shù)除以余1，這是因為則好是的一個剩余系去0。從而對，使得；若，，則，，故對于，有。即對于不同的對應(yīng)于不同的，即中數(shù)可兩兩配對，其積除以余1，然后有，使，即與它自己配對，這時，，或，或。除外，別的數(shù)可兩兩配對，積除以余1。故。定義：設(shè)為整系數(shù)多項式（），我們把含有的一組同余式（）稱為同余方組程。特別地，，當(dāng)均為的一次整系數(shù)多項式時，該同余方程組稱為一次同余方程組.若整數(shù)同時滿足：，則剩余類（其中）稱為同余方程組的一個解，寫作定理4：（中國剩余定理）設(shè)是兩兩互素的正整數(shù)，那么對于任意整數(shù)，一次同余方程組，必有解，且解可以寫為：這里，，以及滿足，（即為對模的逆）。中國定理的作用在于它能斷言所說的同余式組當(dāng)模兩兩互素時一定有解，而對于解的形式并不重要。定理5：（拉格郎日定理）設(shè)是質(zhì)數(shù)，是非負(fù)整數(shù)，多項式是一個模為次的整系數(shù)多項式（即

），則同余方程至多有個解（在模有意義的情況下）。定理6：若為對模的階，為某一正整數(shù)，滿足，則必為的倍數(shù)。以上介紹的只是一些系統(tǒng)的知識、方法，經(jīng)常在解決數(shù)論問題中起著突破難點(diǎn)的作用。另外還有一些小的技巧則是在解決、思考問題中起著排除情況、輔助分析等作用，有時也會起到意想不到的作用，如：，。這里我們只介紹幾個較為直接的應(yīng)用這些定理的例子。典例分析例1.設(shè)，求證：。證明：因為，故由知，從而，但是，故由歐拉定理得：，，從而；同理，。于是，，即。注明：現(xiàn)考慮整數(shù)的冪所成的數(shù)列：若有正整數(shù)使，則有，其中；因而關(guān)于，數(shù)列的項依次同余于這個數(shù)列相繼的項成一段，各段是完全相同的，因而是周期數(shù)列。如下例：例2．試求不大于100，且使成立的自然數(shù)的和。解：通過逐次計算，可求出關(guān)于的最小非負(fù)剩余（即為被11除所得的余數(shù)）為：因而通項為的數(shù)列的項的最小非負(fù)剩余構(gòu)成周期為5的周期數(shù)列：3，9，5，4，1，3，9，5，4，1，………類似地，經(jīng)過計算可得的數(shù)列的項的最小非負(fù)剩余構(gòu)成周期為10的周期數(shù)列：7，5，2，3，10，4，6，9，8，1，………于是由上兩式可知通項為的數(shù)列的項的最小非負(fù)剩余，構(gòu)成周期為10（即上兩式周期的最小公倍數(shù)）的周期數(shù)列：3，7，0，0，4，0，8，7，5，6，………這就表明，當(dāng)時，當(dāng)且僅當(dāng)時，，即；又由于數(shù)列的周期性，故當(dāng)時，滿足要求的只有三個，即從而當(dāng)時，滿足要求的的和為：.下面我們著重對Fetmat小定理及其應(yīng)用來舉例：例3．求證：對于任意整數(shù)，是一個整數(shù)。證明：令，則只需證是15的倍數(shù)即可。由3，5是素數(shù)及Fetmat小定理得，，則；而（3，5）=1，故，即是15的倍數(shù)。所以是整數(shù)。例4．求證：（為任意整數(shù)）。證明：令，則；所以含有因式由Fetmat小定理，知13|7|又13，7，5，3，2兩兩互素，所以2730=能整除。例5．設(shè)是直角三角形的三邊長。如果是整數(shù)，求證：可以被30整除。證明：不妨設(shè)是直角三角形的斜邊長，則。若2

，2

，2

c，則，又因為矛盾！所以2|.若3

，3

，3

c，因為，則，又，矛盾！從而3|.若5

，5

，5

c，因為，，所以或0(mod5)與矛盾！從而5|.又(2,3,5)=1，所以30|.下面講述中國剩余定理的應(yīng)用例6．證明：對于任意給定的正整數(shù)，均有連續(xù)個正整數(shù)，其中每一個都有大于1的平方因子。證明：由于素數(shù)有無窮多個，故我們可以取個互不相同的素數(shù)，而考慮同余組

①因為顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個數(shù)分別被平方數(shù)整除。注：（1）本題的解法體現(xiàn)了中國剩余定理的一個基本功效，它常常能將“找連續(xù)個正整數(shù)具有某種性質(zhì)”的問題轉(zhuǎn)化為“找個兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較容易解決的。

（2）本題若不直接使用素數(shù)，也中以采用下面的變異方法：由費(fèi)爾馬數(shù)兩兩互素，故將①中的轉(zhuǎn)化為后，相應(yīng)的同余式也有解，同樣可以導(dǎo)出證明。例7．證明：對于任意給定的正整數(shù)，均有連續(xù)個正整數(shù)，其中每一個都不是冪數(shù)。分析：我們來證明，存在連續(xù)個正整數(shù)，其中每一個數(shù)都至少有一個素因子，在這個數(shù)的標(biāo)準(zhǔn)分解中僅出現(xiàn)一次，從而這個數(shù)不是冪數(shù)。證明：取個互不相同的素數(shù)，考慮同余組因為顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。對于因為，故，但由①式可知

，即在的標(biāo)準(zhǔn)分解中恰好出現(xiàn)一次，故都不是冪數(shù)。例8．設(shè)是給定的偶數(shù)，且是偶數(shù)。證明：存在整數(shù)使得，且。證明：我們先證明，當(dāng)為素數(shù)冪時結(jié)論成立。實際上，能夠證明，存在使

且：若，則條件表明為偶數(shù)，此時可取；若，則與中有一對滿足要求。一般情形下，設(shè)是的一個標(biāo)準(zhǔn)分解，上面已經(jīng)證明，對每個存在整數(shù)使得且，而由中國剩余定理，同余式

①有解，同余式

②有解?，F(xiàn)不難驗證解符合問題中的要求：因，故，于是，又由①②知，故。注：此題的論證表現(xiàn)了中國剩余定理最為基本的作用：將一個關(guān)于任意正整數(shù)的問題，化為為素數(shù)冪的問題，而后者往往是比較好處理的。同余同余式性質(zhì)應(yīng)用非常廣泛，在處理某些整除性、進(jìn)位制、對整數(shù)分類、解不定方程等方面的問題中有著不可替代的功能，與之密切相關(guān)的的數(shù)論定理有歐拉定理、費(fèi)爾馬定理和中國剩余定理?；A(chǔ)知識三個數(shù)論函數(shù)對于任何正整數(shù)均有定義的函數(shù)，稱為數(shù)論函數(shù)。在初等數(shù)論中，所能用到的無非也就有三個，分別為：高斯(Gauss)取整函數(shù)[x]及其性質(zhì)，除數(shù)函數(shù)d(n)和歐拉(Euler)函數(shù)和它的計算公式。1．

高斯(Gauss)取整函數(shù)[]設(shè)是實數(shù)，不大于的最大整數(shù)稱為的整數(shù)部分，記為[]；稱為的小數(shù)部分，記為｛｝。例如：［0.5］＝0，等等。由的定義可得如下性質(zhì)：性質(zhì)1.；性質(zhì)2.；性質(zhì)3.設(shè)，則；性質(zhì)4.;;性質(zhì)5.；性質(zhì)6.對于任意的正整數(shù)，都有如下的埃米特恒等式成立：；為了描述性質(zhì)7，我們給出如下記號：若，且，則稱為恰好整除，記為。例如：我們有等等，其實，由整數(shù)唯一分解定理：任何大于1的整數(shù)能唯一地寫成的形式，其中為質(zhì)（素）數(shù)（）。我們還可以得到：。性質(zhì)7.若，則請注意，此式雖然被寫成了無限的形式，但實際上對于固定的，必存在正整數(shù)，使得，因而，故，而且對于時，都有。因此，上式實際上是有限項的和。另外，此式也指出了乘數(shù)的標(biāo)準(zhǔn)分解式中，素因數(shù)的指數(shù)的計算方法。2．除數(shù)函數(shù)d(n)正整數(shù)的正因數(shù)的個數(shù)稱為除數(shù)函數(shù)，記為d(n)。這里給出d(n)的計算公式：d(n)＝，為素數(shù)唯一分解定理中的指數(shù)。為了敘述地更加明確，我們組出素數(shù)唯一分解定理。算術(shù)基本定理（素數(shù)唯一分解定理）：任何一大于1的整數(shù)均可以分解為素數(shù)的乘積，若不考慮素數(shù)乘積的先后順序，則分解式是唯一的。例如：。當(dāng)一個整數(shù)分解成素數(shù)的乘積時，其中有些素數(shù)可以重復(fù)出現(xiàn)。例如在上面的分解式中，2出現(xiàn)了三次。把分解式中相同的素數(shù)的積寫成冪的形式，我們就可以把大于1的正整數(shù)寫成（1）此式稱為的標(biāo)準(zhǔn)分解式。這樣，算術(shù)基本定理也可以描述為大于1的整數(shù)的標(biāo)準(zhǔn)分解式是唯一的（不考慮乘積的先后順序）。推論1.若的標(biāo)準(zhǔn)分解式是（1）式，則是的正因數(shù)的充要條件是：（2）應(yīng)說明（2）不能稱為是的標(biāo)準(zhǔn)分解式，，其原因是其中的某些可能取零值（也有可能不含有某個素因數(shù)，因而）推論2.設(shè)，且，若是整數(shù)的次方，則也是整數(shù)的次方。特別地，若是整數(shù)的平方，則也是整數(shù)的平方。3.歐拉(Euler)函數(shù)設(shè)正整數(shù)0,1，……中與互素的個數(shù)，稱之為的歐拉函數(shù)，并記為。若的標(biāo)準(zhǔn)分解式是，則的計算公式是：例如：；

.以下我們講述同余的概念：同余的概念是高斯（Gauss）在1800年左右給出的。設(shè)是正整數(shù)，若用去除整數(shù)，所得的余數(shù)相同，則稱為與關(guān)于模同余，記作，否則，稱為與關(guān)于模不同余。定義1.（同余）設(shè)，若，則稱和對模同余，記作；若不然，則稱和對模不同余，記作。例如：，等等。當(dāng)時，，則稱是對模的最小非負(fù)剩余。由帶余除法可知，和對模同余的充要條件是與被除得的余數(shù)相同。對于固定的模，模的同余式與通常的等式有許多類似的性質(zhì)：性質(zhì)1.的充要條件是也即。性質(zhì)2.同余關(guān)系滿足以下規(guī)律：（1）（反身性）；（2）（對稱性）若，則；（3）（傳遞性）若，，則；（4）（同余式相加）若，，則；（5）（同余式相乘）若，，則；反復(fù)利用（4）（5），可以對多個兩個的（模相同的）同余式建立加、減和乘法的運(yùn)算公式。特別地，由（5）易推出：若，為整數(shù)且，則；但是同余式的消去律一般并不成立，即從未必能推出，可是我們卻有以下結(jié)果：（6）若，則，由此可以推出，若，則有，即在與互素時，可以在原同余式兩邊約去而不改變模（這一點(diǎn)再一次說明了互素的重要性）。現(xiàn)在提及幾個與模相關(guān)的簡單而有用的性質(zhì)：（7）若，｜，則；（8）若，，則；（9）若，則，特別地，若兩兩互素時，則有；性質(zhì)3.若，則；；性質(zhì)4.設(shè)是系數(shù)全為整數(shù)的多項式，若，則。這一性質(zhì)在計算時特別有用：在計算大數(shù)字的式子時，可以改變成與它同余的小的數(shù)字，使計算大大地簡化。如例3。定義2.設(shè)，是使成立的最小正整，則稱為對模的階。在取定某數(shù)后，按照同余關(guān)系把彼此同余的整數(shù)歸為一類，這些數(shù)稱為模的剩余類。一個類的任何一個數(shù)，都稱為該類所有數(shù)的剩余。顯然，同類的余數(shù)相同，不同類的余數(shù)不相同，這樣我們就把全體整數(shù)按照模劃分為了個剩余類：。在上述的個剩余類中，每一類任意取一個剩余，可以得到個數(shù)，稱為模的一個完全剩余系。例如關(guān)系模7，下面的每一組數(shù)都是一個完全剩余系：0，1，2，3，4，5，6；-7，8，16，3，-10，40，20；-3，-2，-1，0，1，2，3。

顯然，一組整數(shù)成為模的完全剩余系只需要滿足兩個條件（1）有個數(shù)；（2）各數(shù)關(guān)于模兩兩不同余。最常用的完全剩余系是最小非負(fù)完全剩余系及絕對值最小完全剩余系。模的最小非負(fù)完全剩余系是：0，1，2，………,;即除數(shù)為時，余數(shù)可能取到的數(shù)的全部值。當(dāng)為奇數(shù)時，絕對值最小的完全剩余系是：；當(dāng)為偶數(shù)時，絕對值最小的完全剩余系有兩個：；。以上只是我們個人對同余及剩余類的理解，為了方便大家研究，我們把有關(guān)材料上的具體概念給出，希望大家好好地研究：定義3.（同余類）設(shè)，每一個這樣的類為模的同余類。說明：整數(shù)集合可以按模來分類，確切地說，若和模同余，則和屬同一類，否則不屬于同一類，每一個這樣的類為模的一個同余類。由帶余除法，任一整數(shù)必恰與0,1,……，中的一個模同余，而0,1,……，這個數(shù)彼此模不同余，因此模共有個不同的同余類，即。例如，模2的同余類共有兩個，即通常說的偶數(shù)類與奇數(shù)類，這兩類中的數(shù)分別具有形式和（為任意整數(shù)）。定義4。（剩余類）設(shè)是正整數(shù)，把全體整按對模的余數(shù)分成類，相應(yīng)的個集合記為：，其中，稱為模的一個剩余類。以下是幾條常用性質(zhì)：（1）且；（2）每一個整數(shù)僅在的一個里；（3）對于任意，則的充要條件是。定義5.（完全剩余系）一組數(shù)稱為模的完全剩余系，如果對任意有且僅有一個是對模的剩余，即。換一種說法更好理解：設(shè)為模的全部剩余類，從每個中任取一個，得個數(shù)組成的數(shù)組，叫做模的一個完全剩余系。說明：在個剩余類中各任取一個數(shù)作為代表，這樣的個數(shù)稱為模的一個完全剩余系，簡稱模的完系。換句話說，個數(shù)稱為模的一個完系，是指它們彼此模不同余，例如0,1，2，……，是模的一個完系，這稱作是模的最小非負(fù)完系。性質(zhì)：（1）個整數(shù)構(gòu)成模的一個完全剩余系兩兩對模不同余；（2）若，則與同時跑遍模的完全剩余系。典例分析例1．試解方程：。解：因為左邊是整數(shù)，因而右邊的分式也應(yīng)該是整數(shù)，所以于是，從而，故。但是是整數(shù)，故，，代入前面的不等式，得，直接觀察即知，于是。例2．?dāng)?shù)100！的十進(jìn)位制表示中，未尾連續(xù)地有多少位全是零？解：命題等價于100！最多可以被10的多少次方整除。因為因而100！中2的指數(shù)大于5的指數(shù)，所以100！中5的指數(shù)就是所需求出的零的位數(shù)。由即可知100！的未尾連續(xù)地有24位全是數(shù)碼零。例3．試求被50除所得的余數(shù)。解：由于是關(guān)于的整系數(shù)多項式，而，于是知。又注意到，故又，所以注意到，因而29就是所求的余數(shù)。說明：在上述過程中，我們已經(jīng)看到的作用。一般而言，知道一個整數(shù)的多少次冪關(guān)于模同余于是非常有用的。事實上，若，則對大的指數(shù)利用帶余除法定理，可得，于是有，這里余數(shù)是一個比小得多的數(shù)，這樣一來，計算的問題，就轉(zhuǎn)化成了計算余數(shù)次冪的問題，從而使計算簡單化。例4．設(shè)，計算某星期一后的第天是6星期幾？解；星期幾的問題是被7除求余數(shù)的問題。由于，于是，，因而。為了把指數(shù)的指數(shù)寫成的形式，還需取6為模來計算。為此我們有，進(jìn)而有，，依次類推，有，所以從而，這樣，星期一后的第天將是星期五。例5．求所有的素數(shù)，使與也是素數(shù)。分析：要使與也是素數(shù)，應(yīng)該是對除以某個數(shù)素的余數(shù)進(jìn)行分類討論，最后確定只能是這個素數(shù)。由于只有兩個數(shù)，所以不能太大，那樣討論起來也不會有什么效果，試驗發(fā)現(xiàn)對本題不起任何效果，現(xiàn)對展開討論。解：設(shè)，，且若或4時，，；若或3時，，；即時，為5的倍數(shù)且比5大，不為質(zhì)數(shù)。故，此時，；都是素數(shù)。即可題有唯一解。注：要使幾個數(shù)同為質(zhì)數(shù)，一般是對這幾個數(shù)也合乎以某一質(zhì)數(shù)的余數(shù)來確定，如均為質(zhì)數(shù)，可得只能為3，由于這是的一次式，故三個數(shù)就模3，而二次式對三個數(shù)就模5，四個數(shù)一般就模7了。例6．求滿足的全部正整數(shù)。分析：如果，兩邊，得，這是不可能的；如果，而中有一個大于1，則另一個也大于1，得，故為奇數(shù)，，得，而，為奇數(shù)，從而，矛盾！所以為唯一解。注：在解不定方程時，往往要分情況討論，也常常利用同余來導(dǎo)出一些性質(zhì)求出矛盾！例7．?dāng)?shù)列滿足：證明：（1）對任意為正整數(shù)；(2)對任意為完全平方數(shù)。（2005年全國高中數(shù)學(xué)聯(lián)賽試題）證明：（1）由題設(shè)得且嚴(yán)格單調(diào)遞增.將條件式變形得兩邊平方整理得①②①-②得③由③式及可知，對任意為正整數(shù).（2）將①兩邊配方，得④由③式≡∴≡≡0（mod3）∴為正整數(shù)，④式成立.是完全平方數(shù).例8．若可以寫成有限小數(shù)，那么自然數(shù)的值是多少？解：由于若與互素，則分?jǐn)?shù)是既約分?jǐn)?shù)；若與不互素，設(shè)它們的公約數(shù)為，且，設(shè)，則，故與的公約數(shù)是5，此時分?jǐn)?shù)的分子、分母只有公約數(shù)5。由于可以寫成有限小數(shù)，故約分之后的分母除了2,5以外，沒還有其它的公約數(shù)，因此。因為是奇數(shù)，，故，即。由于故，從而，即，故只有才是有限小數(shù)。競賽講座03--同余式與不定方程同余式和不定方程是數(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ù)進(jìn)行分類，即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ù)個解.(2)

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

求方程的整數(shù)解.解(配方法)原方程配方得(x-2y)2+y2=132.在勾股數(shù)中,最大的一個為13的只有一組即5,12,13,因此有8對整數(shù)的平方和等于132即(5,12),(12,5),(-5,-12),(-12,-5),(5-,12),(12,-5),(-5,12),(-12,5).故原方程組的解只能是下面的八個方程組的解

解得

例7

(原民主德國1982年中學(xué)生競賽題)已知兩個自然數(shù)b和c及素數(shù)a滿足方程a2+b2=c2.證明:這時有a＜b及b+1=c.證明（因式分解法）∵a2+b2=c2，∴a2=（c-b）（c+b），又∵a為素數(shù)，∴c-b=1，且c+b=a2.于是得c=b+1及a2=b+c=2b+1＜3b，即＜.而a≥3,∴≤1，∴＜1.∴a＜b.例9（第35屆美國中學(xué)數(shù)學(xué)競賽題）滿足聯(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,c)有兩個,即(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≤.滿足這個不等式的整數(shù)只有y=0，1，2.當(dāng)y=0時，由原方程可得x=0或x=1；當(dāng)y=1時，由原方程可得x=2或0；當(dāng)y=2時，由原方程可得x=1或2.所以方程有整數(shù)解最后我們來看兩個分式和根式不定方程的例子.例12

求滿足方程且使y是最大的正整數(shù)解（x，y）.解將原方程變形得由此式可知，只有12-x是正的且最小時，y才能取大值.又12-x應(yīng)是144的約數(shù)，所以，12-x=1，x=11，這時y=132.故

滿足題設(shè)的方程的正整數(shù)解為（x，y）=（11，132）.例13（第35屆美國中學(xué)生數(shù)學(xué)競賽題）滿足0＜x＜y及的不同的整數(shù)對（x，y）的個數(shù)是（

）.（A）0

（B）1

（C）3

（D）4

（E）7解法1根據(jù)題意知，0＜x＜1984，由得

當(dāng)且僅當(dāng)1984x是完全平方數(shù)時，y是整數(shù).而1984=26·31，故當(dāng)且僅當(dāng)x具有31t2形式時，1984x是完全平方數(shù).∵x＜1984，∵1≤t≤7.當(dāng)t=1，2，3時，得整數(shù)對分別為（31，1519）、（124，1116）和（279，775）.當(dāng)t＞3時y≤x不合題意，因此不同的整數(shù)對的個數(shù)是3，故應(yīng)選（C）.解法2∵1984=∴由此可知：x必須具有31t2形式，y必須具有31k2形式，并且t+k=8（t，k均為正整數(shù)）.因為0＜x＜y，所以t＜k.當(dāng)t=1，k=7時得（31，1519）；t=2，k=6時得（124，1116）；當(dāng)t=3，k=5時得（279，775）.因此不同整數(shù)對的個數(shù)為3.練習(xí)二十1.

選擇題(1)方程x2-y2=105的正整數(shù)解有(

).（A）

一組（B）二組

（C）三組

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

）.（A）

3個（B）4個

（C）5個

（D）6個2．填空題（1）的個位數(shù)分別為_________及_________.(2)滿足不等式104≤A≤105的整數(shù)A的個數(shù)是x×104+1，則x的值________.(3)

已知整數(shù)y被7除余數(shù)為5,那么y3被7除時余數(shù)為________.(4)

(全俄第14屆中學(xué)生數(shù)學(xué)競賽試題)求出任何一組滿足方程x2-51y2=1的自然數(shù)解x和y_________.3.(第26屆國際數(shù)學(xué)競賽預(yù)選題)求三個正整數(shù)x、y、z滿足.4．（1985年上海數(shù)學(xué)競賽題）在數(shù)列4，8，17，77，97，106，125，238中相鄰若干個數(shù)之和是3的倍數(shù)，而不是9的倍數(shù)的數(shù)組共有多少組？5．求的整數(shù)解.6．求證可被37整除.7．（全俄1986年數(shù)學(xué)競賽題）求滿足條件的整數(shù)x，y的所有可能的值.8．（1985年上海初中數(shù)學(xué)競賽題）已知直角三角形的兩直角邊長分別為l厘米、m厘米，斜邊長為n厘米，且l，m，n均為正整數(shù)，l為質(zhì)數(shù).證明：2（l+m+n）是完全平方數(shù).9.(1988年全國初中數(shù)學(xué)競賽題)如果p、q、、都是整數(shù)，并且p＞1，q＞1，試求p+q的值.

練習(xí)二十1.D.C.2.(1)9及1.

(2)9.

(3)4.(4)原方程可變形為x2=(7y+1)2+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無整數(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),∴88882222≡82(mod37).7777≡7(mod37),77773333≡73(mod37),88882222+77773333≡(82+73)(mod37),而82+73=407,37|407,∴37|N.7.簡解:原方程變形為3x2-(3y+7)x+3y2-7y=0由關(guān)于x的二次方程有解的條件△≥0及y為整數(shù)可得0≤y≤5,即y=0,1,2,3,4,5.逐一代入原方程可知,原方程僅有兩組解(4,5)、(5,4).8.∵l2+m2=n2,∴l(xiāng)2=(n+m)(n-m).∵l為質(zhì)數(shù),且n+m＞n-m＞0,∴n+m=l2,n-m=1.于是l2=n+m=(m+1)+m=2m+1,2m=l2-1,2(l+m+1)=2l+2+2m=l2+2l+1=(l+1)2.即2(l+m+1)是完全平方數(shù).9.易知p≠q,不妨設(shè)p＞q.令=n,則m＞n由此可得不定方程(4-mn)p=m+2,解此方程可得p、q之值.數(shù)論初步期末復(fù)習(xí)輔導(dǎo)一、計算題求24871與3468的最大公因數(shù)?分析：利用輾轉(zhuǎn)相除法，r即最大公因數(shù)解：24871=34687+5953468=5955+493595=4931+102493=1024+85102=851+1785=175,所以,(24871,3468)=17.求[24871,3468]=?解：因為（24871,3468）=17所以[24871,3468]==5073684所以24871與3468的最小公倍數(shù)是5073684。3、求[136,221,391]=?分析：如果()是個整數(shù)，則=.先求[136,221]=1768，再求[1768,391]=40664，即是136,221,391三數(shù)的最大公倍數(shù)解：[136,221,391]=[[136,221],391]=[]=[1768,391]==104391=40664.4、.分析：利用剩余定理（輾轉(zhuǎn)相除法）求二元一次不定方程的方法是（1）先化簡原方程得到同解方程；（2）再求同解方程；（3）寫出一切解的形式。）解：因為（9，21）=3，，所以有解；化簡得；