利用階與指數(shù)型同余式解競賽題

《利用階與指數(shù)型同余式解競賽題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、2014年第4期5利用階與指數(shù)型J-al余式解競賽題王蕾楊曉嗚(1．浙江省杭州高級中學(xué)，3100032．浙江大學(xué)出版社，310028)中圖分類號：0156．1文獻(xiàn)標(biāo)識碼：A文章編號：1005—6416(2014)04—0005—04(本講適合高中)(ii)設(shè)P=2，且0—1、口一1含素因子2的冪次分別為、(>，v>13)．則r‘’=2，其中，1定義與符號0，1≤≤“；，’歐拉定理給定整數(shù)，n>1，設(shè)整數(shù)0與m={1，<<；互素．則口i1(roodm)．【一+1．后≥．使得0三1(roodm)成立的最小正整數(shù)，稱3例題

2、選講為n對于模m的階，記作8(口)．滿足(0)=(m)的n(若存在)，稱為模m例1已知P為素數(shù)，為正整數(shù)．試求余數(shù)的原根．S=1+2+?+(P—1)(roodP)．設(shè)、g、h∈Z[]．若／．()一g()=mh()，解若(p一1)l，則當(dāng)(，P)=1時，稱與g模m同余，記作iE1(roodP)．)-g()(roodm)．于是，S-p一1蘭一1(modp)．若(p一1)}，設(shè)0為模P的一個原根．則2主要性質(zhì)P十(口一1)，(1)對任意非負(fù)整數(shù)、有且(1≤≤p一1)也是模P的縮系．口一n(roodm)當(dāng)且僅當(dāng)(0)I(u一

3、)．故S-∑(=0S(modp)，特別地，1，0，0，?，0‘。模m互不同余；‘=l(0一1)S-0(modP)．(0)I(m)；從而，S-0(roodp)．對于素數(shù)P，。(n)l(P一1)．例2整數(shù)n>l滿足nI(2+1)．m(0)(1)證明：要么凡=3，要么9In；(2)凡是否恰含2000個互不相同的素因子；若6(口)與(6)互素，則(第4l屆imo)6(ab)=(口)8(6)．(3)試求滿足nI(2“+1)的所有整數(shù)n>1．(3)合模性質(zhì)：[，](0)=[8m(0)，6(口)]，(第31屆IMO)其中，[，y]

4、表示、Y的最小公倍數(shù)．(1)證明顯然，n為奇數(shù)，設(shè)P是凡的最小(4)對于給定的素數(shù)P和整數(shù)0，記t(0)=r．素因子．則2三一1(modP)，2三1(roodP)；(i)設(shè)P為奇素數(shù)，n一1含素因子p的冪次(2)≤p一11，且(m，3)=1．6中等數(shù)學(xué)設(shè)9是m的最小素因子．=3(M+3Ⅳ)同理，

5、s=(2)=2或6．含素因子3的冪次為+2．由于n含素因子3的冪次為2，故由于ql(2一1)，qf(2i一1)，故Jj}+l≥2=

6、j}=1．ql(2i+1)，最后證明m=l，見(1)．即qI(2+1)或qI(2+1)，矛盾．因此，滿足條件的n=3．(2)解歸納證明：對任意的正整數(shù)，存在例3求所有整數(shù)對(m，n)(m、n／>2)，使得正奇數(shù)n=n()恰含個互不相同的素因子(其對任意的整數(shù)均有中一個是3)且滿足蘭(roodm)．n()I(2’+1)．解若有素數(shù)P使得Plm，取=p得出矛盾．當(dāng)=1時，(1)=3．故m=p

7、。p：?p(pi為不同的素數(shù))．假設(shè)當(dāng)時，結(jié)論成立．進(jìn)而，“；(roodm)等價于同余式組由于()是3的奇數(shù)倍，從而，2+1可被“E(roodP)(1≤≤．j})．2+1=9整除．取為模p的原根得而2一2‘+1=(2‘+1)(2‘¨一2)+3(Pi一1)I(n一1)．含素因子3的冪次為l，且從而，=1+-[pl一1，P2—1，?，P一1]．2(¨一2()+1，——一，另一方面，對任意互不相同的素數(shù)P，當(dāng)(，P)=1時，均有故2‘一2‘’+1有素因子P，且(p，2‘’+1)=1．6()I(P一1)．從而，(P，())=

8、1．從而，。()I(n一1)．取17,(+1)=3p·n(．j})．故三(modP)(當(dāng)PI時，此式也成立)．則n(Ij}+1)恰含

9、j}+1個互不相同的素因子因此，滿足要求的所有整數(shù)數(shù)對(m，)為(其中一個是3)，且2‘“+1可被2‘+1整除，n=plp2’，n=1+[pl一1，P2—1，?，P一1]，而2‘+1=(2‘’+1)(2‘¨一2‘+1)可其中，k,u為任意正整數(shù)，pi為任意互不相同的素數(shù)被3p·n(

10、j})：n(+1)整除，因此，當(dāng)Il}+1時，結(jié)例4求所有素數(shù)組(p，q，r)，使得論也成立．PI(q+

11、1)，gl(rP+1)，rI(P+1)．綜上，結(jié)論成立．(2003，美國國家隊選拔考試)(3)解上面已證n的最小素因子為3．解由P,q、r兩兩互素，知其互不相同．令n=3km(m是與3互素的奇數(shù))．(1)P、g、r同為奇素數(shù)．對非負(fù)整數(shù)，只需歸納證明2+1含素因子由PI(q+I)，得。(q)=2或2r．3的冪次為+1．若。(g)=2r，則當(dāng)=0