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

1、初等數(shù)論中的幾個(gè)重要定理基礎(chǔ)知識(shí)定義（歐拉（Euler）函數(shù)）一組數(shù)可，兀2，兀稱為是模搐的既約剩余系，如果對(duì)任意 的（虧，加）“且對(duì)于任意的aeZ,若S的） = 1,則有且僅有一個(gè)心是/對(duì)模 於的剩余，即sx/modw）o并定義奴朋）二二卩2，加中和喘互質(zhì)的數(shù)的個(gè)數(shù)， 勿加）稱為歐拉（Euler）函數(shù)。這是數(shù)論中的非常重要的一個(gè)函數(shù)，顯然鍬1）= 1,而對(duì)二忍1,殞同就是1,2, 朋一1中與搐互素的數(shù)的個(gè)數(shù)，比如說P是素?cái)?shù)，則有鈕）=去一1。血型）二m 引理：pg;可用容斥定理來證（證明略）。定理1：（歐拉（Euler）定理）設(shè)S，的）= ,則翊）。分析與解答：要證么鞏粹=IN。刪），我們得

2、設(shè)法找出炭同個(gè)肚相乘，由炭同個(gè)數(shù) 我們想到12，加中與也互質(zhì)的做網(wǎng)的個(gè)數(shù)：么1皿2,山鞏斛，由于0,朋）= ,從而 購(gòu)1，處2,，購(gòu)附）也是與搐互質(zhì)的侃同個(gè)數(shù),且兩兩余數(shù)不一樣，故也 5三 aalfaa2,-,aaMa，a2的）（mod3）,而（ai，a2aw）m）=】，；.嚴(yán)爐図=l（mod m）證明:取模吃的_個(gè)既約剩余系二快嘰 考慮abltab2f-fabJt由 于/與於互質(zhì)，故叫（1丿金）仍與旳互質(zhì)，且有噸abf（yiiMs）,于是對(duì)每 個(gè)1蘭$都能找到唯一的一個(gè)，使得毎三4（j）（md）,這種對(duì)應(yīng)關(guān)系。（函）三僅心（mo伽）三（mod2）應(yīng)（亓糾）三OjXmod） 是一一的，從而冋用

3、H, EH。心/円二宀険如）訐么?。?l（mod m）證畢。這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個(gè)數(shù)組組成另外一組剩 余系來解決問題。定理2：（費(fèi)爾馬（Fermat）小定理）對(duì)于質(zhì)數(shù)戸及任意整數(shù)么有”二就血擁刃。設(shè)戸為質(zhì)數(shù)，若么是戸的倍數(shù)，則/ = =刃。若金不是戸的倍數(shù)，則勿二1由引理及歐拉定理得戀）*T心爐。），由此即得。定理，推論：設(shè)戸為質(zhì)數(shù)，a是與戸互質(zhì)的任一整數(shù)，則?_lsl（tnod7）c定理3：（威爾遜（W訂son）定理）設(shè)対為質(zhì)數(shù)，則（戸1）一1血0（1勿。分析與解答：受歐拉定理的影響，我們也找0一1個(gè)數(shù)，然后來對(duì)應(yīng)乘法。證明：對(duì)于（兀去）=1,在兀2兀，0

4、? 1）乳中，必然有一個(gè)數(shù)除以多余1,這是因?yàn)?&2兀，（戸_l）x則好是戸的一個(gè)剩余系去。從而對(duì).使得&三（modg）；若入兒三入九血。4去），（心目）=1,則兀01-尹2三0山。4月），131-尹2）,故 對(duì)于乃丿2 w12e-l,有兀人xy2（mp即對(duì)于不同的X對(duì)應(yīng)于不同的即21,2,去1中數(shù)可兩兩配對(duì)，其積除以戸余1,然后衣兀，使兀s Kmod p）,即與它自 己配對(duì)，這時(shí)x2_1= 0（mcdrt , （x+l）（x 1）三 0（modj?）,開三一或入三（mod 卑）， 汽=-1 或 a = 1o除兀=p-1外，別的數(shù)可兩兩配對(duì)，積除以戸余1。故9一1）僅一1 ml（modp）。定

