梅森数的因子形式及寻找方法

yangchuanju · 发表于 2022-2-11 09:29

梅森数的因子形式及寻找方法

梅森数和梅森素数是8N-1和6N+1形式的整数，
模24余7的整数满足同时模8余7和模6余1，可能是梅森素数。
实际上，只要指数n是奇数，2^n-1就满足上述条件，只能说梅森数和梅森素数是8N-1和6N+1形式的整数，
不能说8N-1和6N+1形式的整数是梅森数或梅森素数。

梅森数都是模8余7的，但它的素因子即有模8余7的，也有模8余1的，没有模8余3和余5的；
梅森数都是模6余1的，但梅森数的素因子即有模6余1的，也有模6余5的，没有模6余3的（它不是素数）。
梅森数的因子（素因子和合数因子）都是2mp+1形式的整数，进一步是8kp+1、(8k+2)p+1、(8k+6)p+1形式的整数，但没有(8k+4)p+1形式的整数。
当指数是模4余3的素数时，为8kp+1和(8k+2)p+1的形式；当指数是模4余1的素数时，为8kp+1和(8k+6)p+1的形式。

2^p+1模8余1，它的素因子模8余1或3，模6余1或5。
2^p+1都是3的倍数，(2^p+1)/3的素因子模8余1或3，模6余1或5。
2^p+1的因子（素因子和合数因子）也都是2mp+1形式的整数，进一步是8kp+1、(8k+2)p+1、(8k+6)p+1形式的整数，也没有(8k+4)p+1中的整数。

yangchuanju · 发表于 2022-2-11 09:30

n 2^n-1 模8余数模6余数模24余数
2 3 3 3 3
3 7 7 1 7
4 15 7 3 15
5 31 7 1 7
6 63 7 3 15
7 127 7 1 7
8 255 7 3 15
9 511 7 1 7
10 1023 7 3 15
11 2047 7 1 7
12 4095 7 3 15
13 8191 7 1 7
14 16383 7 3 15
15 32767 7 1 7
16 65535 7 3 15
17 131071 7 1 7
18 262143 7 3 15
19 524287 7 1 7
20 1048575 7 3 15
21 2097151 7 1 7
22 4194303 7 3 15
23 8388607 7 1 7
24 16777215 7 3 15
25 33554431 7 1 7
26 67108863 7 3 15
27 134217727 7 1 7
28 268435455 7 3 15
29 536870911 7 1 7

n 2^n-1及因子模8余数模6余数模24余数
2 3 3 3 3
3 7 7 1 7
5 31 7 1 7
7 127 7 1 7
11 2047 7 1 7
11 23 7 5 23
11 89 1 5 17
23 8388607 7 1 7
23 47 7 5 23
23 178481 1 5 17
29 536870911 7 1 7
29 233 1 5 17
29 1103 7 5 23
29 2089 1 1 1

模8余3的素数：
3 11 19 43 59 67
模8余5的素数：
5 13 29 37 53 61
它们都是偶指数的φ因子，除2以外都不是素数，
因而它们都不是奇指数梅森数的素因子。

yangchuanju · 发表于 2022-2-11 09:31

