梅森素数Lucas-Lehmer判定法

yangchuanju

LL检验法是令r1=4开始的，如果令r1=3.5.6.7,8,9,10,11等有类似的余数等于0或余数循环出现的情况——
序号        2^3-1=7        模余                                                       
1        3        4        5        6        7        8        9        10        11
2        0        0        2        -1        -2        -1        2        0        0
3        -2        -2        2        -1        2        -1        2        -2        -2
4        2        2        2        -1        2        -1        2        2        2
                                                                       
序号        2^5-1=31        模余                                                       
1        3        4        5        6        7        8        9        10        11
2        7        14        23        3        16        0        17        5        26
3        16        8        0        7        6        -2        8        23        23
4        6        0        -2        16        3        2        0        0        0
5        3        -2        2        6        7        2        -2        -2        -2
6        7        2        2        3        16        2        2        2        2
                                                                       
序号        2^7-1=127        模余                                                       
1        3        4        5        6        7        8        9        10        11
2        7        14        23        34        47        62        79        98        119
3        47        67        19        11        48        32        16        77        62
4        48        42        105        119        16        6        0        85        32
5        16        111        101        62        0        34        -2        111        6
6        0        0        39        32        -2        11        2        0        34
7        -2        -2        122        6        2        119        2        -2        11
8        2        2        23        34        2        62        2        2        119
                                                                       
序号        2^11-1=2047        模余                                                       
1        3        4        5        6        7        8        9        10        11
2        7        14        23        34        47        62        79        98        119
3        47        194        527        1154        160        1795        98        1414        1877
4        160        788        1382        1164        1034        45        1414        1522        240
5        1034        701        71        1827        620        2023        1522        1325        282
6        620        119        945        1317        1609        574        1325        1344        1736
7        1609        1877        531        678        1471        1954        1344        880        510
8        1471        240        1520        1154        160        459        880        632        129
9        160        282        1382        1164        1034        1885        632        257        263
10        1034        1736        71        1827        620        1678        257        543        1616
11        620        510        945        1317        1609        1057        543        79        1529
12        1609        129        531        678        1471        1632        79        98        165
                                                                       
序号        2^13-1=8191        模余                                                       
1        3        4        5        6        7        8        9        10        11
2        7        14        23        34        47        62        79        98        119
3        47        194        527        1154        2207        3842        6239        1411        5968
4        2207        4870        7424        4772        5393        780        1487        506        2554
5        5393        3953        6726        1002        6397        2264        7788        2113        2878
6        6397        5970        181        4700        7562        6319        6778        672        1781
7        7562        1857        8186        7062        2471        6825        6154        1077        2042
8        2471        36        23        5034        3544        6597        4721        4996        543
9        3544        1294        527        6391        3131        1624        128        2037        8162
10        3131        3470        7424        4553        6723        8063        0        4721        839
11        6723        128        6726        6577        789        0        -2        128        7684
12        789        0        181        256        3        -2        2        0        3126
13        3        -2        8186        6        7        2        2        -2        11
14        7        2        23        34        47        2        2        2        119
                                                                       
序号        2^17-1=131071        模余                                                       
1        3        4        5        6        7        8        9        10        11
2        7        14        23        34        47        62        79        98        119
3        47        194        527        1154        2207        3842        6239        9602        14159
4        2207        37634        15585        21004        21220        81010        128103        55489        69720
5        21220        95799        17660        114099        59513        26199        27265        40258        110363
6        59513        119121        57689        85795        127676        99843        76582        13647        88021
7        127676        66179        128029        96805        122846        19742        30827        119787        89629
8        122846        53645        78792        24736        17987        72479        39177        58713        16049
9        17987        122218        1347        30266        48939        10830        126988        49067        15884
10        48939        126220        110484        106606        96407        111424        24870        58359        120850
11        96407        70490        72024        66037        65037        512        123920        24015        5252
12        65037        69559        59607        22126        19126        0        19109        7823        58592
13        19126        99585        52850        9689        115784        -2        121144        120241        10830
14        115784        78221        130559        29883        123845        2        111006        111424        111424
15        123845        130559        0        6964        48816        2        85182        512        512
16        48816        0        -2        1024        3        2        13633        0        0
17        3        -2        2        6        7        2        9        -2        -2
18        7        2        2        34        47        2        79        2        2
                                                                       