5、義：設(shè)XKR為整系數(shù)多項(xiàng)式（1蘭丘），我們把含有兀的一組同余式 /z（x）s0（mod.） jk稱為同余方組程。特別地，當(dāng)乳（耳均為兀的一次整系 數(shù)多項(xiàng)式時(shí)，該同余方程組稱為一次同余方程組.若整數(shù)亡同時(shí)滿足：$2三曲&叫）1蘭上，則剩余類匱二劉兀2莊三鞏nwd型）（其中型二陶J(rèn)，廻,嚴(yán)訂）稱為同余方程組的一個(gè)解，寫作定理4：（中國(guó)剩余定理）設(shè)叫是兩兩互素的正整數(shù)，那么對(duì)于任意整數(shù)計(jì)2,叭一次同余方程組勺他呵），1曲必有解，且解可以寫為：兀三跡坷幻 +M2N2a2 +- +Mf ka!( (raod m)這里心咤性以及環(huán)滿足M河嚴(yán)l（md）, 2仝（即弘為對(duì)模的逆）。中國(guó)定理的作用在于它能斷言所

6、說的同余式組當(dāng)模兩兩互素時(shí)一定有解而對(duì)于解的 形式并不重要。定理5:（拉格郎日定理）設(shè)戸是質(zhì)數(shù)，尬是非負(fù)整數(shù)，多項(xiàng)式/（E二色/+鬥兀+如 是一個(gè)模戸為力次的整系數(shù)多項(xiàng)式（即戸、 a2，則同余方程/（刃三0血。刃）至多 有個(gè)解（在模戸有意義的情況下）。定理6：若為么對(duì)模於的階，用為某一正整數(shù)，滿足 = 1（尬。已刪），則S必為2的倍 數(shù)。以上介紹的只是一些系統(tǒng)的知識(shí).方法，經(jīng)常在解決數(shù)論問題中起著突破難點(diǎn)的作用。另外 還有一些小的技巧則是在解決.思考問題中起著排除情況.輔助分析等作用，有時(shí)也會(huì)起到2 f0(mod9) 3整除 n 時(shí)Yl = c|_0(mod3)環(huán)整除時(shí) 這里我們化5跑偽奇數(shù)時(shí)

7、意想不到的作用，如：t0（mod4）偽偶數(shù)時(shí) 只介紹幾個(gè)較為直接的應(yīng)用這些定理的例子。典例分析 例1設(shè)（9心1,求證:叫（尹-滬）。 證明:因?yàn)?1 = 7x13,故由（91曲）=1知（91衛(wèi)）=1,從而（7衛(wèi)）=1,（13衛(wèi)）= 1,但是 07）二 6,奴13）二 12,故由歐拉定理得：an = （a6f =l2 = l（mod7） , 12 = l（mod 13）, 從而0Ml（niQd91）；同理，b%喚甜91）。干是,0_對(duì)2二_二0（逋擁91）,即91|（十_才2） 注明：現(xiàn)考慮整數(shù)么的毎Q所成的數(shù)列：/X疋，若有正整數(shù)怎使閔刪）則有= ay(rncdm) 電勺m =切+心0廠k .

8、因而關(guān)于mod（）,數(shù)列么,滬,，呼，的項(xiàng)依次同余于色滬,，卅，忑這個(gè)數(shù)列相繼的上項(xiàng)成一段，各段是完全相同的，因而是周期數(shù)列。如下例：例2試求不大于100,且使11|（3浜+護(hù)+4）成立的自然數(shù)的和。解：通過逐次計(jì)算，可求出于關(guān)于modll的最小非負(fù)剩余（即為被11除所得的余數(shù)）為:3= 3(modl 1),32 s9(modl5?33=5(modll), 34 =5x3s 4(modll),35 = 4x3= l(modl 1)因而通項(xiàng)為于的數(shù)列的項(xiàng)的最小非負(fù)剩余構(gòu)成周期為5的周期數(shù)列:3, 9, 5, 4, 1, 3, 9, 5, 4, 1,類似地，經(jīng)過計(jì)算可得嚴(yán)的數(shù)列的項(xiàng)的最小非負(fù)剩余構(gòu)

9、成周期為10的周期數(shù)列:7, 5, 2, 3, 10, 4, 6, 9, 8, 1,于是由上兩式可知通項(xiàng)為3S+7S+ 4的數(shù)列的項(xiàng)的最小非負(fù)剩余，構(gòu)成周期為10 （即上兩式周期的最小公倍數(shù)）的周期數(shù)列：3, 7, 0, 0, 4, 0, 8, 7, 5, 6,這就表明，當(dāng)1曲山時(shí)，當(dāng)且僅當(dāng)23,4,6時(shí)，鄉(xiāng)+7H +4=0（modl5f即叫F +丁 +4）；又由于數(shù)列的周期性，故當(dāng)1氏+1也切貼+1）時(shí)，滿足要求的只有三個(gè)，即 = 10+3,104-4,10+6從而當(dāng)1?2 = l + l=0(mod 2) 又因?yàn)樽C明：不妨設(shè)匕是直角三角形的斜邊長(zhǎng)，則2 = 2若2、么，2、心，2、2 =

