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

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

2、一的一個，使得，這種對應關系是一一的，從而，。，故。證畢。這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個數(shù)組組成另外一組剩余系來解決問題。定理2：費爾馬Fermat小定理對于質(zhì)數(shù)及任意整數(shù)有。設為質(zhì)數(shù)，假設是的倍數(shù)，那么。假設不是的倍數(shù)，那么由引理及歐拉定理得，由此即得。定理推論：設為質(zhì)數(shù)，是與互質(zhì)的任一整數(shù)，那么。定理3：威爾遜Wilson定理設為質(zhì)數(shù)，那么。分析與解答：受歐拉定理的影響，我們也找個數(shù)，然后來對應乘法。證明：對于，在中，必然有一個數(shù)除以余1，這是因為那么好是的一個剩余系去0。從而對，使得；假設，那么，故對于，有。即對于不同的對應于不同的，即中數(shù)可兩兩配對，其積除以

3、余1，然后有，使，即與它自己配對，這時，或，或。除外，別的數(shù)可兩兩配對，積除以余1。故。定義：設為整系數(shù)多項式，我們把含有的一組同余式稱為同余方組程。特別地，當均為的一次整系數(shù)多項式時，該同余方程組稱為一次同余方程組.假設整數(shù)同時滿足：，那么剩余類其中稱為同余方程組的一個解，寫作定理4：中國剩余定理設是兩兩互素的正整數(shù)，那么對于任意整數(shù)，一次同余方程組，必有解，且解可以寫為：這里，以及滿足，即為對模的逆。中國定理的作用在于它能斷言所說的同余式組當模兩兩互素時一定有解，而對于解的形式并不重要。定理5：拉格郎日定理設是質(zhì)數(shù)，是非負整數(shù)，多項式是一個模為次的整系數(shù)多項式即 ，那么同余方程至

4、多有個解在模有意義的情況下。定理6：假設為對模的階，為某一正整數(shù)，滿足，那么必為的倍數(shù)。以上介紹的只是一些系統(tǒng)的知識、方法，經(jīng)常在解決數(shù)論問題中起著突破難點的作用。另外還有一些小的技巧那么是在解決、思考問題中起著排除情況、輔助分析等作用，有時也會起到意想不到的作用，如：，。這里我們只介紹幾個較為直接的應用這些定理的例子。典例分析例1.設，求證：。證明：因為，故由知，從而，但是，故由歐拉定理得：，從而；同理，。于是，即。注明：現(xiàn)考慮整數(shù)的冪所成的數(shù)列：假設有正整數(shù)使，那么有，其中；因而關于，數(shù)列的項依次同余于這個數(shù)列相繼的項成一段，各段是完全相同的，因而是周期數(shù)列。如下例：例2試求不大于100，

5、且使成立的自然數(shù)的和。解：通過逐次計算，可求出關于的最小非負剩余即為被11除所得的余數(shù)為：因而通項為的數(shù)列的項的最小非負剩余構成周期為5的周期數(shù)列：3，9，5，4，1，3，9，5，4，1，類似地，經(jīng)過計算可得的數(shù)列的項的最小非負剩余構成周期為10的周期數(shù)列：7，5，2，3，10，4，6，9，8，1，于是由上兩式可知通項為的數(shù)列的項的最小非負剩余，構成周期為10即上兩式周期的最小公倍數(shù)的周期數(shù)列：3，7，0，0，4，0，8，7，5，6，這就說明，當時，當且僅當時，即；又由于數(shù)列的周期性，故當時，滿足要求的只有三個，即從而當時，滿足要求的的和為：.下面我們著重對Fetmat小定理及其應用來舉例：例

6、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ù)，求證：可以被30整除。證明：不妨設是直角三角形的斜邊長，那么。假設2  ，2  ，2  c，那么，又因為矛盾！所以2|.假設3  ，3  ，3  c，因為，那么，又，矛盾！從而3|.假設 5 

7、0;，5  ，5  c，因為，所以或0(mod5)與矛盾！從而5|.又(2,3,5)=1，所以30|.下面講述中國剩余定理的應用例6證明：對于任意給定的正整數(shù)，均有連續(xù)個正整數(shù)，其中每一個都有大于1的平方因子。證明：由于素數(shù)有無窮多個，故我們可以取個互不相同的素數(shù)，而考慮同余組     因為顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個數(shù)分別被平方數(shù)整除。注：1此題的解法表達了中國剩余定理的一個根本成效，它常常能將“找連續(xù)個正整數(shù)具有某種性質(zhì)的問題轉(zhuǎn)化為“找個兩兩互素的數(shù)具有某種性質(zhì)，而后者往往是比擬容易解決

8、的。   2此題假設不直接使用素數(shù)，也中以采用下面的變異方法：由費爾馬數(shù)兩兩互素，故將中的轉(zhuǎn)化為后，相應的同余式也有解，同樣可以導出證明。例7證明：對于任意給定的正整數(shù)，均有連續(xù)個正整數(shù)，其中每一個都不是冪數(shù)。分析：我們來證明，存在連續(xù)個正整數(shù)，其中每一個數(shù)都至少有一個素因子，在這個數(shù)的標準分解中僅出現(xiàn)一次，從而這個數(shù)不是冪數(shù)。證明：取個互不相同的素數(shù)，考慮同余組因為顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。對于因為，故，但由式可知 ，即在的標準分解中恰好出現(xiàn)一次，故都不是冪數(shù)。例8 設是給定的偶數(shù)，且是偶數(shù)。證明：存在整數(shù)使得，且。證明：我們先證明，當為素數(shù)冪時結論成立。實際上，能夠證明，存在使 且：假設，那么條件說明為偶數(shù)，此時可取；假設，那么與中有一對滿足要求。一般情形下，設是的一個標準分解，上面已經(jīng)證明，對每個存在整數(shù)使得且，而由中國剩余定理，同余式