为什么梅森合数Mp的合数因子都是以2为基的强伪素数？

nyy

梅森合数Mp的定义：Mp=2^p-1为合数，并且p为素数。
比如
2^29 - 1分解质因数得到
{{233, 1}, {1103, 1}, {2089, 1}}
排除M29，这个数有三个合数因子，我测试了一下，都通过了miller rabin测试，以2为基。

MR[233*1103,2]
MR[233*2089,2]
MR[1103*2089,2]

结果都返回true

我从维基百科上看到这个结论，但是谁能证明一下呢？

1. Clear["Global`*"];(*Clear all variables*)
   
2. (*miller rabin子函数*)
   
3. MR[n_,a_]:=Module[{s,m,t1,k},
   
4.     s=0;m=n-1;While[Mod[m,2]==0,m=m/2;s=s+1];
   
5.     t1=PowerMod[a,m,n];
   
6.     If[t1==1,Return[True]];
   
7.     k=0;While[k<s-1&&t1!=n-1,k=k+1;t1=Mod[t1^2,n]];
   
8.     If[t1==n-1,Return[True],Return[False]]
   
9. ]
   
10. MR[233*1103,2]
    
11. MR[233*2089,2]
    
12. MR[1103*2089,2]
    

复制代码

nyy

对于M43的两个因子。
2^43 - 1=8796093022207={{431, 1}, {9719, 1}, {2099863, 1}}
MR[431*9719,2]
返回true

nyy

对M163进行测试，
结果也是如此

代码如下

1. (*选择大于1的合数因子*)
   
2. aaa=Select[Divisors[2^163-1],And[#>1,Not@PrimeQ[#]]&]
   
3. (*对合数因子进行以2为基的miller rabin测试*)
   
4. bbb=MR[#,2]&/@aaa
   
5. (*统计测试结果*)
   
6. ccc=Tally[bbb]
   

复制代码

输出结果
{105826244207, 16563351642751, 77606621039153, 4158308781501239, \
19483514009133817, 3049454284123621481, 11663266256111186911, \
2928118869890693955479, 458293335998086701515047, \
2147306778162773425682441, 5444966325981078575081927, \
25512073120557082585375081, 3993011765633573362223747033, \
322712293769748729825537010567, 1002464733455002280154597767137, \
3834132933069162270508264798247, 600097759221772839888520270348471, \
2811723157900302652316835934504313, \
150657417396751927677594034629718319, \
705896569174407860595941718304957057, \
110483114904628180514196887638679762801, \
422565438231362784708740322088849687831, \
106087077691514234145382293018897081225359, \
16604175889671855364937107652554265512073887, \
77797900674357884219057394596540380453714961, \
11692013098647223345629478661730264157247460343807}

{True, True, True, True, True, True, True, True, True, True, True, \
True, True, True, True, True, True, True, True, True, True, True, \
True, True, True, True}

{{True, 26}}

nyy

证明：对于Mp=2^p-1来说，他的任何素数因子q，都有q=2*k*p+1

而Mp=2^p-1=0(mod q)

q1=1(mod p)
q2=1(mod p)
所以q1*q2=1(mod p)

剩下的见三楼吧
https://bbs.emath.ac.cn/thread-18615-1-1.html


https://bbs.emath.ac.cn/forum.ph ... 9&fromuid=14149