初等數(shù)論中的幾個(gè)重要定理_百度文庫(kù)

1、初等數(shù)論中的幾個(gè)重要定理 基礎(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ì)，且有，于

2、是對(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)閯t好是的一個(gè)剩余系去0。從而對(duì)，使得；若，則，故對(duì)于，有。即對(duì)于不同的對(duì)應(yīng)于不同的，即中數(shù)可兩

3、兩配對(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ù)

4、多項(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)?，故由知，從而，但是，故由歐拉定理得：，從而；同理，。于是，即。注明：現(xiàn)考慮整數(shù)的冪所成的數(shù)列：若有正整數(shù)使，則有，其中；因而關(guān)于，數(shù)列的項(xiàng)依次同余于這個(gè)數(shù)列相繼的項(xiàng)成一段，各段是完全相同的，因而是周期數(shù)列

5、。如下例：例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í)，滿足要求的的和為：.下面我們著

6、重對(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)槊?！所?|.若3  ，3  ，3  c，因?yàn)?，則，又，矛

7、盾！從而3|.若 5  ，5  ，5  c，因?yàn)椋曰?(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)轱@然是兩兩互素的，故由中國(guó)剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)個(gè)數(shù)分別被平方數(shù)整除。注：（1）本題的解法體現(xiàn)了中國(guó)剩余定理的一個(gè)基本功效，它常常能將“找連續(xù)個(gè)正整數(shù)具有某種性質(zhì)”的問(wèn)題轉(zhuǎn)化為“找個(gè)兩兩互素的數(shù)具有某

8、種性質(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)轱@然是兩兩互素的，故由中國(guó)剩余定理知，上述同余組有正整數(shù)解。對(duì)于因?yàn)?，故，但由式可?#160;，即在的標(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ó)剩余定理，同余式