mp=2p-1为合数时默森尼数的因数

mp=2p-1为合数时默森尼数的因数

mean尼数。2p-1是寻找大质数和大致数的重要工具，对研究mean尼数的结构和识别方法非常有用。1q+2p-1和mp11设p为奇质数,若Q是Mp=2p-1的因数,显然Q是奇数。Q|(2p-1)⇔2≡1(modQ)⇔2p+1≡2(modQ)⇔(2(p+1)/2)2≡2(modQ)这就说明:2是Q的平方剩余由P.42知Q≡±1(mod8)即Q=8k±1形式k∈N引理1若Q是Mp的因数,则(1)当Q≡1(mod8)时,Q=8kp+1(2)当Q≡-1(mod8)时,Q=2p(8m+r)+1k‚m∈Νr={1当p=8t+3或p=8t+73当p=8t+1或p=8t+5t∈Ν‚p＞2Q=2p(8m+r)+1k‚m∈Nr={1当p=8t+3或p=8t+73当p=8t+1或p=8t+5t∈N‚p＞2证明(i)首先设Q|Mp且Q为奇质数,Mp=2p-1≡0(modQ)由费马定理2Q-1≡1(modQ),p是奇质数是适合此关系最小质因数,所以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)当Q为Mp的因数时,Q1,Q2为质因数,Q=Q1.Q2=(8k1p+1)(8k2p+1)=8kp+1形式若Q有多个质因素,仍为形式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)当p=8t+12pr≡-2(mod8)⇒r=3当p=8t+32pr≡-2(mod8)⇒r=1当p=8t+52pr≡-2(mod8)⇒r=3当p=8t+72pr≡-2(mod8)⇒r=1在此t∈N。所以Q=2pk+1=2p(8m+r)+1m∈Νr={1当p=8t+3或p=8t+73当p=8t+1或p=8t+5t∈Ν‚p＞2所以Q=2pk+1=2p(8m+r)+1m∈Nr={1当p=8t+3或p=8t+73当p=8t+1或p=8t+5t∈N‚p＞2定理1.1设p为奇质数,则Mp=2p-1=(8kp+1).[2p(8m+r)+1]其中其中k,m,t∈N;(3)中(k,m)必为非负整数解。(3)证明由已知p为奇质数,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)的非负整数解。定理1.2Mp=2p-1为质数的充分必要条件Mp=[2p(8m+r)+1]p>2(4)证明:必要性若Mp=2p-1为质数,则(3)式中k=0,反证法,若不然k1≠0,k1∈N*(k1,m)为(3)式中非负整数解,即有Mp=2p-1=(8k1p+1).[2p(8m+r)+1]又因为:8k1p+1>0,(2p(8m+r)+1>1。这时Mp有两个大于1的因素,即Mp为合数,这与已知Mp为质数矛盾,所以(3)式中只有k=0,即Mp=2p-1=2p(8m+r)+1成立。充分性若(4)式成立,即Mp=2p(8m+r)+1成立,那么Mp=2p(8m+r)+1为质数,若不然,Mp为合数,那么Mp有质因数Q,由于p=8t+1,,p=8t+3,p=8t+5,p=8t+7,t∈N。所以Q≡-1(mod8)又在(3)式中k=0所以Mp的一切真质因数均以模8剩余为-1。又有Mp=2p-1≡-1(mod8)(-1)2k+1=-1故Mp的真质因数的个数为奇数且大于或等于3。设其真质因数QiQi=2p(8mi+r)+1i=1,2,3,…(注意:若Mp的质因数个数等于1,那么Mp为质数了,目的已达到)令A=Q1.Q2≡(-1)(-1)=1(mod8)A|Mp=2p-1由引理1.A=8kp+1k∈N*这与k=0矛盾。所以Mp=2p-1为质数.例1,M5=25-1=31为质数M5=25-1=(8×0×5+1).[2×5(8×0+3)+1]k=0非负整数解(0,0)例2.M7=27-1=127为质数M7=27-1=(8×0×7+1).[2×7(8×2+1)+1]它有非负整数解(0,1),k=0例3.M11=211-1=2047=89×23为合数M11=211-1=(8×11+1)[2×11(8×0+1)+1]k=1≠0它有解(1,0)2p+23+log2p1t-1的设计参数定理2.1若Mp=2p-1是合数,其质因数个数T满足下列不等式1＜Τ＜p+23+log2p1＜T＜p+23+log2p(5)证明:因Mp=2p-1是合数,k∈N*质因数形式:Qi=8kp+1k∈NQj=2p(8m+r)+1m∈N所以Mp=2p-1的质因数中至少有一个等于8p+1或至少有一个等于2rp+1的因数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]中最小正整数mi;则2p(8m+r)+1不是质因数,那么它必有因数Q(Q>1)Q|[2p(8m1+r)+1]即Q|Mp由引理1.Q≡±1(mod8)由于m1的最小性,所以只有Q≡-1(mod8)令A=2p(8m1+r)+1Q≡-1(mod8)即有A|Mp且A≡-1(mod8)由引理1可得:A=[2p(8m2+r)+1]形式而是m2<m1这与已知m1为最小正整数矛盾故[2p(8m1+r)+1]是质因数。3规划一个合数的[p/2]/2引理2若q为自然数几的最小质因数,则(nq)≡(-1)q-1u(modn)引理3若p为奇数,且3|p,p为质数的充分必要条件是(p2k+1)≡0(modp)中1≤k≤[√p/2][x]表示不超过x的最大整数定理3.1Mp=2p-1是质数的充要条件(Μp2kp+1)≡0(modΜp)(6)其中1≤k≤[p/2]/2]=2[p/2]-1证明:必要性显然充分性若(6)式成立,则Mp=2p-1为质数,若不然,Mp为合数,必有最小质因素QMp=2p-1=Qu,u≠0Q>3Q=2kp+1,(p,2)=1{2k±1}∩{2kp+1}={2kp+1}故Q=2k0p+1是Mp的最小质因数那么必有(Μp2k0p+1)≡(-1)q-1u≠0(modΜp)这与(6)式矛盾所以Mp=2p-1为质数。例5‚Μ11=211-1=20471≤k≤2[p/2]-1=25-1=24=16[√2047]=45{2pk