基礎(chǔ)知識(shí)

　　定義（歐拉(Euler)函數(shù)）一組數(shù)稱為是模的既約剩余系，如果對(duì)任意的，且對(duì)于任意的，若＝1，則有且僅有一個(gè)是對(duì)模的剩余，即。并定義中和互質(zhì)的數(shù)的個(gè)數(shù)，稱為歐拉（Euler）函數(shù)。

這是數(shù)論中的非常重要的一個(gè)函數(shù)，顯然，而對(duì)于，就是1,2，…，中與互素的數(shù)的個(gè)數(shù)，比如說(shuō)是素?cái)?shù)，則有。

　　引理：；可用容斥定理來(lái)證（證明略）。

　　定理1：（歐拉（Euler）定理）設(shè)＝1，則。

　　分析與解答：要證，我們得設(shè)法找出個(gè)相乘，由個(gè)數(shù)我們想到中與互質(zhì)的的個(gè)數(shù)：，由于＝1，從而也是與互質(zhì)的個(gè)數(shù)，且兩兩余數(shù)不一樣，故（），而（）＝1，故。

　　證明：取模的一個(gè)既約剩余系，考慮，由于與互質(zhì)，故仍與互質(zhì)，且有　，于是對(duì)每個(gè)都能找到唯一的一個(gè)，使得，這種對(duì)應(yīng)關(guān)系是一一的，從而，。

，，故。證畢。

這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個(gè)數(shù)組組成另外一組剩余系來(lái)解決問(wèn)題。

　　定理2：（費(fèi)爾馬（Fermat）小定理）對(duì)于質(zhì)數(shù)及任意整數(shù)有。

設(shè)為質(zhì)數(shù)，若是的倍數(shù)，則。若不是的倍數(shù)，則由引理及歐拉定理得，，由此即得。

　　定理推論：設(shè)為質(zhì)數(shù)，是與互質(zhì)的任一整數(shù)，則。

　　定理3：（威爾遜（Wilson）定理）設(shè)為質(zhì)數(shù)，則。

　　分析與解答：受歐拉定理的影響，我們也找個(gè)數(shù)，然后來(lái)對(duì)應(yīng)乘法。

　　證明：對(duì)于，在中，必然有一個(gè)數(shù)除以余1，這是因?yàn)?span style="FONT-SIZE: 10.5pt">則好是的一個(gè)剩余系去0。

　　　從而對(duì)，使得；

　　　若，，則，，故對(duì)于，有　。即對(duì)于不同的對(duì)應(yīng)于不同的，即中數(shù)可兩兩配對(duì)，其積除以余1，然后有，使，即與它自己配對(duì)，這時(shí)，，或，或。

　　除外，別的數(shù)可兩兩配對(duì)，積除以余1。故。

定義：設(shè)為整系數(shù)多項(xiàng)式（），我們把含有的一組同余式（）稱為同余方組程。特別地，，當(dāng)均為的一次整系數(shù)多項(xiàng)式時(shí)，該同余方程組稱為一次同余方程組.若整數(shù)同時(shí)滿足：

，則剩余類（其中）稱為同余方程組的一個(gè)解，寫作

　　定理4：（中國(guó)剩余定理）設(shè)是兩兩互素的正整數(shù)，那么對(duì)于任意整數(shù)，一次同余方程組，必有解，且解可以寫為：

　　這里，，以及滿足，（即為對(duì)模的逆）。

中國(guó)定理的作用在于它能斷言所說(shuō)的同余式組當(dāng)模兩兩互素時(shí)一定有解，而對(duì)于解的形式并不重要。

　　定理5：（拉格郎日定理）設(shè)是質(zhì)數(shù)，是非負(fù)整數(shù)，多項(xiàng)式是一個(gè)模為次的整系數(shù)多項(xiàng)式（即 ），則同余方程至多有個(gè)解（在模有意義的情況下）。

　　定理6：若為對(duì)模的階，為某一正整數(shù)，滿足，則必為的倍數(shù)。

以上介紹的只是一些系統(tǒng)的知識(shí)、方法，經(jīng)常在解決數(shù)論問(wèn)題中起著突破難點(diǎn)的作用。另外還有一些小的技巧則是在解決、思考問(wèn)題中起著排除情況、輔助分析等作用，有時(shí)也會(huì)起到意想不到的作用，如：，。這里我們只介紹幾個(gè)較為直接的應(yīng)用這些定理的例子。

　　典例分析

例1.設(shè)，求證：。

證明：因?yàn)?span style="FONT-SIZE: 10.5pt">，故由知，從而，但是，故由歐拉定理得：，，從而；同理，。

于是，，即。

注明：現(xiàn)考慮整數(shù)的冪所成的數(shù)列：若有正整數(shù)使，則有，其中；

因而關(guān)于，數(shù)列的項(xiàng)依次同余于這個(gè)數(shù)列相繼的項(xiàng)成一段，各段是完全相同的，因而是周期數(shù)列。如下例：

例2．試求不大于100，且使成立的自然數(shù)的和。

解：通過(guò)逐次計(jì)算，可求出關(guān)于的最小非負(fù)剩余（即為被11除所得的余數(shù)）為：

因而通項(xiàng)為的數(shù)列的項(xiàng)的最小非負(fù)剩余構(gòu)成周期為5的周期數(shù)列：

