2^99368963-1是梅森素数吗？

yangchuanju · 发表于 2024-8-19 06:38

A005384 A005385 A002515
100000 10000 10000
热尔曼素数安全素数模4余3素数Lucasian primes: p == 3 (mod 4) with 2*p+1 prime.
1 2 1 5 1 3
2 3 2 7 2 11
3 5 3 11 3 23
4 11 4 23 4 83
5 23 5 47 5 131
6 29 6 59 6 179
7 41 7 83 7 191
8 53 8 107 8 239
9 83 9 167 9 251
10 89 10 179 10 359
11 113 11 227 11 419
12 131 12 263 12 431
13 173 13 347 13 443
14 179 14 359 14 491
15 191 15 383 15 659
16 233 16 467 16 683
17 239 17 479 17 719
18 251 18 503 18 743
19 281 19 563 19 911
20 293 20 587 20 1019
21 359 21 719 21 1031
22 419 22 839 22 1103
23 431 23 863 23 1223
24 443 24 887 24 1439
25 491 25 983 25 1451
26 509 26 1019 26 1499
27 593 27 1187 27 1511
28 641 28 1283 28 1559
29 653 29 1307 29 1583
30 659 30 1319 30 1811
……
9999 1349339 9999 2698679 9999 3025079
10000 1349363 10000 2698727 10000 3025163
56032 9999653
56033 10000079
100000 19391363

yangchuanju · 发表于 2024-8-19 08:37

若梅森数的指数是卢卡斯素数（Lucasian primes），它的指数皆模4余3，且它的2倍加1都是素数，这些梅森数一定含有一个2p+1型素因子，肯定都不是素数了（最小的一个素数3除外）。

A005384提供了10万个热尔曼素数，其中约有5万个素数是卢卡斯素数，以这5万个热尔曼素数为指数的梅森数都有一个2p+1型素因子，都是梅森合数（最小的一个模4余3的素数3除外）。

yangchuanju · 发表于 2024-8-19 19:31

本帖最后由 yangchuanju 于 2024-8-19 19:35 编辑

如何快速寻找梅森数的素因子
已知知道，所有梅森数都是模8余7的正整数（梅森素数2^2-1=3除外）；
每一个梅森数如果是合数，它的素因子及复合因子都是2kp+1型的正整数；
（每一个梅森素数也可表示成2kp+1形式的正整数，如梅森素数2^5-1=31=2*6*5+1，2^7-1=127=2*9*7+1）
所有梅森数之中都不含有幂因子，即没有平方梅森因子，更没有立方梅森因子，……；
各个梅森数的素因子（及梅森素数）互不相同，即没有某个素数p即是梅森数Mp1的素因子，
又是其它梅森数Mp2的素因子的现象，如素数23是梅森数2^11-1的一个素因子，它不再是其它梅森数的素因子。
梅森数的指数都是素数，除2以外可分成模4余3，模4余1两大类。

要找到某个梅森数Mp=2^p-1的素因子可用不大于Mp平方根的正整数从小到大逐个试除，直到某个正整数能够整除，它便是那个梅森数的一个最小的（素）因子；
由于偶数都不是梅森数的因子，故试除过程中舍弃所有偶数，只用奇数试除即可；
又由于奇合数一会是梅森数的最少因子，故试除过程中只用不大于Mp平方根的素数从小到大逐个试除，直到某个小素数p1能够整除，它便是那个梅森数的一个最小的素因子p1；
找到某个素因子p1后，将Mp除以这个素因子p1，再用不小于p1、不大于Mp/p1平方根的素数从小到大逐个试除，直到某个素数p2能够整除，它便是那个梅森数的第2素因子p2；
找到它的素因子p1、p2后，如果Mp/(p1*p2)还是合数，可将Mp除以p1*p2，再用不小于p1*p2、不大于Mp/(p1*p2)平方根的素数从小到大逐个试除，直到某个素数p3又能够整除，它便是那个梅森数的第3素因子p3；……
直到Mp/(p1*p2*p3*……)是素数时为止。

