梅森素数的判定

yangchuanju

梅森素数的判定
若合数Mp=2^p-1=m*n，m是较小的素数，则m≡1(mod p)； 若m≡1(mod p)，对于每一个小于√ (Mp)的素数m，m不整除Mp，则Mp=2^p-1是素数。
若m≡1(mod p)，p＜m≤√ (Mp)不存在素数m，则Mp=2^p-1是素数。
根据费马小定理，(2，p)=1，2^(p-1) ≡1(mod p)，则2^p≡2(mod p)，则2^p-1≡1(mod p)。
也就是说小于p的素数都不能整除Mp=2^p-1，所以只用验证p＜m≤√ (Mp)就行了。

例如：1、M11=2^11-1=23×89，23≡1(mod 11)，其它梅森合数自已验证。
2、M13=2^13-1=8191是一个素数。
证明：设m=13k+1，13k+1<√ (8191)，k=1、2、3、4、5、6，k=4或6时m是素数，m=13k+1=53或m=13k+1=79，但是53不整除8191，79 不整除8191，所以8191是一个素数。
3、M7=2^7-1=127是一个素数
设m=7k+1，7k+1＜√ (127)，k=1，m=7k+1=8不是素数，也就是说p＜m≤√ (Mp)内没有素数m，所以M7=2^7-1=127是一个素数。

原文来自网络，作者和出处不详。原文为图片，译者根据原文进行了改写。

yangchuanju

本判定方法也属于试除法，但这种试除法要比太阳试除法强的多。

太阳

1楼帖，2^p-1是否为素数，事实上根据素数乘积形式进行判断的，作者应该也发现了2^p-1素数乘积形式
\(素数乘积形式:2^a-1＝\left( ac_1+1\right)\times\left( ac_2+1\right)\times\left( ac_3+1\right)\times\cdots\times\left( ac_n+1\right)\)

太阳

2^67-1，验证多少次才能给出答案？

太阳

证明：设m=13k+1，13k+1<√ (8191)，k=1、2、3、4、5、6，k=4或6时m是素数，m=13k+1=53或m=13k+1=79，但是53不整除8191，79 不整除8191，所以8191是一个素数。
试除2次可以判断2^13-1是素数
2^67-1，验证多少次才能给出答案？

yangchuanju

太阳 发表于 2022-2-2 09:17
证明：设m=13k+1，13k+1

令r1=4，那么对于2^67-1有：               
ri        ri+1        余数
1        ——        4
2        14        14
3        194        60
4        3598        47
5        2207        63
6        3967        14
               
试验6次余数循环，不会有余数0出现，               
2^67-1不是素数！               
2^67-1=147573952589676412927<21>=193707721*761838257287<12>               

太阳

2^67-1，k=1，2，3，验证(181313464*k)^2＞2^67-1，判断2^67-1是否为素数，1楼帖，确实提高验证效果

太阳

，，，，，，，，

yangchuanju

太阳 发表于 2022-2-2 09:56
2^67-1，k=1，2，3，验证(181313464*k)^2＞2^67-1，判断2^67-1是否为素数，1楼帖，确实提高验证效果

对于2^67-1，如果老老实实地用太阳试除法，需试除到k=（193707721-1）/67=1445580*2时，其中k只取偶数即可，为1445580次；
1楼法只用1445580个2k*67+1中的素数约10万个素数试除即可。
然而用6楼的LL检验法仅试验6次即可。

但用太阳的试除法要验证2^7897466719774591-1是不是素数是不可能的，想从中找出亿位素数也是不可能的。

太阳

太阳 发表于 2022-2-2 10:05
，，，，，，，，

\(素数乘积形式:2^a-1＝\left( ac_1+1\right)\times\left( ac_2+1\right)\times\left( ac_3+1\right)\times\cdots\times\left( ac_n+1\right)\)
数学发现2^a-1素数乘积形式