mp=2p-1為合數(shù)時(shí)默森尼數(shù)的因數(shù)

mp=2p-1為合數(shù)時(shí)默森尼數(shù)的因數(shù)

mean尼數(shù)。2p-1是尋找大質(zhì)數(shù)和大致數(shù)的重要工具，對(duì)研究mean尼數(shù)的結(jié)構(gòu)和識(shí)別方法非常有用。1q+2p-1和mp11設(shè)p為奇質(zhì)數(shù),若Q是Mp=2p-1的因數(shù),顯然Q是奇數(shù)。Q|(2p-1)?2≡1(modQ)?2p+1≡2(modQ)?(2(p+1)/2)2≡2(modQ)這就說(shuō)明:2是Q的平方剩余由P.42知Q≡±1(mod8)即Q=8k±1形式k∈N引理1若Q是Mp的因數(shù),則(1)當(dāng)Q≡1(mod8)時(shí),Q=8kp+1(2)當(dāng)Q≡-1(mod8)時(shí),Q=2p(8m+r)+1k?m∈Νr={1當(dāng)p=8t+3或p=8t+73當(dāng)p=8t+1或p=8t+5t∈Ν?p＞2Q=2p(8m+r)+1k?m∈Nr={1當(dāng)p=8t+3或p=8t+73當(dāng)p=8t+1或p=8t+5t∈N?p＞2證明(i)首先設(shè)Q|Mp且Q為奇質(zhì)數(shù),Mp=2p-1≡0(modQ)由費(fèi)馬定理2Q-1≡1(modQ),p是奇質(zhì)數(shù)是適合此關(guān)系最小質(zhì)因數(shù),所以p|(Q-1)且2|(Q-1),(p,2)=1于是有2p|(Q-1)即有Q=2pk+1形式k∈N。又有Q≡1(mod8)且(p,8)=1,所以有Q=8kp+1形式k∈N。(ii)當(dāng)Q為Mp的因數(shù)時(shí),Q1,Q2為質(zhì)因數(shù),Q=Q1.Q2=(8k1p+1)(8k2p+1)=8kp+1形式若Q有多個(gè)質(zhì)因素,仍為形式Q=8kp+1即(1)得證。(2)Q|Mp=2p-1且Q≡-1(mod8)又有Q=2kp+1Q≡-1(mod8)}?2kp≡-2(mod8)Q=2kp+1Q≡?1(mod8)}?2kp≡?2(mod8)令k=8m+rr=1,2,3,4,5,6,72kp=16mp+2rp≡2pr≡-2(mod8)當(dāng)p=8t+12pr≡-2(mod8)?r=3當(dāng)p=8t+32pr≡-2(mod8)?r=1當(dāng)p=8t+52pr≡-2(mod8)?r=3當(dāng)p=8t+72pr≡-2(mod8)?r=1在此t∈N。所以Q=2pk+1=2p(8m+r)+1m∈Νr={1當(dāng)p=8t+3或p=8t+73當(dāng)p=8t+1或p=8t+5t∈Ν?p＞2所以Q=2pk+1=2p(8m+r)+1m∈Nr={1當(dāng)p=8t+3或p=8t+73當(dāng)p=8t+1或p=8t+5t∈N?p＞2定理1.1設(shè)p為奇質(zhì)數(shù),則Mp=2p-1=(8kp+1).[2p(8m+r)+1]其中其中k,m,t∈N;(3)中(k,m)必為非負(fù)整數(shù)解。(3)證明由已知p為奇質(zhì)數(shù),Mp=2p-1我們有Mp|Mp且Mp≡-1(mod8)由引理1:Mp=2p-1=2p(8m+r)+1=(0p+1)[2p(8m0+r)+1]m0∈N即(0,m0)為(3)的非負(fù)整數(shù)解。定理1.2Mp=2p-1為質(zhì)數(shù)的充分必要條件Mp=[2p(8m+r)+1]p>2(4)證明:必要性若Mp=2p-1為質(zhì)數(shù),則(3)式中k=0,反證法,若不然k1≠0,k1∈N*(k1,m)為(3)式中非負(fù)整數(shù)解,即有Mp=2p-1=(8k1p+1).[2p(8m+r)+1]又因?yàn)?8k1p+1>0,(2p(8m+r)+1>1。這時(shí)Mp有兩個(gè)大于1的因素,即Mp為合數(shù),這與已知Mp為質(zhì)數(shù)矛盾,所以(3)式中只有k=0,即Mp=2p-1=2p(8m+r)+1成立。充分性若(4)式成立,即Mp=2p(8m+r)+1成立,那么Mp=2p(8m+r)+1為質(zhì)數(shù),若不然,Mp為合數(shù),那么Mp有質(zhì)因數(shù)Q,由于p=8t+1,,p=8t+3,p=8t+5,p=8t+7,t∈N。所以Q≡-1(mod8)又在(3)式中k=0所以Mp的一切真質(zhì)因數(shù)均以模8剩余為-1。又有Mp=2p-1≡-1(mod8)(-1)2k+1=-1故Mp的真質(zhì)因數(shù)的個(gè)數(shù)為奇數(shù)且大于或等于3。設(shè)其真質(zhì)因數(shù)QiQi=2p(8mi+r)+1i=1,2,3,…(注意:若Mp的質(zhì)因數(shù)個(gè)數(shù)等于1,那么Mp為質(zhì)數(shù)了,目的已達(dá)到)令A(yù)=Q1.Q2≡(-1)(-1)=1(mod8)A|Mp=2p-1由引理1.A=8kp+1k∈N*這與k=0矛盾。所以Mp=2p-1為質(zhì)數(shù).例1,M5=25-1=31為質(zhì)數(shù)M5=25-1=(8×0×5+1).[2×5(8×0+3)+1]k=0非負(fù)整數(shù)解(0,0)例2.M7=27-1=127為質(zhì)數(shù)M7=27-1=(8×0×7+1).[2×7(8×2+1)+1]它有非負(fù)整數(shù)解(0,1),k=0例3.M11=211-1=2047=89×23為合數(shù)M11=211-1=(8×11+1)[2×11(8×0+1)+1]k=1≠0它有解(1,0)2p+23+log2p1t-1的設(shè)計(jì)參數(shù)定理2.1若Mp=2p-1是合數(shù),其質(zhì)因數(shù)個(gè)數(shù)T滿足下列不等式1＜Τ＜p+23+log2p1＜T＜p+23+log2p(5)證明:因Mp=2p-1是合數(shù),k∈N*質(zhì)因數(shù)形式:Qi=8kp+1k∈NQj=2p(8m+r)+1m∈N所以Mp=2p-1的質(zhì)因數(shù)中至少有一個(gè)等于8p+1或至少有一個(gè)等于2rp+1的因數(shù)r=1,3。所以2p>Mp=2p-1>(8p)T-1.(2p)p>(T-1)(log2p+3)+log2p+1p>Tlog2p+3T-log2p-3+log2p+1p+2>T(3+log2p)所以1＜Τ＜p+23+log2p1＜T＜p+23+log2p例4?Μ11=211-1=89×23=20741＜Τ＜p+23+log2p≤133+3.4=2.031＜Τ＜2.03∴Τ=2定理2.2適合(3)式Mp=2p-1=(8kp+1)[2p(8m+r)+1]中最小正整數(shù)mi;則2p(8m+r)+1不是質(zhì)因數(shù),那么它必有因數(shù)Q(Q>1)Q|[2p(8m1+r)+1]即Q|Mp由引理1.Q≡±1(mod8)由于m1的最小性,所以只有Q≡-1(mod8)令A(yù)=2p(8m1+r)+1Q≡-1(mod8)即有A|Mp且A≡-1(mod8)由引理1可得:A=[2p(8m2+r)+1]形式而是m2<m1這與已知m1為最小正整數(shù)矛盾故[2p(8m1+r)+1]是質(zhì)因數(shù)。3規(guī)劃一個(gè)合數(shù)的[p/2]/2引理2若q為自然數(shù)幾的最小質(zhì)因數(shù),則(nq)≡(-1)q-1u(modn)引理3若p為奇數(shù),且3|p,p為質(zhì)數(shù)的充分必要條件是(p2k+1)≡0(modp)中1≤k≤[√p/2][x]表示不超過(guò)x的最大整數(shù)定理3.1Mp=2p-1是質(zhì)數(shù)的充要條件(Μp2kp+1)≡0(modΜp)(6)其中1≤k≤[p/2]/2]=2[p/2]-1證明:必要性顯然充分性若(6)式成立,則Mp=2p-1為質(zhì)數(shù),若不然,Mp為合數(shù),必有最小質(zhì)因素QMp=2p-1=Qu,u≠0Q>3Q=2kp+1,(p,2)=1{2k±1}∩{2kp+1}={2kp+1}故Q=2k0p+1是Mp的最小質(zhì)因數(shù)那么必有(Μp2k0p+1)≡(-1)q-1u≠0(modΜp)這與(6)式矛盾所以Mp=2p-1為質(zhì)數(shù)。例5?Μ11=211-1=20471≤k≤2[p/2]-1=25-1=24=16[√2047]=45{2pk