3，9，5，4，1，3，9，5，4，1，………

類似地，經(jīng)過(guò)計(jì)算可得的數(shù)列的項(xiàng)的最小非負(fù)剩余構(gòu)成周期為10的周期數(shù)列：

7，5，2，3，10，4，6，9，8，1，………

于是由上兩式可知通項(xiàng)為的數(shù)列的項(xiàng)的最小非負(fù)剩余，構(gòu)成周期為10（即上兩式周期的最小公倍數(shù)）的周期數(shù)列：

3，7，0，0，4，0，8，7，5，6，………

這就表明，當(dāng)時(shí)，當(dāng)且僅當(dāng)時(shí)，，即；

又由于數(shù)列的周期性，故當(dāng)時(shí)，滿足要求的只有三個(gè)，即

從而當(dāng)時(shí)，滿足要求的的和為：

.

下面我們著重對(duì)Fetmat小定理及其應(yīng)用來(lái)舉例：

例3．求證：對(duì)于任意整數(shù)，是一個(gè)整數(shù)。

證明：令，則只需證是15的倍數(shù)即可。

由3，5是素?cái)?shù)及Fetmat小定理得，，則

；

而（3，5）=1，故，即是15的倍數(shù)。所以是整數(shù)。

例4．求證：（為任意整數(shù)）。

證明：令，則；

所以含有因式

由Fetmat小定理，知13|7|

又13，7，5，3，2兩兩互素，所以2730=能整除。

例5．設(shè)是直角三角形的三邊長(zhǎng)。如果是整數(shù)，求證：可以被30整除。

證明：不妨設(shè)是直角三角形的斜邊長(zhǎng)，則。

若2  ，2  ，2  c，則，又因?yàn)?span style="FONT-SIZE: 10.5pt">矛盾！

所以2|.

若3  ，3  ，3  c，因?yàn)?span style="FONT-SIZE: 10.5pt">，則，又，矛盾！從而3|.

若 5  ，5  ，5  c，因?yàn)?span style="FONT-SIZE: 10.5pt">，，

所以或0(mod5)與矛盾！

從而5|.

又(2,3,5)=1，所以30|.

下面講述中國(guó)剩余定理的應(yīng)用

例6．證明：對(duì)于任意給定的正整數(shù)，均有連續(xù)個(gè)正整數(shù)，其中每一個(gè)都有大于1的平方因子。

證明：由于素?cái)?shù)有無(wú)窮多個(gè)，故我們可以取個(gè)互不相同的素?cái)?shù)，而考慮同余組     ①

因?yàn)?span style="FONT-SIZE: 10.5pt">顯然是兩兩互素的，故由中國(guó)剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個(gè)數(shù)分別被平方數(shù)整除。

注：（1）本題的解法體現(xiàn)了中國(guó)剩余定理的一個(gè)基本功效，它常常能將“找連續(xù)個(gè)正整數(shù)具有某種性質(zhì)”的問(wèn)題轉(zhuǎn)化為“找個(gè)兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較容易解決的。

   （2）本題若不直接使用素?cái)?shù)，也中以采用下面的變異方法：由費(fèi)爾馬數(shù)兩兩互素，故將①中的轉(zhuǎn)化為后，相應(yīng)的同余式也有解，同樣可以導(dǎo)出證明。

例7．證明：對(duì)于任意給定的正整數(shù)，均有連續(xù)個(gè)正整數(shù)，其中每一個(gè)都不是冪數(shù)。

分析：我們來(lái)證明，存在連續(xù)個(gè)正整數(shù)，其中每一個(gè)數(shù)都至少有一個(gè)素因子，在這個(gè)數(shù)的標(biāo)準(zhǔn)分解中僅出現(xiàn)一次，從而這個(gè)數(shù)不是冪數(shù)。

證明：取個(gè)互不相同的素?cái)?shù)，考慮同余組

因?yàn)?span style="FONT-SIZE: 10.5pt">顯然是兩兩互素的，故由中國(guó)剩余定理知，上述同余組有正整數(shù)解。

對(duì)于因?yàn)?span style="FONT-SIZE: 10.5pt">，故，但由①式可知 ，即在的標(biāo)準(zhǔn)分解中恰好出現(xiàn)一次，故都不是冪數(shù)。

例8． 設(shè)是給定的偶數(shù)，且是偶數(shù)。

證明：存在整數(shù)使得，且。

證明：我們先證明，當(dāng)為素?cái)?shù)冪時(shí)結(jié)論成立。實(shí)際上，能夠證明，存在使

 且：

若，則條件表明為偶數(shù)，此時(shí)可取；

若，則與中有一對(duì)滿足要求。

一般情形下，設(shè)是的一個(gè)標(biāo)準(zhǔn)分解，上面已經(jīng)證明，對(duì)每個(gè)存在整數(shù)使得且，而由中國(guó)剩余定理，

同余式      ①有解，

同余式      ②有解。

現(xiàn)不難驗(yàn)證解符合問(wèn)題中的要求：因，故 ，

于是，又由①②知，

故。

注：此題的論證表現(xiàn)了中國(guó)剩余定理最為基本的作用：將一個(gè)關(guān)于任意正整數(shù)的問(wèn)題，化為為素?cái)?shù)冪的問(wèn)題，而后者往往是比較好處理的。