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

1、初等數(shù)論中的幾個重要定理基礎(chǔ)知識定義（歐拉（Euler）函數(shù)）一組數(shù) 可，句二汽 稱為是模端的既約剩余系，如果對任意 的1«父后，5哈=且對于任意的淳已工，若（4胞）=1,則有且僅有一個燈是以對模 股的剩余，即空.勺（mod隙）。并定義飆瓦）=£ = 02M中和股互質(zhì)的數(shù)的個數(shù)， 武聞稱為歐拉（Euler）函數(shù)。這是數(shù)論中的非常重要的一個函數(shù)，顯然加D = 1 ,而對于布1 ,加附）就是1,2 ,港-1中與胴互素的數(shù)的個數(shù)，比如說 P是素數(shù)，則有 雙="1。網(wǎng)跖）二r （1-司程！引理：P力質(zhì)物；可用容斥定理來證（證明略）。定理1 ：（歐拉（Euler）定理）設(shè)&

2、amp;間=1,則鼻時叫三l（m凸d冽）。分析與解答：要證丁三Mmod，我們得設(shè)法找出微個行相乘，由必刊個數(shù) 我們想到12,活中與港互質(zhì)的式成）的個數(shù):口卜/林），由于（見耀）=1,從而 厘的必犯也是與酒互質(zhì)的底加）個數(shù)，且兩兩余數(shù)不一樣，故的,出“缸樹三 坳必如皿四）三網(wǎng)的馬一/閭（mod柳），而（的做綿出處）=1, 故明三l（3d啕。證明：取模鶴的一個既約剩余系玩聞一，勿忌=飆曬）,考慮鼻瓦，魂打，間網(wǎng) ,由 于由與逃互質(zhì)，故0b4E J 仍與附互質(zhì)，且有血 叫（引工工，于是對每 個1W J G后都能找到唯一的一個1 - 6力-后，使得也.比儂淵明），這種對應(yīng)關(guān)系o口幽）的 口配 d%，（

3、口鳥）（n與）（m白財是 的，從而尸1月內(nèi),- JT 9c,1（也口%） = 1/_!, . / =1（*i冽）,故/叫三Igod網(wǎng)。證畢。這是數(shù)論證明題中常用的一種方法，使用一組剩余系，然后乘一個數(shù)組組成另外一組剩余系來解決問題。定理2：（費爾馬（Fermat）小定理）對于質(zhì)數(shù)戶及任意整數(shù)4有獷="皿心向。設(shè)，為質(zhì)數(shù)，若小是爐的倍數(shù)，則“'=0 =。若直不是尹的倍數(shù)，則Q0=1由引理及歐拉定理得 涯）寸心冽，:一小如心勃閑,由此即得。定理2”推論：設(shè)中為質(zhì)數(shù)，M是與尹互質(zhì)的任一整數(shù)，則小三Kmodp）。定理3：（威爾遜（Wilson ）定理）設(shè)戶為質(zhì)數(shù)，則（P-D!T（mo

4、dp）。分析與解答：受歐拉定理的影響，我們也找審一1個數(shù)，然后來對應(yīng)乘法。證明：對于（凡P）= l,在冗2見，（戶1）工中,必然有一個數(shù)除以尹余1,這是因為 小2工，（71）工則好是P的一個剩余系去0。從而對,土已1，2尹-嘰力E02產(chǎn)-D ,使得秒三；若科（mod/）, O,p）=l ,則工1-必）三0血©。），Pl®-%）,故 對于MM w12,，P-D,有五孫式小"p） 。即對于不同的犬對應(yīng)于不同的少,即 12 “'rP T中數(shù)可兩兩配對，其積除以P余1,然后有父，使工三單皿d中），即與它自 己配對，這時-1三0值10<1正，焦+1）5-1）。

5、（m0&審），支三一1或尤1值©日9）， »T 或"1。除了=Lp -外，別的數(shù)可兩兩配對，積除以夕余10故一5三MT）三Tmoapj。定義：設(shè)力（*）為整系數(shù)多項式（iMj”），我們把含有黑的一組同余式力三0Md %）（1公）稱為同余方組程。特別地，當 $6）均為"的一次整系 數(shù)多項式時，該同余方程組稱為一次同余方程組 .若整數(shù)匕同時滿足："C三式a?。?14厘，則剩余類% = 乙工三”mud臉）（其中網(wǎng)二網(wǎng)，啊%）稱為同 余方程組的一個解，寫作 一定理4:（中國剩余定理） 設(shè)啊，網(wǎng)nJ 函上是兩兩互素的正整數(shù)，那么對于任意整數(shù)%，口

