初等數(shù)論中的幾個重要定理

1、初等數(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ì)，故仍

2、與互質(zhì)，且有，于是對每個都能找到唯一的一個，使得，這種對應(yīng)關(guān)系是一一的，從而，。,，故。證畢。這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個數(shù)組組成另外一組剩余系來解決問題。定理2:（費爾馬（Fermat ）小定理）對于質(zhì)數(shù)及任意整數(shù)有。設(shè)為質(zhì)數(shù)，若是的倍數(shù)，則。若不是的倍數(shù)，則由引理及歐拉定理得，由此即得。定理推論：設(shè)為質(zhì)數(shù)，是與互質(zhì)的任一整數(shù)，則。定理3:（威爾遜（Wils on ）定理）設(shè)為質(zhì)數(shù)，則。分析與解答：受歐拉定理的影響，我們也找個數(shù)，然后來對應(yīng)乘法。證明：對于，在中，必然有一個數(shù)除以余1這是因為則好是的一個剩余系去0。從而對，使得；若，U，故對于，有。即對于不同的對

3、應(yīng)于不同的，即中數(shù)可兩兩配對，其積除以余1，然后有，使，即與它自己配對，這時，或，或。除外，別的數(shù)可兩兩配對，積除以余1。故。定義：設(shè)為整系數(shù)多項式（），我們把含有的一組同余式（）稱為同余方組程。特別地，當(dāng)均為的一次整系數(shù)多項式時，該同余方程組稱為一次同余方程組若整數(shù)同時滿足：，則剩余類（其中）稱為同余方程組的一個解，寫作定理4:（中國剩余定理） 設(shè)是兩兩互素的正整數(shù)，那么對于任意整數(shù)，一次同余方程 組，必有解，且解可以寫為：x = 角+陰勺+'"" +皿掛以（mo d朋）這里，以及滿足，（即為對模的逆）。中國定理的作用在于它能斷言所說的同余式組當(dāng)模兩兩互素時一定有

4、解，而對于解的 形式并不重要。定理5 ：（拉格郎日定理）設(shè)是質(zhì)數(shù)，是非負(fù)整數(shù)，多項式是一個模為次的整系數(shù)多項 式（即 ），則同余方程至多有個解（在模有意義的情況下）。定理6:若為對模的階，為某一正整數(shù)，滿足，則必為的倍數(shù)。以上介紹的只是一些系統(tǒng)的知識、 方法，經(jīng)常在解決數(shù)論問題中起著突破難點的作用。 另外 還有一些小的技巧則是在解決、 思考問題中起著排除情況、輔助分析等作用，有時也會起到 意想不到的作用口：，。這里我們只介紹幾個較為直接的應(yīng)用這些定理的例子。典例分析例1.設(shè)，求證：。證明：因為，故由知，從而，但是，故由歐拉定理得：，從而；同理，。于是，即。注明：現(xiàn)考慮整數(shù)的幕所成的數(shù)列：若有正

5、整數(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 ,10的周期數(shù)列:類似地，經(jīng)過計算可得的數(shù)列的項的最小非負(fù)剩余構(gòu)成周期為7, 5, 2, 3, 10, 4, 6, 9, 8, 1,于是由上兩式可知通項為的數(shù)列的項的最小非負(fù)剩余，構(gòu)成周期為10 （即上兩式周期的最小公倍數(shù)）的周期數(shù)列：3, 7, 0,

6、 0, 4, 0, 8, 7, 5, 6,這就表明，當(dāng)時，當(dāng)且僅當(dāng)時，即；又由于數(shù)列的周期性，故當(dāng)時，滿足要求的只有三個，即從而當(dāng)時，滿足要求的的和為：另（1誕+ 3）+（1處+4+（1就+勺二乞刃去+13二孔另上+ 1。:<13二3弘仍+1孔二1船0*-0JU）JU）F面我們著重對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，

7、5，3，2兩兩互素，所以 2730=能整除。30整除。例5設(shè)是直角三角形的三邊長。如果是整數(shù)，求證：可以被證明：不妨設(shè)是直角三角形的斜邊長，則。若2，2，2C,則，又因為矛盾！所以2|.若3，3，3C,因為，則，又，矛盾！從而3|若5，5，5C,因為，所以或0(mod5)與矛盾!從而5|.又(2,3,5)=1 ，所以 30|.F面講述中國剩余定理的應(yīng)用例6證明：對于任意給定的正整數(shù)，均有連續(xù)個正整數(shù)，其中每一個都有大于1的平方因子。證明：由于素數(shù)有無窮多個，故我們可以取個互不相同的素數(shù)，而考慮同余組因為顯然是兩兩互素的， 故由中國剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個數(shù)分 別被平方數(shù)整

8、除。注：（1）本題的解法體現(xiàn)了中國剩余定理的一個基本功效，它常常能將“找連續(xù)個正整數(shù)具有某種性質(zhì)”的問題轉(zhuǎn)化為“找個兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較容易解決的。（2 ）本題若不直接使用素數(shù)，也中以采用下面的變異方法：由費爾馬數(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è)是的一個