由于梅森数的素因子不包括所有类型的素数，只是各种素数中的某些类型，故只用可能是梅森数因子类型的素数试除即可。
已知对于模4余3的梅森数，它们的各个素因子减1与梅森数指数的比分别是2,8,10,16,18,24,26,32,34，……8k,8k+2；
对于模4余1的梅森数，它们的各个素因子减1与梅森数指数的比分别是6,8,14,16,22,24,30,32，……8k-2,8k。
故对于各类梅森数在试除过程中，不必用不大于Mp平方根的素数从小到大逐个试除，
只需用2p+1,8p+1,10p+1,16p+1,18p+1,……8kp+1,(8k+2)p+1
或6p+1,8p+1,14p+1,16p+1,……(8k-2)p+1,8kp+1试除即可。

对于模4余3的梅森数Mp=2^p-1，如果2p+1也是素数，这个2p+1型素数一定是那个梅森数的一个（最小）素因子；
如梅森数2^39971-1的最小素因子是79943，第2素因子是什么至今无人知晓；梅森数2^39983-1的最小素因子是79967，第2素因子是什么至今无人知晓；……
对于模4余1的梅森数Mp=2^p-1，不论2p+1是素数还是合数，这个2p+1型奇数都不是那个梅森数的素因子。
如梅森数2^39953-1、2^39989-1的指数都是热尔曼素数，2p+1都是素数，但它们不是对应梅森数的素因子；
至今只知这两个梅森数是合数，但没有找到一个素因子。
对于指数是模4余3型梅森数，当8p+1,10p+1,16p+1,18p+1,……8kp+1,(8k+2)p+1是素数时，它们不一定是那个梅森数的素因子；
对于指数是模4余3型梅森数，当6p+1,8p+1,14p+1,16p+1,……(8k-2)p+1,8kp+1是素数时，它们不一定是那个梅森数的素因子。

yangchuanju · 发表于 2024-8-19 20:33

以下各列梅森数的最小素因子都是16p+1，从分解式看16p+1都是素数，16p+1数前后也有素数，但它们不是对应梅森数的素因子——
p 3967 4447 5011 9127 9343 9883
2倍数加1 7935 8895 10023 18255 18687 19767
8倍数加1 31737 35577 40089 73017 74745 79065
10倍数加1 39671 44471 50111 91271 93431 98831
16倍数加1 63473 71153 80177 146033 149489 158129
18倍数加1 71407 80047 90199 164287 168175 177895
2倍分解 3*5*23*23 3*5*593 3*13*257 3*5*1217 3*6229 3*11*599
8倍分解 3*71*149 3*3*59*67 3*7*23*83 3*3*7*19*61 3*3*5*11*151 3*3*5*7*251
10倍分解 39671素 7*6353 50111素 107*853 13*7187 23*4297
16倍分解 63473素 71153素 80177素 146033素 149489素 158129素
18倍分解 7*101*101 11*19*383 90199素 41*4007 5*5*7*31*31 5*47*757

以下各列梅森数的最小素因子都是18p+1，从分解式看18p+1都是素数，18p+1数前后也有素数，但它们不是对应梅森数的素因子——
p 4099 4127 7459 7759 10247 10891
2倍数加1 8199 8255 14919 15519 20495 21783
8倍数加1 32793 33017 59673 62073 81977 87129
10倍数加1 40991 41271 74591 77591 102471 108911
16倍数加1 65585 66033 119345 124145 163953 174257
18倍数加1 73783 74287 134263 139663 184447 196039
24倍数加1 98377 99049 179017 186217 245929 261385
26倍数加1 106575 107303 193935 201735 266423 283167
2倍分解 3*3*911 5*13*127 3*4973 3*7*739 5*4099 3*53*137
8倍分解 3*17*643 137*241 3*19891 3*3*3*11*11*19 7*7*7*239 3*3*3*7*461
10倍分解 179*229 3*13757 11*6781 77591素 3*34157 11*9901
16倍分解 5*13*1009 3*3*11*23*29 5*23869 5*7*3547 3*3*18217 174257素
18倍分解 73783素 74287素 134263素 139663素 184447素 196039素
24倍分解 98377素 37*2677 29*6173 31*6007 83*2963 5*61*857
26倍分解 3*5*5*7*7*29 7*15329 3*5*7*1847 3*3*5*4483 29*9187 3*3*73*431