6、戶工，一次同余方程組工三%（mod%） ,必有解，且解可以寫為：工=MM% +、汨2 + M上弧狐（mo d疝）% = （1<3這里想二切嗎僚上，罵,以及滿足見"小儂源嗎） '三，工k （即以為叫對模嗎f的逆）。中國定理的作用在于它能斷言所說的同余式組當模兩兩互素時一定有解，而對于解的 形式并不重要。定理5:（拉格郎日定理）設(shè)尹是質(zhì)數(shù)，號是非負整數(shù)，多項式,（五）"叫 / +瘋武+/ 是一個模戶為修次的整系數(shù)多項式（即”沖），則同余方程/（工）三0（modp）至多有 找個解（在模聲有意義的情況下）。定理6：若,為厘對模鶴的階，£為某一正整數(shù)，滿足&#

7、163;三Kmod啕，則3必為上的倍 數(shù)。以上介紹的只是一些系統(tǒng)的知識、 方法，經(jīng)常在解決數(shù)論問題中起著突破難點的作用。 另外 還有一些小的技巧則是在解決、 思考問題中起著排除情況、輔助分析等作用，有時也會起到fl（mod8）h為奇額時口 f0（mod9）理除h時f?三 ,? =1意想不到的作用，如：-00。的也為偶數(shù)時，一31口斯）壞整廂時。這里我們只介紹幾個較為直接的應(yīng)用這些定理的例子。典例分析例1.設(shè)3向）=1 ,求證：911（1-產(chǎn)）。證明：因為91 = 7*3,故由（91W）=1知（91戶）=1 ,從而fM=L（13M = l，但是 喇=6,如可=12 ,故由歐拉定理得：，、的仁1%

8、則.7） , /三i3od13）, 從而（m0d9D .同理，聲=Kmod91）。于是，三1-1三QMd91）,即叫（>-此。注明：現(xiàn)考慮整數(shù)值的募值"所成的數(shù)列：若有正整數(shù)化使臚三m白d第）， 則有”三口,其中?; = + r?0<r c.k ；因而關(guān)于皿忒，數(shù)列風速土由、的項依次同余于0心上k,樂這 個數(shù)列相繼的七項成一段，各段是完全相同的，因而是周期數(shù)列。如下例：例2.試求不大于100,且使1 "6 ” *的成立的自然數(shù)冷的和。解：通過逐次計算，可求出 于關(guān)于mod 11的最小非負剩余（即為被 11除所得的余數(shù)）為：3-Wmodl ）寸三%modM）,下三

9、”延 4（modl 1）,35 4x3 l（niodl 1）因而通項為丁的數(shù)列的項的最小非負剩余構(gòu)成周期為5的周期數(shù)列：3, 9, 5, 4, 1, 3, 9, 5, 4, 1,類似地，經(jīng)過計算可得 7"的數(shù)列的項的最小非負剩余構(gòu)成周期為10的周期數(shù)列：7, 5, 2, 3, 10, 4, 6, 9, 8, 1,于是由上兩式可知通項為 于+ T +4的數(shù)列的項的最小非負剩余，構(gòu)成周期為10 （即上兩式周期的最小公倍數(shù)）的周期數(shù)列：3, 7, 0, 0, 4, 0, 8, 7, 5, 6,這就表明，當1孔£1口時，當且僅當打二工46時，號”+門=0融出!），即11|（?!+7

10、、4）；又由于數(shù)列的周期性，故當時，滿足要求的第只有三個，即是工10上+30文+ 4,10k+ 6從而當1W盟3口口時，滿足要求的總的和為：9P92/10尢+3）+（1證+4）+。及+0 =工*尢+13=加工七+10乂13二列乂45+130=1413?；?#163;二下面我們著重對Fetmat小定理及其應(yīng)用來舉例：1 i 1 i 7X + - X + X例3.求證：對于任意整數(shù) K, 5315 是一個整數(shù)。1 51 57又 + _工 +k證明：令廣（工）=5315 ，則只需證=%,+5/+7工是15的倍數(shù)即可。由3, 5是素數(shù)及Fetmat小定理得/三Md 5） , 1 一（mod勾 則媛+

