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

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

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

3、H, EH。心/円二宀険如）訐么小）=l（mod m）證畢。這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個數(shù)組組成另外一組剩 余系來解決問題。定理2：（費爾馬（Fermat）小定理）對于質(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個數(shù)，然后來對應(yīng)乘法。證明：對于（兀去）=1,在兀2兀，0

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

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

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

7、意想不到的作用，如：t0（mod4）偽偶數(shù)時 只介紹幾個較為直接的應(yīng)用這些定理的例子。典例分析 例1設(shè)（9心1,求證:叫（尹-滬）。 證明:因為91 = 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_對2二_二0（逋擁91）,即91|（十_才2） 注明：現(xiàn)考慮整數(shù)么的毎Q所成的數(shù)列：/X疋，若有正整數(shù)怎使閔刪）則有= ay(rncdm) 電勺m =切+心0廠k .

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

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

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

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

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