序号        2^19-1=524287        模余                                                       
1        3        4        5        6        7        8        9        10        11
2        7        14        23        34        47        62        79        98        119
3        47        194        527        1154        2207        3842        6239        9602        14159
4        2207        37634        277727        283140        152264        80926        127881        448177        199645
5        152264        218767        231661        58715        354554        148557        514342        409322        255422
6        354554        510066        277312        264198        244924        369556        337067        200240        220950
7        244924        386344        52469        157744        420095        116504        121013        160699        442780
8        420095        323156        489209        508514        86240        440158        285970        412414        150470
9        86240        218526        488780        275489        326503        338426        30351        313150        411090
10        326503        504140        361099        500147        409010        89463        10940        282018        510814
11        409010        103469        213751        256741        208425        387312        146162        338709        118425
12        208425        417706        499384        482291        132664        16041        207853        353913        327660
13        132664        307417        452173        486833        470878        413049        47946        150119        205173
14        470878        382989        26241        334389        399999        195155        344706        286038        432410
15        399999        275842        201248        266255        439061        217769        442189        129657        362427
16        439061        85226        111039        258318        523263        5348        372217        199279        38208
17        523263        523263        2140        85484        0        289604        33902        1024        236254
18        0        0        385302        2048        -2        285424        108498        0        358494
19        -2        -2        524282        6        2        524279        524278        -2        11
20        2        2        23        34        2        62        79        2        119

yangchuanju

现对上贴各表中的余数0和余数循环情况逐一分析如下——
如果检验余数有0出现，则下一余数是-2，再向下的余数都是2，用正整数倒数情况类比，可视为它们是“有限小数”；
否则，如果检验余数循环出现，用正整数倒数情况类比，可视为它们是“循环小数”。

对于梅森素数2^3-1=7，当r1=4及3,10,11时r2便是0，数据太少，无规律可探讨；
对于梅森素数2^5-1=31，当r1=4及9,10,11时r4都是0；当r1=3,6,7时余数循环出现，循环节长都是4；
对于梅森素数2^7-1=127，当r1=4及3,10时r6都是0；当r1=7,9时也有余数0出现，但不是r6（都是提前出现的）；当r1=5,6,8,11时余数循环出现，循环节长都是6；
对于梅森素数2^13-1=8191，当r1=4及10时r12都是0；当r1=8,9时也有余数0出现，但不是r12（都是提前出现的）；当r1=3,6,7,11时余数循环出现，循环节长都是12；当r1=5时余数也是循环出现的，循环节长是6；
对于梅森素数2^17-1=131071，当r1=4及10,11时r16都是0；当r1=5,8时也有余数0出现，但不是r16（都是提前出现的）；当r1=3,6,7,9时余数循环出现，循环节长都是16；
对于梅森素数2^19-1=524287，当r1=4及3,10时r18都是0；当r1=7时也有余数0出现，但不是r18（是提前出现的）；当r1=5,6,8,9,11时余数循环出现，循环节长都是18；
……
请注意，循环节长大部分是指数减1，也有循环节长是指数减1的某个分数的；有的循环节从r1开始，有的循环节要从r2开始；
对于上述各个梅森素数，r1=10时的表现都是r1=4相同，即都有余数0出现，且r的下标比指数少1。