yangchuanju · 发表于 2024-8-20 04:51

请注意，如果梅森数是一个二合数，它的第1素因子一定是小于梅森数平方根的，第2素因子一定是大于梅森数平方根的；
如果梅森数是一个三合数，它的第1素因子一定是小于梅森数平方根的，第3素因子是不是大于梅森数平方根的不能确定；
如M29、M53的第1,2,3素因子都是小于相应梅森数平方根的，但M43、M47的第3素因子都是大于相应梅森数平方根的；
四合数以上的多合数的最大素因子的大小更是不宜预测，但p2*p3*p4*……或p3*p4*……等复合因子肯定是大于多合梅森数平方根的。

yangchuanju · 发表于 2024-8-20 06:00

假定我们至今仍不知道M67是不是梅森素数，有没有素因子也不知道；
但67模4余3是易知的，它如果有素因子应该是2p+1,8p+1,10p+1,16p+1,18p+1,……8kp+1,(8k+2)p+1型的。
采用试除法逐个试除呗！

首先计算出2k*67+1，2k=2,8,10.16,18,24,26……；
计算M67的平方根约等于12148002000<11>，除以67等于18131362.7；最大2k等于181313448,181313450,181313456,181313458；（181313462不合规则舍弃）
接着分解2k*67+1，找出其中的素数1609,3217,4289,4423,5897,7103,7639,9649,11257,11927,12329，……193707721，……12147995791,12147996863；
用这些素数从小到大逐个试除，素数1609,3217……都不能整除，直到用素数193707721试除时整除才发生，M67的9位最小素因子193707721被找到；共试除多少次不再计算；
用193707721除2^67-1得761838257287<12>，M67方被完全分解；其中第一素因子减1除以67等于2891160。

2k 2k*67+1 分解式
2 135 135=3*3*3*5
8 537 537=3*179
10 671 671=11*61
16 1073 1073=29*37
18 1207 1207=17*71
24 1609 1609 is prime
48 3217 3217 is prime
64 4289 4289 is prime
66 4423 4423 is prime
88 5897 5897 is prime
106 7103 7103 is prime
114 7639 7639 is prime
144 9649 9649 is prime
168 11257 11257 is prime
178 11927 11927 is prime
184 12329 12329 is prime
2891158 193707587 193707587=23*2203*3823
2891160 193707721 193707721 is prime
2891166 193708123 193708123=7*7*61*229*283
2891168 193708257 193708257=3*64569419
181313368 12147995657 12147995657=7*41*42327511
181313370 12147995791 12147995791 is prime
181313376 12147996193 12147996193=199*61045207
181313378 12147996327 12147996327=3*1033*3919973
181313384 12147996729 12147996729=3*11*359*1025407
181313386 12147996863 12147996863 is prime
181313392 12147997265 12147997265=5*3607*673579
181313394 12147997399 12147997399=59*239*861499
181313400 12147997801 12147997801=18803*646067
181313402 12147997935 12147997935=3*5*313*379*6827
181313408 12147998337 12147998337=3*3*15199*88807
181313410 12147998471 12147998471=7*29*37*151*10711
181313416 12147998873 12147998873=17*157*4551517
181313418 12147999007 12147999007=107*811*139991
181313424 12147999409 12147999409=7*13*5569*23971
181313426 12147999543 12147999543=3*3*3*3*19*31*254627
181313432 12147999945 12147999945=3*5*809866663
181313434 12148000079 12148000079=3271*3713849
181313440 12148000481 12148000481=241*50406641
181313442 12148000615 12148000615=5*14957*162439
181313448 12148001017 12148001017=751*16175767
181313450 12148001151 12148001151=3*11*13*17*41*40627
181313456 12148001553 12148001553=3*10691*378761
181313458 12148001687 12148001687=47*53*4876757

yangchuanju · 发表于 2024-8-20 06:06

本帖最后由 yangchuanju 于 2024-8-20 06:29 编辑