10、1（042）矛盾！若 3* 么，3、c,因?yàn)?3 力 1)訂1(10，則a2-t-i)2 = H- = 2(mod 3) 又c2 =l(mod3) 矛盾！從而 3 Q民.若 5 卞 幺,5 * b , 5、 c,因?yàn)?XI)%心 5)，(軟 2尸=-l(mod5),所以/+護(hù)三2或o(mod5)與/ l(modR矛盾！從而5 $民.又(2,3,5)=1,所以 301abe.下面講述中國(guó)剩余定理的應(yīng)用例6.證明：對(duì)于任意給定的正整數(shù)，均有連續(xù)力個(gè)正整數(shù)，其中每一個(gè)都有大于1的平 方因子。證明：由于素?cái)?shù)有無窮多個(gè)，故我們可以取肚個(gè)互不相同的素?cái)?shù)P-P2,而考慮同余組 x = -z(mod2),32

11、 2 2因?yàn)镻-PsPx顯然是兩兩互素的，故由中國(guó)剩余定理知，上述同余組有正整數(shù)解。于是，連續(xù)尬個(gè)數(shù)入+1皿+2,冰+“分別被平方數(shù)幾吐曲整除。注：（1）本題的解法體現(xiàn)了中國(guó)剩余定理的一個(gè)基本功效，它常常能將找連續(xù)肚個(gè)正整 數(shù)具有某種性質(zhì)”的問題轉(zhuǎn)化為“找力個(gè)兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較 容易解決的。（2）本題若不宜接使用素?cái)?shù)，也中以釆用下面的變異方法：由費(fèi)爾馬數(shù)理+1（30）兩兩互素,故將中的品轉(zhuǎn)化為呼（1,2,對(duì)后,相應(yīng)的同余式也 有解，同樣可以導(dǎo)出證明。例7.證明：對(duì)于任意給定的正整數(shù)乃，均有連續(xù)力個(gè)正整數(shù)，其中每一個(gè)都不是幕數(shù)。分析：我們來證明，存在連續(xù)力個(gè)正整數(shù)，其中

12、每一個(gè)數(shù)都至少有一個(gè)素因子，在這個(gè)數(shù)的 標(biāo)準(zhǔn)分解中僅出現(xiàn)一次，從而這個(gè)數(shù)不是無數(shù)。證明：取土個(gè)互不相同的素?cái)?shù)乃？2,，禺，考慮同余組=2 2 2因?yàn)镻4顯然是兩兩互素的，故由中國(guó)剩余定理知，上述同余組有正整數(shù)解。對(duì)于因?yàn)閰[必山就卅），故塚|（兀七），但由式可知*（x + O,即刃在（兀+）的標(biāo)準(zhǔn)分解中恰好出現(xiàn)一次，故兀+1冰+2,工+”都不是幕數(shù)。例8設(shè)總朮是給定的偶數(shù)，飛且上儀一 是偶數(shù)。證明：存在整數(shù)兀尹使得區(qū)對(duì)=（”同，且入+尹三做m。仏）。證明：我們先證明，當(dāng)為素?cái)?shù)毎卩時(shí)結(jié)論成立。實(shí)際上，能夠證明，存在兀刀使若p = 2，則條件表明上為偶數(shù)，此時(shí)可取若P A 2,則X=,y=k-1與x=2,y = k-2中有一對(duì)滿足要求。一般情形下，設(shè)沖，尸是力的一個(gè)標(biāo)準(zhǔn)分解，上面已經(jīng)證明，對(duì)每個(gè)刃存在整數(shù)召必使得刃卞 利i