指数p p模4余数 q模8余数 q模6余数 q模24余数素因子q
11 3 7 5 23 23
11 3 1 5 17 89
23 3 7 5 23 47
23 3 1 5 17 178481
29 1 1 5 17 233
29 1 7 5 23 1103
29 1 1 1 1 2089
37 1 7 1 7 223
37 1 1 1 1 616318177
41 1 7 5 23 13367
41 1 1 5 17 164511353
43 3 7 5 23 431
43 3 7 5 23 9719
43 3 7 1 7 2099863
47 3 7 5 23 2351
47 3 1 1 1 4513
47 3 1 5 17 13264529
53 1 1 1 1 6361
53 1 7 5 23 69431
53 1 1 5 17 20394401
59 3 7 5 23 179951
59 3 1 5 17 3203431780337
67 3 1 1 1 193707721
67 3 7 1 7 761838257287
71 3 7 5 23 228479
71 3 1 5 17 48544121
71 3 1 1 1 212885833
73 1 7 1 7 439
73 1 1 5 17 2298041
73 1 1 5 17 9361973132609
79 3 7 5 23 2687
79 3 7 1 7 202029703
79 3 7 5 23 1113491139767
83 3 7 5 23 167
97 1 7 5 23 11447
101 1 7 1 7 7432339208719
103 3 7 1 7 2550183799
109 1 7 5 23 745988807
113 1 7 1 7 3391
113 1 7 5 23 23279
113 1 1 5 17 65993
113 1 1 1 1 1868569
131 3 7 5 23 263
139 3 7 1 7 5625767248687
151 3 1 1 1 18121
151 3 7 5 23 55871
151 3 7 1 7 165799
151 3 7 1 7 2332951
157 1 1 1 1 852133201
157 1 7 5 23 60726444167
157 1 1 5 17 1654058017289
163 3 7 5 23 150287
163 3 1 1 1 704161
163 3 1 5 17 110211473
163 3 1 1 1 27669118297
167 3 7 5 23 2349023
173 1 1 1 1 730753
173 1 7 5 23 1505447
179 3 7 5 23 359
179 3 1 5 17 1433
181 1 1 1 1 43441
181 1 1 1 1 1164193
181 1 1 5 17 7648337
191 3 7 5 23 383
191 3 1 1 1 7068569257
191 3 1 5 17 39940132241
191 3 1 1 1 332584516519201
193 1 7 5 23 13821503
197 1 7 5 23 7487
199 3 1 5 17 164504919713
211 3 1 1 1 15193
223 3 7 5 23 18287
223 3 7 1 7 196687
223 3 1 1 1 1466449
223 3 1 1 1 2916841
229 1 1 5 17 1504073
229 1 1 5 17 20492753
233 1 7 1 7 1399
233 1 7 1 7 135607
233 1 1 5 17 622577
239 3 7 5 23 479
239 3 1 5 17 1913
239 3 1 1 1 5737
239 3 7 1 7 176383
239 3 1 5 17 134000609
241 1 1 5 17 22000409
251 3 7 5 23 503
251 3 1 1 1 54217
257 1 7 1 7 535006138814359
263 3 7 1 7 23671
263 3 1 1 1 13572264529177
269 1 1 1 1 13822297
271 3 1 1 1 15242475217
277 1 1 5 17 1121297
281 1 1 1 1 80929
283 3 7 5 23 9623
283 3 1 5 17 68492481833
307 3 7 1 7 14608903
307 3 7 1 7 85798519
307 3 7 1 7 23487583303
307 3 1 5 17 78952752017
311 3 7 5 23 5344847
313 1 1 1 1 10960009
317 1 7 1 7 9511
331 3 7 5 23 16937389168607
331 3 -1 1 7 865118802936559
337 1 7 1 7 18199
337 1 1 1 1 2806537
337 1 1 5 17 95763203297
337 1 1 5 17 726584894969
349 1 7 1 7 1779973928671
353 1 1 1 1 931921
359 3 7 5 23 719
359 3 1 5 17 855857
359 3 1 5 17 778165529
367 3 7 5 23 12479
367 3 1 1 1 51791041
367 3 1 1 1 78138581882953
373 1 7 1 7 25569151
379 3 7 1 7 180818808679
383 3 7 1 7 1440847
383 3 1 5 17 7435494593
389 1 7 5 23 56478911
389 1 7 5 23 4765678679
397 1 7 1 7 2383
397 1 1 5 17 6353
397 1 7 1 7 50023
397 1 1 5 17 53993
397 1 7 1 7 202471
397 1 7 5 23 5877983
401 1 7 1 7 856971565399
409 1 7 1 7 4480666067023
409 1 1 5 17 76025626689833
419 3 7 5 23 839
419 3 1 1 1 903780021613921
421 1 7 -1 -1 614002928307599
431 3 7 5 23 863
431 3 1 5 17 3449
431 3 1 5 17 36238481
431 3 1 5 17 76859369
431 3 1 5 17 558062249
431 3 1 5 17 4642152737
439 3 7 5 23 104110607
439 3 7 5 23 127321491658223
443 3 7 5 23 887
443 3 1 1 1 207818990653657
449 1 7 5 23 1256303
449 1 1 1 1 6871197486841
457 1 1 1 1 150327409
461 1 7 1 7 2767
463 3 1 1 1 11113
463 3 1 5 17 3407681
463 3 1 1 1 448747600991881
467 3 1 1 1 121606801
479 3 7 5 23 33385343
479 3 1 5 17 6293443049
487 3 7 5 23 4871
491 3 7 5 23 983
491 3 7 5 23 7707719
491 3 1 1 1 110097436327057
499 3 7 1 7 20959
509 1 1 1 1 12619129
541 1 7 5 23 4312790327
541 1 1 1 1 6115209994009
547 3 7 5 23 5471
557 1 7 1 7 3343
557 1 7 1 7 21993703
569 1 1 1 1 15854617
569 1 1 1 1 55470673
571 3 7 5 23 5711
571 3 1 1 1 27409
577 1 7 1 7 3463
577 1 7 1 7 132305774316967
587 3 1 5 17 554129
587 3 7 1 7 2926783
587 3 1 5 17 39483330766889
593 1 1 5 17 104369
601 1 7 1 7 3607
601 1 7 5 23 64863527
617 1 1 1 1 59233
617 1 1 5 17 68954123297
619 3 7 5 23 110183
619 3 7 5 23 710820995447
641 1 1 5 17 35897
641 1 7 1 7 49999
641 1 1 5 17 1173835097
643 3 1 5 17 3189281
653 1 7 5 23 78557207
653 1 1 1 1 289837969
659 3 7 5 23 1319
661 1 1 5 17 1330270433
673 1 7 5 23 581163767
677 1 7 1 7 1943118631
683 3 7 5 23 1367
691 3 1 1 1 906642603313
701 1 1 5 17 796337
701 1 1 5 17 2983457
701 1 7 5 23 28812503
701 1 7 5 23 1073825104511
701 1 1 1 1 9983923992673
701 1 7 1 7 15865578195367
701 1 1 1 1 40686928318417
709 1 1 1 1 216868921
719 3 7 5 23 1439
719 3 7 1 7 772207
733 1 7 5 23 694653525743
743 3 7 5 23 1487
743 3 1 1 1 1219280833
743 3 1 5 17 14904366017
757 1 7 1 7 9815263
757 1 7 1 7 561595591
761 1 7 1 7 4567
761 1 1 5 17 6089
769 1 1 5 17 1591805393
773 1 1 1 1 6864241
773 1 1 1 1 9461521
797 1 1 5 17 2006858753
797 1 1 1 1 54573369937
811 3 7 1 7 326023
821 1 7 5 23 419273207
821 1 1 5 17 109840721427977
827 3 1 5 17 66161
827 3 1 1 1 1637241673
829 1 1 5 17 72953
839 3 1 5 17 26849
839 3 7 5 23 138561000316919
853 1 7 1 7 2065711807
853 1 1 1 1 513740645819473
857 1 1 5 17 6857
859 3 1 1 1 7215601
863 3 7 1 7 8258911
863 3 1 1 1 169382737
863 3 7 1 7 175642891399
877 1 1 5 17 35081
877 1 7 1 7 1436527
881 1 7 1 7 26431
883 3 7 5 23 8831
883 3 1 1 1 63577
887 3 7 1 7 16173559
907 3 7 1 7 1170031
907 3 1 1 1 3256645177
911 3 7 5 23 1823
911 3 7 5 23 26129303
929 1 7 5 23 13007
929 1 1 1 1 340388595097
937 1 7 1 7 28111
937 1 7 5 23 2419437071
941 1 1 5 17 7529
947 3 1 5 17 295130657
947 3 7 1 7 25749931927
953 1 1 1 1 343081
953 1 1 1 1 562070136841
967 3 1 1 1 23209
967 3 1 5 17 549257
977 1 1 1 1 867577
977 1 1 5 17 1813313
991 3 1 5 17 8218291649
991 3 1 1 1 41473350001
991 3 7 5 23 231620367206687