寻找历程
2300多年来，人类仅发现51个梅森素数，由于这种素数珍奇而迷人，因此被人们誉为“数海明珠”。自梅森提出其断言后，人们发现的已知最大素数几乎都是梅森素数，因此寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。
梅森素数的探寻难度极大，它不仅需要高深的理论和纯熟的技巧，而且需要进行艰苦的计算。
手算笔录时代
早在公元前4世纪，古希腊著名数学家欧几里得（前330～前275）就提出了2^p－1型素数的概念，即可以表示为2^p－1形式的素数。
他发现这种类型的素数和完全数之间有着密切联系：如果2^p－1是素数，则2^(p－1)*(2^p－1)是完全数。
【译者注：以下多个2p-1都是2^p-1，乘方符号^未再一一添加】
欧几里得的结论为2p－1型素数研究奠定了基础。不过在计算能力低下的公元前，人们仅知道四个2p－1型素数：、、和，发现人已无从考证。

欧几里得开启了最初的探寻之旅
15世纪，第5个2p－1型素数的发现人同样没有留下姓名。
长期以来人们一直以为所有2p－1型的数可能都是素数，但雷吉乌斯在1536年纠正了这一错误观点。他指出M11=23×89，并不是素数。由此人们开始深入思考哪些2p－1型的数才是素数？这样的素数又有多少？人类寻找2p－1型素数之路开始真正走上正轨。

卡塔尔迪成为历史上最早的发现者
首先对2p－1型的数进行整理的是意大利数学家彼得罗•卡塔尔迪（1548～1626）。1588年，卡塔尔迪先是正确地指出p=17和19，2p－1是素数；但他之后又提出p=23、29、31和37，2p－1也都是素数。在卡塔尔迪所处的年代，判断2p－1型的数是不是素数极其困难。虽然卡塔尔迪的结论经后人验证错了三个，人们还是把和这两个素数归于他的发现。

马林•梅森提出著名“断言”
17世纪，法国数学家马林•梅森（1588～1648）对2p－1型的数进行了更为全面深入地研究。1644年，梅森在其著作中提出了他认为的四个2p－1型素数：M31、M67、M127和M257，这就是著名的“梅森断言”。梅森在提出“断言”四年之后就去世了。后来人们从梅森的断言中找到了不少错漏，并没有把任何一个2p－1型素数的“发现权”归属于他。不过，人们为了纪念梅森在2p－1型素数研究中所做的开创性工作，以后就把这种类型的素数称为“梅森素数”。

费马和欧拉先后证明M23、M29和M37都是合数
手算笔录的时代，每前进一步，都显得格外艰难。1772年，瑞士大数学家莱昂哈德•欧拉（1707～1783）在双目失明的情况下，靠心算证明了的确是素数。这是人们找到的第8个梅森素数，它共有10位数，堪称当时世界上已知的最大素数。欧拉还证明了欧几里得关于完全数定理的逆定理：所有的偶完全数都具有2p－1（2p－1）的形式，其中2p－1是素数。这表明梅森素数和偶完全数是一一对应的。

欧拉在梅森素数方面也有突出贡献
梅森素数的研究在100年后又有了新的进展。19世纪70年代，法国数学家爱德华•卢卡斯（1842～1891）提出了一个用来判别Mp是否为素数的重要定理——卢卡斯定理，为梅森素数的寻找提供了有力的工具。 [2]1876年，卢卡斯证明确实也是素数，这是人们靠手工计算发现的最大梅森素数，长达39位。

卢卡斯推进了梅森素数的研究
至此，梅森的断言已有两个是正确的。然而——
19世纪末至20世纪初，人们利用卢卡斯定理又陆续找到了三个梅森素数。1883年，俄国数学家伊凡•波佛辛（1827～1900）证明也是素数——这是梅森遗漏的。梅森还漏掉另外两个素数和，它们分别在1911年和1914年被美国业余数学家拉尔夫•鲍尔斯（1875～1952）发现。

柯尔找到M67的因子
梅森的断言还有两处错误。1876年，卢卡斯第一个否定了“M67为素数”这一自梅森断言以来一直被人们相信的结论，但他并未找到其因子。直到1903年，才由数学家柯尔（1861～1926）算出M67=193707721×761838257287。1922年，数学家克莱契克（1882～1957）验证了M257并不是素数，而是合数。
在手工计算的漫长年代里，人们历尽艰辛，一共只找到12个梅森素数。