对于梅森合数2^11-1=2047=23*89，当r1=4是没有余数0出现，余数是循环出现的，循环节长等于60，60是指数11减1的6倍；
对于其它的r1数值，余数也都是循环出现的，循环节长最大是60，较少的有12,10,5等，都是60的某个分数；各种循环节有的从r2开始，有的从其它余数开始：
r1        循环节长        开始r
3        5        4
4        60        2
5        5        4
6        5        3
7        5        3
8        12        4
9        10        2
10        10        2
11        60        2
……

yangchuanju

不定方程x^2-2=(2^n-1)*y的整数解，n大于等于3的奇数——       
n        不定方程及整数解
3        x^2-2=7y；x=3，y=1；x=4，y=2；x=10，y=14；x=11，y=17；x=17，y=41；x=18，y=45；
5        x^2-2=31y；x=8，y=2；x=23，y=17；
7        x^2-2=127y；x=16，y=2；x=111，y=97；
9        x^2-2=511y；x=32，y=2；
11        x^2-2=2047y；x=64，y=2；
13        x^2-2=8191y；x=128，y=2；x=8063，y=7937；
15        x^2-2=32767y；x=256，y=2；
17        x^2-2=131071y；x=512，y=2；x=130559，y=130049；
19        x^2-2=524287y；x=1024，y=2；x=523263，y=522241；
21        x^2-2=2097151y；x=2048，y=2；
23        x^2-2=8388607y；x=4096，y=2；
25        x^2-2=33554431y；x=8192，y=2；
27        x^2-2=134217727y；x=16384，y=2；
29        x^2-2=536870911y；x=32768，y=2；
31        x^2-2=2147483647y；x=65536，y=2；
……        …………
此类不定方程的整数解可用于判断梅森数在用LL检验时是否有余数0出现的情况；       
如对于n=11,23，虽然当x=64,4096时有整数解，但在2^11-1、2^23-1等梅森合数中的各个LL检验余数中是没有64和4096的！       

太阳

判断2^127-1是素数，最少要试除多少次？确定它是素数

yangchuanju

yangchuanju 发表于 2024-8-26 05:17
LL检验法是令r1=4开始的，如果令r1=3.5.6.7,8,9,10,11等有类似的余数等于0或余数循环出现的情况——
序号         ...

（接前楼）
对于2^23-1的LL检验余数，虽然没有0出现，但它的一系列余数是循环重复出现的，循环节长为32340；
由于2^23-1不是素数，它的余数循环节长32340不是2^23-1的分数，也不是两素因子减1的乘积的分数；它是指数23减1的1470倍。
将r1=4，换成5,10,14,19,21,23,24,26,28,31时循环节长也是32340，循环是从r2或r1开始的；
将r1=4，换成8,9,20,22,25,27,29,32时循环节长都是3234，循环是从r4或r5开始的；
将r1=4，换成3,6,7,11,12,13,15,16,17,18,30时循环节长都是528，循环是从r1、r2、r4或r5开始的；需要注意的是，528=22*24不是32340的分数(32340/528=61.25)。
r1        循环节长        循环开始
4        32340        r2
5        32340        r1
10        32340        r2
14        32340        r1
19        32340        r2
21        32340        r2
23        32340        r1
24        32340        r2
26        32340        r1
28        32340        r2
31        32340        r2
8        3234        r5
9        3234        r5
20        3234        r5
22        3234        r4
25        3234        r4
27        3234        r5
29        3234        r5
32        3234        r4
3        528        r5
6        528        r2
7        528        r4
11        528        r5
12        528        r4
13        528        r5
15        528        r4
16        528        r3
17        528        r5
18        528        r5
30        528        r1

yangchuanju

对于2^29-1，若将r1=4换成r1=3,5,6,7,8,9,10,11,12,13,14的循环节长分别为：                       
r1        循环节长        循环开始        循环节/28
3        84        r5        3
4        252        r2        9
5        660        r5        23.57142857
6        252        r3        9
7        84        r4        3
8        924        r5        33
9        252        r4        9
10        252        r2        9
11        924        r5        33
12        924        r2        33
13        924        r2        33
14        252        r1        9