yangchuanju · 发表于 2022-2-11 09:32

本帖最后由 yangchuanju 于 2022-2-11 09:35 编辑

并非每个p*8k+1和p*(8k+6)+1或p*(8k+2)+1中的素数都是Mp的素因子，只有个别素数才是Mp的素因子，并且要逐个检验到Mp的平方根才行。
至今没有找到任何素因子的梅森数是M1277，它是一个385位大合数，指数1277模4余1，它的素因子是1277*8k+1或1277*(8k+6)+1中的素数，若逐个检验，k需检验到191位。
几年前尚未完全分解的梅森数M1009，还有一个204位的复合因子，指数1009模4余1，它的素因子是1009*8k+1或1009*(8k+6)+1中的素数，若逐个检验，k还需检验到100位。
几年前尚未完全分解的梅森数M947、M991，分别有一个217、264位的复合因子，指数947、991模4余3，它的素因子是1009*8k+1或1009*(8k+2)+1中的素数，若逐个检验，k需检验到107和130位。
现今这3个梅森数都已完全分解。

2^1009-1<304>=3454817×198582684439<12>×20649907789079<14>×21624641697047<14>×30850253615723594284324529<26>×1134327302421596486779379019599<31>×3280162939...47<89>×1560053963...37<116>
89位素因子：32801629399316220386255938566077541078836238345868341181567256008155638984594836583203447
116位素因子：15600539638391814556172775617971983694064724957715783341113053160801081635609556652398088573742248793995924472587137