太阳 · 发表于 2024-8-20 09:23

第51梅森素数，2^82589933-1，这个数字非常大，这是使用什么方法判断2^82589933-1是素数？

yangchuanju · 发表于 2024-8-21 06:02

梅森合数分解已经取得一些微不足道的进展：
1,p=4r+3,如果8r+7也是素数,则：(8r+7)|(2^P-1).即（2p+1）|（2^P-1）； .例如：23|(2^11-1);；11=4×2+3,23=2×11+1； 47|(2^23-1);；23=4×5+3,47=2×23+1； 167|(2^83-1)；83=4×20+3；163=2×83+1；
2,p=2^n×3^2+1,则（6p+1）|(2^P-1),例如：223|(2^37-1);；37=2×2×3×3+1；223=6×37+1； 439|(2^73-1)；73=2×2×2×3×3+1；439=6×73+1; 3463|(2^577-1);；577=2×2×2×2×2×2×3×3+1；3463=6×577+1;
3,p=2^n×3^m×5^s-1,则（8p+1）|（2^P-1）； .例如; 233|(2^29-1)；29=2×3×5-1；233=8×29+1; ;1433|(2^179-1)；179=2×2×3×3×5-1；1433=8×179+1; 1913|（2^239-1）；239=2×2×2×2×3×5-1；1913=8×239+1.

顺带一提，梅森合数分解已经取得一些微不足道的进展：
1，p=4r+3，如果8r+7也是素数，则：(8r+7)|(2^P-1)。即（2p+1）|（2^P-1）；.例如：23|(2^11-1);；11=4×2+3；47|(2^23-1);；47=4×11+3；167|(2^83-1);,,,.83=4×20+3；。。。。
2，p=2^n×3^2+1,，则（6p+1）|(2^P-1)，例如：223|(2^37-1);；37=2×2×3×3+1；439|(2^73-1)；73=2×2×2×3×3+1；3463|(2^577-1);；577=2×2×2×2×2×2×3×3+1；，，，。
3，p=2^n×3^m×5^s-1,则（8p+1）|（2^P-1）；.例如;233|(2^29-1)；29=2×3×5-1；;1433|(2^179-1)；179=2×2×3×3×5-1；1913|（2^239-1）；239=2×2×2×2×3×5-1；，，，。
还有一些梅森数分解取得进展，不再一一叙述（王晓明王蕊珂）。

yangchuanju · 发表于 2024-8-22 13:57

yangchuanju 发表于 2024-8-21 06:02
梅森合数分解已经取得一些微不足道的进展：
1,p=4r+3,如果8r+7也是素数,则：(8r+7)|(2^P-1).即（2p+1）|（ ...