11、5工、7工三3工+ 7工三03cd 5）.五$ + 5/ +7" 2元+ ” 0（m凸d 3）而（3, 5） =1,故婷4刀,7工三°（m心血今，即15J是15的倍數(shù)。所以/是整數(shù)。（總為任意整數(shù)）。證明：令，=廬一片，則/5）二屋®-1）（犬+ 川+1）（產(chǎn)一月+1）（/日）；所以?。幸蚴揭?鑄-%#一%/一艘由Fetmat小定理，知13|屋口一科7|弱 一/51再5 f 3|浦一2 |M -制又13, 7, 5, 3, 2兩兩互素，所以2730=13乂7乂5乂 3乂2能整除忽“一片。例5.設(shè)凡3c是直角三角形的三邊長。如果 口" 是整數(shù)，求證：

12、 詆 可以被30整除。證明：不妨設(shè)亡是直角三角形的斜邊長，則 C2=a2。若2未出，2卡機2卡c,則=/*/=1+1三082）,又因為三1他僅12）矛盾！所以2| l沱二.若3卡出，3卡機3卡c,因為區(qū)±l）、】Md引，則M+川三+ 1三2解咫， 又d= l（m心d可，矛盾！從而3|施.若5卡爾5在屋5卡c,因為毋0d5）,伊士打三一l（mod5）,所以M十產(chǎn)三±2或0（mod5）與/三±130d與矛盾！從而5心上.又（2,3,5）=1 ,所以 30| 阪.下面講述中國剩余定理的應(yīng)用例6.證明：對于任意給定的正整數(shù) 浮，均有連續(xù)抬個正整數(shù)，其中每一個都有大于1的平

13、方因子。證明：由于素數(shù)有無窮多個， 故我們可以取其個互不相同的素數(shù) 戶1，戶如一，戶R ,而考慮同余組元三一3凸d尸三12/243因為當，力 顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。12于是，連續(xù)行個數(shù)及+ 1潭+ 4+冷分別被平方數(shù)尸】，入，必 整除。注：（1）本題的解法體現(xiàn)了中國剩余定理的一個基本功效，它常常能將“找連續(xù)首個正整數(shù)具有某種性質(zhì)”的問題轉(zhuǎn)化為“找 抬個兩兩互素的數(shù)具有某種性質(zhì)”，而后者往往是比較 容易解決的。（2）本題若不直接使用素數(shù)，也中以采用下面的變異方法：由費爾馬數(shù)凡二23+1依生0）22兩兩互素，故將中的Pi轉(zhuǎn)化為罵（工=12/*,力）后，相應(yīng)的同

14、余式也有解，同樣可以導(dǎo)出證明。例7.證明：對于任意給定的正整數(shù) 融，均有連續(xù)理個正整數(shù)，其中每一個都不是哥數(shù)。分析：我們來證明，存在連續(xù) 器個正整數(shù)，其中每一個數(shù)都至少有一個素因子，在這個數(shù)的 標準分解中僅出現(xiàn)一次，從而這個數(shù)不是哥數(shù)。證明：取片個互不相同的素數(shù) 九聲如心，考慮同余組工工 T（mMp因為戶、尸國顯然是兩兩互素的，故由中國剩余定理知，上述同余組有正整數(shù)解。對于三"因為支+工二嚴依高尸?），故/G+D ,但由式可知 V （工+0，即跖在5+工）的標準分解中恰好出現(xiàn)一次，故 木+ L工+工，/+并都不是哥數(shù)。例8.設(shè)外1t是給定的偶數(shù)，品 °且上5-D是偶數(shù)。證明：存在整數(shù)工尸使得（匕用=3/） = 1,且工+，三上加內(nèi)量）。證明：我們先證明，當 期為素數(shù)哥P時結(jié)論成立。實際上，能夠證明，存在 兀尸使若尸=2 ,則條件表明k為偶數(shù)，此時可取=1,7 = -1 ；若尸> 2 ,則工=上一1與左=2,y = A：2中有一對滿足要求。一般情形下，設(shè)及工戶，"1P： J = 12,I是抬的一個標準分解，上面已經(jīng)證明，對每個烏存在整數(shù)再，乃使得已卡