1、初等數論中的幾個重要定理基礎知識定義（歐拉（Euler）函數）一組數稱為是模的既約剩余系，如果對任意的，且對于任意 的，若=1,則有且僅有一個是對模的剩余，即。并定義中和互質的數的個數，稱為歐拉（Euler ）函數。這是數論中的非常重要的一個函數，顯然，而對于，就是1,2，中與互素的數的個數，比如說是素數，則有。引理：；可用容斥定理來證（證明略）。定理1:（歐拉（Euler ）定理）設=1，則。分析與解答：要證，我們得設法找出個相乘，由個數我們想到中與互質的的個數：，由 于= 1,從而也是與互質的個數，且兩兩余數不一樣，故（），而（）=1，故。證明：取模的一個既約剩余系，考慮，由于與互質，故仍

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

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

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

5、整數使，則有，其中；因而關于，數列的項依次同余于這個數列相繼的項成一段，各段是完全相同的，因而是周期數列。如下例：例2.試求不大于100,且使成立的自然數的和。解：通過逐次計算，可求出關于的最小非負剩余（即為被11除所得的余數）為：因而通項為的數列的項的最小非負剩余構成周期為5的周期數列:3, 9, 5, 4， 1, 3, 9, 5， 4, 1 ,10的周期數列:類似地，經過計算可得的數列的項的最小非負剩余構成周期為7, 5, 2, 3, 10, 4, 6, 9, 8, 1,于是由上兩式可知通項為的數列的項的最小非負剩余，構成周期為10 （即上兩式周期的最小公倍數）的周期數列：3, 7, 0,

6、 0, 4, 0, 8, 7, 5, 6,這就表明，當時，當且僅當時，即；又由于數列的周期性，故當時，滿足要求的只有三個，即從而當時，滿足要求的的和為：另（1誕+ 3）+（1處+4+（1就+勺二乞刃去+13二孔另上+ 1。:<13二3弘仍+1孔二1船0*-0JU）JU）F面我們著重對Fetmat小定理及其應用來舉例例3.求證：對于任意整數，是一個整數。 證明：令，則只需證是 15的倍數即可。由3, 5是素數及Fetmat小定理得，則而（3, 5） =1,故，即是15的倍數。所以是整數。例4 .求證：(為任意整數)。證明：令，則；所以含有因式由Fetmat小定理，知 13|7|又13，7，

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

8、除。注：（1）本題的解法體現了中國剩余定理的一個基本功效，它常常能將“找連續個正整數具有某種性質”的問題轉化為“找個兩兩互素的數具有某種性質”，而后者往往是比較容易解決的。（2 ）本題若不直接使用素數，也中以采用下面的變異方法：由費爾馬數兩兩互素，故 將中的轉化為后，相應的同余式也有解，同樣可以導出證明。例7.證明：對于任意給定的正整數，均有連續個正整數，其中每一個都不是幕數。分析：我們來證明，存在連續個正整數， 其中每一個數都至少有一個素因子，在這個數的標 準分解中僅出現一次，從而這個數不是幕數。證明：取個互不相同的素數，考慮同余組因為顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數解。對于因為，故，但由式可知，即在的標準分解中恰好出現一次，故都不是幕數。例8 設是給定的偶數，且是偶數。證明：存在整數使得，且。證明：我們先證明，當為素數幕時結論成立。實際上，能夠證明，存在使且:若，則條件表明為偶數，此時可取；若，則與中有一對滿足要求。一般情形下，設是的一個