梅森数分解已经取得的“一些微不足道的进展”不正确——
王晓明、王蕊珂文《梅森合数分解已经取得一些微不足道的进展》之二
2，p=2^n×3^2+1，则（6p+1）|(2^P-1)，
例如：223|(2^37-1)；37=2×2×3×3+1；
439|(2^73-1)；73=2×2×2×3×3+1；
3463|(2^577-1)；577=2×2×2×2×2×2×3×3+1；
……
有6p+1素因子的梅森数都是指数模4余1的，它们都是相应梅森数的第一素因子；
素因子减1除以梅森指数都等于6。
在梅森指数p不大于4万的梅森数中共有163个第1素因子是6p+1的，
按照二王的研究结论，指数p加1的分解式中都有n个2，2个3；实际并非如此，仅用36个符合这个规律，即p=2^n×3^2+1,则（6p+1）|（2^P-1）；
p (p1-1)/p p1 p-1分解式
37 6 223 36=2*2*3*3
73 6 439 72=2*2*2*3*3
397 6 2383 396=2*2*3*3*11
577 6 3463 576=2*2*2*2*2*2*3*3
1693 6 10159 1692=2*2*3*3*47
2593 6 15559 2592=2*2*2*2*2*3*3*3*3
3457 6 20743 3456=2*2*2*2*2*2*2*3*3*3
4861 6 29167 4860=2*2*3*3*3*3*3*5
4933 6 29599 4932=2*2*3*3*137
6373 6 38239 6372=2*2*3*3*3*59
6841 6 41047 6840=2*2*2*3*3*5*19
8353 6 50119 8352=2*2*2*2*2*3*3*29
9613 6 57679 9612=2*2*3*3*3*89
11701 6 70207 11700=2*2*3*3*5*5*13
12421 6 74527 12420=2*2*3*3*3*5*23
13177 6 79063 13176=2*2*2*3*3*3*61
15661 6 93967 15660=2*2*3*3*3*5*29
15913 6 95479 15912=2*2*2*3*3*13*17
16561 6 99367 16560=2*2*2*2*3*3*5*23
16741 6 100447 16740=2*2*3*3*3*5*31
17317 6 103903 17316=2*2*3*3*13*37
18217 6 109303 18216=2*2*2*3*3*11*23
18757 6 112543 18756=2*2*3*3*521
19081 6 114487 19080=2*2*2*3*3*5*53
20521 6 123127 20520=2*2*2*3*3*3*5*19
21493 6 128959 21492=2*2*3*3*3*199
22717 6 136303 22716=2*2*3*3*631
24337 6 146023 24336=2*2*2*2*3*3*13*13
29881 6 179287 29880=2*2*2*3*3*5*83
30133 6 180799 30132=2*2*3*3*3*3*3*31
30637 6 183823 30636=2*2*3*3*23*37
30781 6 184687 30780=2*2*3*3*3*3*5*19
32653 6 195919 32652=2*2*3*3*907
35677 6 214063 35676=2*2*3*3*991
36433 6 218599 36432=2*2*2*2*3*3*11*23
39241 6 235447 39240=2*2*2*3*3*5*109

其余的指数减1分解式都不满足p=2^n×3^2+1条件——
p (p1-1)/p p1 p-1分解式
233 6 1399 232=2*2*2*29
461 6 2767 460=2*2*5*23
557 6 3343 556=2*2*139
601 6 3607 600=2*2*2*3*5*5
761 6 4567 760=2*2*2*5*19
1013 6 6079 1012=2*2*11*23
1321 6 7927 1320=2*2*2*3*5*11
1361 6 8167 1360=2*2*2*2*5*17
1381 6 8287 1380=2*2*3*5*23
1453 6 8719 1452=2*2*3*11*11
1777 6 10663 1776=2*2*2*2*3*37
1993 6 11959 1992=2*2*2*3*83
2417 6 14503 2416=2*2*2*2*151
2621 6 15727 2620=2*2*5*131
2897 6 17383 2896=2*2*2*2*181
3037 6 18223 3036=2*2*3*11*23
3181 6 19087 3180=2*2*3*5*53
3581 6 21487 3580=2*2*5*179
3593 6 21559 3592=2*2*2*449
4001 6 24007 4000=2*2*2*2*2*5*5*5
4273 6 25639 4272=2*2*2*2*3*89
4441 6 26647 4440=2*2*2*3*5*37
4517 6 27103 4516=2*2*1129
4597 6 27583 4596=2*2*3*383
4801 6 28807 4800=2*2*2*2*2*2*3*5*5
4813 6 28879 4812=2*2*3*401
5197 6 31183 5196=2*2*3*433
5393 6 32359 5392=2*2*2*2*337
5557 6 33343 5556=2*2*3*463
5717 6 34303 5716=2*2*1429
5801 6 34807 5800=2*2*2*5*5*29
6173 6 37039 6172=2*2*1543
6277 6 37663 6276=2*2*3*523
6353 6 38119 6352=2*2*2*2*397
6977 6 41863 6976=2*2*2*2*2*2*109
7573 6 45439 7572=2*2*3*631
7853 6 47119 7852=2*2*13*151
7901 6 47407 7900=2*2*5*5*79
8377 6 50263 8376=2*2*2*3*349
……

		自动登录	找回密码
密码			注册

2^99368963-1是梅森素数吗？

点评