2^947-1<286>=295130657×25749931927<11>×4621646208862937<16>×11892980076500863942962129100776937<35>×4247385134...73<104>×6705118430...89<113>
104位素因子：42473851340526147266826509993319628093194922290192667926440870920964574700349265985080009020182263507473
113位素因子：67051184308582949424821574393399302494429796682222222649491297904528668494149744674438169229263695832033422757289

2^991-1<299>=8218291649<10>×41473350001<11>×231620367206687<15>×6721885469...59<127>×3943730076...91<137>
127位素因子：6721885469050382920298612421830968178768028093133627640714502537112053019071272802490029644416444090606146146238871876925423959
137位素因子：39437300765327204031983243120992095727633141975484859958380479021870710828340701521806772849536517037509868664540317823526815309243487991

yangchuanju · 发表于 2022-2-11 09:37

按上述法寻找梅森因子，比从2p+1系列中寻找素因子减少了许多。
不论梅森数的指数模4余几，梅森数都是模4余3的。
梅森因子p*8k+1模4余1，p*(8k+6)+1和p*(8k+2)+1模4余3，
模4余1的因子乘以模4余1的另一因子的积模4余1，模4余1的因子乘以模4余3的另一因子的积模4余3，模4余3的因子乘以模4余3的另一因子的积模4余1，
梅森合数所有素因子中模4余3的素因子个数是奇数：1、3、5……，模4余1的素因子个数可奇可偶。

梅森合数的素因子以2为底的阶是素数，等于梅森数的指数，若找到阶等于指素数p的某个素数q，则q便是梅森数2^p-1的一个素因子。
计算素数的阶，并不简单，可能还不如直接作除法。
如果寻找素数也嫌太麻烦，也可能直接作除法。

寻找梅森数2^p-1因子的方法：
（1）首先计算p模4的余数是1还是3；
（2）若p模4余3，再查看2p+1是素数否，若2p+1是素数，则2p+1可整除该梅森数；
（3）若2p+1不是素数，再查看8p+1、10p+1是素数否，若是则用它们试除之；
（4）若p模4余1，再查看6p+1、8p+1是素数否，若是则用它们试除之；
（5）继续寻找2mp+1型数字中的素数并试除之；
（6）在找到了梅森数的一个素因子后，即将该因子除去；
（7）对消除了梅森数的一个素因子后的数，可再用下一个2mp+1型素数试除之；
（8）一直试除到2mp+1小于消除了梅森数2^p-1的若干个素因子后的数<（2^p-1)/[(2*m1*p+1)*(2*m2*p+1)*…*(2*mi*p+1)]>的平方根为止；
（9）剩余的数便是梅森数的一个重大的素因子。
（10）试除过程中，由于4p+1、12p+1、20p+1、……、（4+8k）p+1型素数不会是2^p-1的因子，在试除时可略去；这里2m=4+8k。
（11）对于模4余1的素数p，由于2p+1、10p+1、……、（2+8k）p+1型素数不会是2^p-1的因子，在试除时亦可略去；这里2m=2+8k。
（12）对于模4余3的素数p，由于6p+1、14p+1、……、（6+8k）p+1型素数不会是2^p-1的因子，在试除时同样可略去；这里2m=6+8k。
合到一起，对于模4余1的素数p，在试除时可略去（2+8k）p+1和（4+8k）p+1型素数；对于模4余3型素数p，在试除时可略去（4+8k）p+1、（6+8k）p+1型素数。

独舟星海 · 发表于 2022-2-11 17:04

根据进位制原则，则任意一个整数皆可表示成2的唯一指数序列：例如素数3（0,1）；素数5（0,2），素数7（0,1,2）；素数11（0,1,3）；而数的乘法，可以表示成指数加法，7*11=（0,1,2）*（0,1,3）=（0+0,1+0,2+0,0+1,1+1,2+1,0+3,1+3,2+3）=（0,1,2,1,2,3,3,4,5）=（0,2,3,4,4,5）=（0,2,3,5,5）=（0,2,3，6），后边的计算是有两个一样进行合并，把指数升高1，一直合并下去，不留重复数字。从这方面能不能获得灵感？2的次幂和相乘。

yangchuanju · 发表于 2022-2-11 18:37

独舟星海发表于 2022-2-11 17:04
根据进位制原则，则任意一个整数皆可表示成2的唯一指数序列：例如素数3（0,1）；素数5（0,2），素数7（0,1, ...

分解梅森数基本上还是试除法，一系列大整数相除就够复杂的啦，没有必要再转换成2进制数字相乘除。

yangchuanju · 发表于 2024-8-6 07:03

兹将本人有关梅森数的一些帖子顶起来，放到一起，供参阅！

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