太阳

已知:\(a^2bc+mt=b^2\)，\(b=m\)，\(b+c=1\)，整数\(a＞1\)，\(b＞1\)，\(c\ne0\)
奇数\(m＞1\)，\(t＞1\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc-mt=b^2\)，\(|b|=m\)，\(b-c=1\)，整数\(a＞1\)，\(b≠1\)，\(c\ne0\)
奇数\(m＞1\)，\(t＞1\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(2a＞m\)，\(4＞t\)，\(\frac{a}{2^kt^n}=3\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(a＞m\)，\(4＞t\)，\(\frac{a}{2^kt^n}=3\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(2a＞m\)，\(6＞t\)，\(\frac{a}{2^kt^n}=3\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(a＞m\)，\(6＞t\)，\(\frac{a}{2^kt^n}=3\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(2a＞m\)，\(4＞t\)，\(\frac{a}{2^kt^n}=5\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(a＞m\)，\(4＞t\)，\(\frac{a}{2^kt^n}=5\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(2a＞m\)，\(6＞t\)，\(\frac{a}{2^kt^n}=5\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4=b^2\)，\(a＞m\)，\(6＞t\)，\(\frac{a}{2^kt^n}=5\)
整数\(a＞0\)，\(b\ne0\)，\(c\ne0\)，\(k＞0\)，\(n＞0\)，\(t＞0\)，奇数\(m＞0\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4t^4=b^2\)，\(b=m^2\)，\(b+c=1\)，
整数\(a＞1\)，\(b＞1\)，\(c\ne0\)，\(m＞1\)，\(t＞1\)，素数\(p＞0\)
求证:\(m=p\)
已知:\(a^2bc+m^4t^4=b^2\)，\(|b|=m^2\)，\(b+c=-1\)，
整数\(a＞1\)，\(b\ne1\)，\(c\ne0\)，\(m＞1\)，\(t＞1\)，素数\(p＞0\)
求证:\(m=p\)
这可能是素数公式，不知能不能找到反例？

太阳

已知:\(4a+1=c^4\)，\(9a+1=c^4\)，\(16a+1=c^4\)，\(36a+1=c^4\)
\(64a+1=c^4\)，\(81a+1=c^4\)，\(144a+1=c^4\)，\(324a+1=c^4\)
\(576a+1=c^4\)，\(1296a+1=c^4\)，\(5184a+1=c^4\)，\(m^2t+1\ne c^4\)
\(73＞m＞1\)，\(m\ne2\)，\(m\ne3\)，\(m\ne4\)，\(m\ne6\)，\(m\ne8\)，\(m\ne9\)
\(m\ne12\)，\(m\ne18\)，\(m\ne24\)，\(m\ne36\)，\(m\ne72\)
整数\(a＞0\)，\(m＞1\)，\(t＞0\)，奇数\(c＞0\)，素数\(p＞0\)
求证:\(c=p\)

yangchuanju

太阳 发表于 2024-8-29 05:57
已知:\(4a+1=c^4\)，\(9a+1=c^4\)，\(16a+1=c^4\)，\(36a+1=c^4\)
\(64a+1=c^4\)，\(81a+1=c^4\)，\(144a+ ...

梅森素数特别判定法
已知：整数r，整数c>0，素数p≥3，1≤r≤2^p-1，
求证：如果(r^4-4*r^2+2)/(2^p-1)=c，则2^p-1是素数；否则如果(r^4-4*r^2+2)/(2^p-1)≠c，则2^p-1是合数。
亦或如果不定方程(r^4-4*r^2+2)/(2^p-1)=c有正整数解，则2^p-1是素数；否则如果不定方程(r^4-4*r^2+2)/(2^p-1)=c无正整数解，则2^p-1是合数。

太阳先生，您梦寐以求的梅森素数公式被我抢先找到了！
别再像一只无头的苍蝇到处乱碰、乱蒙啦！