(New ?) Wagstaff/Mersenne related property

T.Rex · 2019-11-22, 15:32

Hi,

I have no idea if this property is new. If new, I even am not sure it may be useful.
Anyway.

Let $q$ prime $>3$
$q=2p+1$ and thus $p=\frac{q-1}{2}$ .

Let:
$N_p=2^p+1$ .
$M_p=2^p-1$ Mersenne.
$N_p M_p = 2^{2p}-1=2^{q-1}-1$

Let:
$W_q=\frac{2^q+1}{3}$ Wagstaff.

Then:
$2N_pM_p+3 = 2^q-2+3 = 2^q+1 = 3W_q$

Thus the property : $W_q = \frac{2}{3}N_pM_p+1$ . CQFD.

$\alpha \mid W_q \Rightarrow \alpha = 1+2q\alpha'$
thus : $W_q = 1+2q\beta$ and $2q\beta = W_q-1 = \frac{2}{3}N_pM_p$
thus : $q \, \mid \, \frac{N_pM_p}{3}$ and thus either $q \mid N_p$ or $q \mid M_p$ .

Examples :
$q=11 , \, p=5 , \, q \mid N_p$
$q=17 , \, p=8 , \, q \mid M_p$
$q=47 , \, p=23 , \, q \mid M_p$
$q=59 , \, p=29 , \, q \mid N_p$
$q=257 , \, p=2^7 , \, q \mid M_p$
$q=65537 , \, p=2^{15} , \, q \mid ?_p$

Probably one should only consider cases where p is a prime or a power of 2.

If $p = 2^n$ , then 3 divides $M_p$ since only numbers $k.2^{n+1}+1$ can divide a Fermat number. Can $k$ be $1$ ?

If p is a prime, thus 3 cannot divide $M_p$ since only numbers $1+\alpha p$ can divide a Mersenne number, and thus 3 divides $N_p$ .
So, when p is a prime, when does it divide $N_p$ and not $M_p$ and vice-versa ??

GP2 · 2019-11-23, 00:51

Renaud and Henri Lifchitz mentioned this relation in a 2000 paper, see section 4. Note: they use N_p to denote what we call W_p.

As they point out, this relation means that if W_2n+1 is PRP, then if either W_n or M_n are fully factored, then W_2n+1 can be proven prime by the N−1 method. (Note n does not need to be prime, only 2n+1).

For instance, if we could fully factor M₄₇₆₈₄ or W₄₇₆₈₄ then we could prove that W₉₅₃₆₉ is not just PRP but prime. Spoiler alert: they are nowhere near fully-factored.

Or we could look at all Mersenne primes M_p for which 2p+1 is also prime (OEIS A065406) and check to see if any unfactored W_2p+1 test PRP. Spoiler alert: they don't. M_43,112,609 is a Mersenne prime but W_86,225,219 is composite.

In short, this relation doesn't have much practical use.

sweety439 · 2019-11-23, 21:45

p divides M_n if and only if ord_p(2) divides n, and p divides W_n (for odd n) if and only if ord_p(2) is even and divides 2n

This is the list for ord_p(2) for small odd primes:

Code:

This is the factorization of Phi_n(2), where Phi is the cyclotomic polynomial:

Code:

1      
2      3
3      7
4L      
4M      5
5      31
6      3*
7      127
8      17
9      73
10      11
11      23.89
12L      
12M      13
13      8191
14      43
15      151
16      257
17      131071
18      3*.19
19      524287
20L      5*
20M      41
21      7*.337
22      683
23      47.178481
24      241
25      601.1801
26      2731
27      262657
28L      113
28M      29
29      233.1103.2089
30      331
31      2147483647
32      65537
33      599479
34      43691
35      71.122921
36L      37
36M      109
37      223.616318177
38      174763
39      79.121369
40      61681
41      13367.164511353
42      5419
43      431.9719.2099863
44L      397
44M      2113
45      631.23311
46      2796203
47      2351.4513.13264529
48      97.673
49      4432676798593
50      251.4051
51      103.2143.11119
52L      1613
52M      53.157
53      6361.69431.20394401
54      3*.87211
55      881.3191.201961
56      15790321
57      32377.1212847
58      59.3033169
59      179951.3203431780337
60L      61
60M      1321
61      2305843009213693951
62      715827883
63      92737.649657
64      641.6700417
65      145295143558111
66      67.20857
67      193707721.761838257287
68L      137.953
68M      26317
69      10052678938039
70      281.86171
71      228479.48544121.212885833
72      433.38737
73      439.2298041.9361973132609
74      1777.25781083
75      100801.10567201
76L      229.457
76M      525313
77      581283643249112959
78      22366891
79      2687.202029703.1113491139767
80      4278255361
81      2593.71119.97685839
82      83.8831418697
83      167.57912614113275649087721
84L      14449
84M      1429
85      9520972806333758431
86      2932031007403
87      4177.9857737155463
88      353.2931542417
89      618970019642690137449562111
90      18837001
91      911.112901153.23140471537
92L      277.30269
92M      1013.1657
93      658812288653553079
94      283.165768537521
95      191.420778751.30327152671
96      193.22253377
97      11447.13842607235828485645766393
98      4363953127297
99      199.153649.33057806959
100L      101.8101
100M      5*.268501
101      7432339208719.341117531003194129
102      307.2857.6529
103      2550183799.3976656429941438590393
104      858001.308761441
105      29191.106681.152041
106      107.28059810762433
107      P33
108L      246241
108M      279073
109      745988807.870035986098720987332873
110      11*.2971.48912491
111      321679.26295457.319020217
112      5153.54410972897
113      3391.23279.65993.1868569.1066818132868207
114      571.160465489
115      14951.4036961.2646507710984041
116L      107367629
116M      536903681
117      937.6553.86113.7830118297
118      2833.37171.1824726041
119      239.20231.62983048367.131105292137
120      4562284561
121      727.P31
122      768614336404564651
123      3887047.177722253954175633
124L      5581.384773
124M      8681.49477
125      269089806001.4710883168879506001
126      77158673929
127      P39
128      274177.67280421310721
129      11053036065049294753459639
130      131.409891.7623851
131      263.P38
132L      312709
132M      4327489
133      P33
134      7327657.6713103182899
135      271.348031.49971617830801
136      17*.354689.2879347902817
137      32032215596496435569.5439042183600204290159
138      139.168749965921
139      5625767248687.P30
140L      47392381
140M      7416361
141      4375578271.646675035253258729
142      56409643.13952598148481
143      724153.158822951431.5782172113400990737
144      577.487824887233
145      P34
146      1753.1795918038741070627
147      7*.2741672362528725535068727
148L      149.184481113
148M      593.231769777
149      86656268566282183151.8235109336690846723986161
150      1133836730401
151      18121.55871.165799.2332951.7289088383388253664437433
152      1217.148961.24517014940753
153      919.75582488424179347083438319
154      617.78233.35532364099
155      31*.311.11471.73471.4649919401.18158209813151
156L      13*.313.1249
156M      3121.21841
157      852133201.60726444167.1654058017289.2134387368610417
158      201487636602438195784363
159      6679.13960201.540701761.229890275929
160      414721.44479210368001
161      1289.3188767.45076044553.14808607715315782481
162      3*.163.135433.272010961
163      150287.704161.110211473.27669118297.36230454570129675721
164L      181549.12112549
164M      10169.43249589
165      2048568835297380486760231
166      499.1163.2657.155377.13455809771
167      2349023.P44
168      3361.88959882481
169      4057.6740339310641.P31
170      26831423036065352611
171      93507247.3042645634792541312037847
172L      1759217765581
172M      173.101653.500177
173      730753.1505447.70084436712553223.155285743288572277679887
174      96076791871613611
175      39551.60816001.535347624791488552837151
176      229153.119782433.43872038849
177      184081.27989941729.9213624084535989031
178      179.62020897.18584774046020617
179      359.1433.P49
180L      181.54001
180M      29247661
181      43441.1164193.7648337.P37
182      224771.1210483.25829691707
183      367.55633.37201708625305146303973352041
184      291280009243618888211558641
185      1587855697992791.7248808599285760001152755641
186      529510939.2903110321
187      707983.P43
188L      140737471578113
188M      3761.7484047069
189      1560007.207617485544258392970753527
190      2281.3011347479614249131
191      383.7068569257.39940132241.332584516519201.87274497124602996457
192      18446744069414584321
193      13821503.61654440233248340616559.14732265321145317331353282383
194      971.1553.31817.1100876018364883721
195      P30
196L      4981857697937
196M      197.19707683773
197      7487.P56
198      5347.242099935645987
199      164504919713.P49
200      401.340801.2787601.3173389601
201      1609.22111.P32
202      P30
203      136417.121793911.P38
204L      409.3061.13669
204M      1326700741
205      2940521.70171342151.P31
206      415141630193.8142767081771726171
207      79903.634569679.2232578641663.42166482463639
208      78919881726271091143763623681
209      94803416684681.1512348937147247.5346950541323960232319657
210      211.664441.1564921
211      15193.60272956433838849161.P40
212L      1801439824104653
212M      15358129.586477649
213      66457.2849881972114740679.4205268574191396793
214      643.84115747449047881488635567801
215      1721.731516431.514851898711.297927289744047764444862191
216      33975937.138991501037953
217      5209.62497.6268703933840364033151.378428804431424484082633
218      104124649.2077756847362348863128179
219      3943.671165898617413417.4815314615204347717321
220L      415878438361
220M      3630105520141
221      1327.P55
222      3331.17539.107775231312019
223      18287.196687.1466449.2916841.1469495262398780123809.P24
224      449.2689.183076097.358429848460993
225      115201.617401.1348206751.13861369826299351
226      227.48817.636190001.491003369344660409
227      26986333437777017.P52
228L      131101.160969
228M      275415303169
229      1504073.20492753.59833457464970183.P39
230      691.1884103651.345767385170491
231      463.P34
232      59393.82280195167144119832390568177
233      1399.135607.622577.P57
234      5302306226370307681801
235      2391314881.72296287361.P35
236L      1181.3541.157649.174877
236M      5521693.104399276341
237      1423.49297.23728823512345609279.31357373417090093431
238      823679683.143162553165560959297
239      479.1913.5737.176383.134000609.P49
240      394783681.46908728641
241      22000409.P66
242      117371.11054184582797800455736061107
243      487.16753783618801.192971705688577.3712990163251158343
244L      733.1709.368140581013
244M      3456749.667055378149
245      1471.P48
246      739.165313.13194317913029593
247      15809.6459570124697.402004106269663.P34
248      290657.3770202641.1141629180401976895873
249      1621324657.P40
250      229668251.5519485418336288303251
251      503.54217.178230287214063289511.61676882198695257501367.P26
252L      118750098349
252M      40388473189
253      23*.4103188409.199957736328435366769577.P32
254      P38
255      106591.949111.P28
256      59649589127497217.5704689200685129054721
257      535006138814359.1155685395246619182673033.P39
258      1033.1591582393.15686603697451
259      2499285769.P56
260L      108140989558681
260M      521.51481.34110701
261      P51
262      1049.4744297.P30
263      23671.13572264529177.120226360536848498024035943.P36
264      7393.1761345169.98618273953
265      29324808311.197748738449921.P38
266      4523.P30
267      78903841.28753302853087.P32
268L      269.42875177.2559066073
268M      15152453.9739278030221
269      13822297.P74
270      811.15121.385838642647891
271      15242475217.P72
272      383521.2368179743873.373200722470799764577
273      108749551.4093204977277417.86977595801949844993
274      1097.15619.32127963626435681.105498212027592977
275      382027665134363932751.P40
276L      70334392823809
276M      5415624023749
277      1121297.31133636305610209482201109050392404721.P40
278      4506937.P35
279      16183.34039.1437967.833732508401263.2034439836951867299888617
280      84179842077657862011867889681
281      80929.P80
282      1681003.35273039401.111349165273
283      9623.68492481833.P71
284L      4999465853.472287102421
284M      569.148587949.5585522857
285      1491477035689218775711.25349242986637720573561
286      2003.6156182033.10425285443.15500487753323
287      17137716527.P62
288      1153.6337.38941695937.278452876033
289      12761663.179058312604392742511009.P52
290      7553921.999802854724715300883845411
291      272959.2065304407.5434876633.P34
292L      9444732965601851473921
292M      293.9929.649301712182209
293      40122362455616221971122353.P63
294      748819.26032885845392093851
295      4721.132751.5794391.128818831.3812358161.452824604065751.P22
296      P44
297      8950393.P48
298      1193.650833.38369587.7984559573504259856359124657
299      599.9341359.14718679249.13444476836590589479.51441563151591093599.260242449712509916159
300L      63901.13334701
300M      1201.1182468601
301      490631.365505823711978039310711.P47
302      18717738334417.P32
303      607.P58
304      27361.69394460463940481.11699557817717358904481
305      1831.2441.4271.270841.484074637694471.P42
306      123931.26159806891.27439122228481
307      14608903.85798519.23487583303.78952752017.P57
308L      869467061.3019242689
308M      8317.76096559910757
309      1953272766780718501831.P40
310      11161.5947603221397891.29126056043168521
311      5344847.2647649373910205158468946067671.P57
312      84159375948762099254554456081
313      10960009.14787970697180273.3857194764289141165278097.P47
314      15073.2350291.17751783757817897.96833299198971305921
315      870031.983431.P32
316L      604462909806215075725313
316M      317.381364611866507317969
317      9511.587492521482839879.4868122671322098041565641.P49
318      6043.4475130366518102084427698737
319      18503.64439.84819793631.P64
320      3602561.P32
321      17866285599391.P51
322      P40
323      647.7753.39044358788825633753.P61
324L      3618757.4977454861
324M      106979941.168410989
325      7151.51879585551.P58
326      11281292593.1023398150341859.337570547050390415041769
327      20597276734348736647.33157029794959983067039.P23
328      13121.8562191377.P35
329      12503.200033.9106063.270447871.P58
330      415365721.2252127523412251
331      16937389168607.865118802936559.P72
332L      13063537.148067197374074653
332M      997.46202197673.209957719973
333      1999.10657.169831.1238761.36085879.199381087.698962539799.4096460559560875111
334      P50
335      464311.1532217641.P65
336      2017.25629623713.1538595959564161
337      18199.2806537.95763203297.726584894969.P68
338      4929910764223610387.18526238646011086732742614043
339      10113049.320021624768405574452943847.P34
340L      1021.4421.550801.23650061
340M      7226904352843746841
341      5560125493425335999.126901141805369975317583.P49
342      19*.P32
343      6073159.1428389887.62228099977.P62
344      3855260977.64082150767423457.1425343275103126327372769
345      P54
346      347.4153.35374479827.47635010587.1643464247728189221623609
347      14143189112952632419639.P83
348L      22170214192500421
348M      349.29581.27920807689
349      1779973928671.34720396273212657799920861294559.P62
350      1051.110251.347833278451.34010032331525251
351      446473.29121769.571890896913727.93715008807883087.P21
352      5304641.P42
353      931921.2927455476800301964116805545194017.P67
354      13099.4453762543897.1898685496465999273
355      121932688511.P73
356L      1069.579017791994999956106149
356M      123794003928545064364330189
357      4999.245262248913715001137177.P31
358      58745093521.P43
359      719.855857.778165529.65877330027880703.370906580744492785430299503112990447.P39
360      168692292721.469775495062434961
361      9522401530937.36450568206770608791178096385783.P59
362      1811.31675363.P44
363      8713.7593961.75824014993.P45
364L      1093.1093.8861085190774909
364M      4733.556338525912325157
365      8761.13828603741081.82595052745831.P56
366      P37
367      12479.51791041.78138581882953.301311116540899114446723859201.P56
368      43717618369.549675408461419937.3970299567472902879791777
369      6376386802464073.P57
370      1481.28136651.P33
371      743.2969.63781899287.204712366597949333831.P57
372L      4611545283086450689
372M      373.951088215727633
373      25569151.P105
374      P49
375      751.P58
376      1198107457.23592342593.4501946625921233.181352306852476069537
377      5279.148055441.359661017.P81
378      379.119827.127391413339.56202143607667
379      180818808679.P103
380L      761.2416923620660807201
380M      54721.276696631250953741
381      2287.15241.349759.P63
382      P58
383      1440847.7435494593.503823044204581129045587727.15174923558680812616818436353130417.P39
384      769.P36
385      55441.1971764055031.P56
386      6563.35679139.1871670769.7455099975844049.1280761337388845898643
387      11492353.22763003975641.6834040335349578249140287.P31
388L      389.4657.4959325597.17637260034881
388M      3881.5821.3555339061.394563864677
389      56478911.4765678679.P100
390      107251.571403921126076957182161
391      37537.25806248225716242845491832244899635927231330561.P55
392      7057.273617.1007441.375327457.1405628248417.364565561997841
393      36093121.51118297.58352641.P55
394      197002597249.1348959352853811313.P30
395      12641.5435488351.16203007441.P70
396L      42373.15975607282273
396M      235621.8463901912489
397      2383.6353.50023.53993.202471.5877983.814132872808522587940886856743.1234904213576000272542841146073.P31
398      P60
399      73417.83791.P56
400      1601.25601.82471201.P33

sweety439 · 2019-11-23, 21:46

Quote:

Originally Posted by T.Rex

Hi,

I have no idea if this property is new. If new, I even am not sure it may be useful.
Anyway.

Let $q$ prime $>3$
$q=2p+1$ and thus $p=\frac{q-1}{2}$ .

Let:
$N_p=2^p+1$ .
$M_p=2^p-1$ Mersenne.
$N_p M_p = 2^{2p}-1=2^{q-1}-1$

Let:
$W_q=\frac{2^q+1}{3}$ Wagstaff.

Then:
$2N_pM_p+3 = 2^q-2+3 = 2^q+1 = 3W_q$

Thus the property : $W_q = \frac{2}{3}N_pM_p+1$ . CQFD.

$\alpha \mid W_q \Rightarrow \alpha = 1+2q\alpha'$
thus : $W_q = 1+2q\beta$ and $2q\beta = W_q-1 = \frac{2}{3}N_pM_p$
thus : $q \, \mid \, \frac{N_pM_p}{3}$ and thus either $q \mid N_p$ or $q \mid M_p$ .

Examples :
$q=11 , \, p=5 , \, q \mid N_p$
$q=17 , \, p=8 , \, q \mid M_p$
$q=47 , \, p=23 , \, q \mid M_p$
$q=59 , \, p=29 , \, q \mid N_p$
$q=257 , \, p=2^7 , \, q \mid M_p$
$q=65537 , \, p=2^{15} , \, q \mid ?_p$

Probably one should only consider cases where p is a prime or a power of 2.

If $p = 2^n$ , then 3 divides $M_p$ since only numbers $k.2^{n+1}+1$ can divide a Fermat number. Can $k$ be $1$ ?

If p is a prime, thus 3 cannot divide $M_p$ since only numbers $1+\alpha p$ can divide a Mersenne number, and thus 3 divides $N_p$ .
So, when p is a prime, when does it divide $N_p$ and not $M_p$ and vice-versa ??

if p is prime, q=2*p+1 is also prime, then:

q divides M_p if and only if p = 3 mod 4

q divides W_p if and only if p = 1 mod 4

a1call · 2019-11-23, 22:25

The Mersenne part has been known since 1775 as proven in this link first shown to me by sm:
https://primes.utm.edu/notes/proofs/MerDiv2.html
It is of practical use in proving factors of Mersenne numbers with prime exponents prime.
23 is guaranteed to be prime because it divides M11 and 23= 2*11+1

sweety439 · 2019-11-23, 22:39

Quote:

Originally Posted by a1call

The Mersenne part has been known since 1775 as proven in this link first shown to me by sm:
https://primes.utm.edu/notes/proofs/MerDiv2.html
It is of practical use in proving factors of Mersenne numbers with prime exponents prime.
23 is guaranteed to be prime because it divides M11 and 23= 2*11+1

341 divides M170 and 341=2*170+1, but 341 is not prime

a1call · 2019-11-23, 22:46

The Mersenne composite must have a prime exponent.
Is 170 a prime number?

2019-11-22, 15:32	#1
T.Rex Feb 2004 France 392₁₆ Posts	(New ?) Wagstaff/Mersenne related property Hi, I have no idea if this property is new. If new, I even am not sure it may be useful. Anyway. Let $q$ prime $>3$ $q=2p+1$ and thus $p=\frac{q-1}{2}$ . Let: $N_p=2^p+1$ . $M_p=2^p-1$ Mersenne. $N_p M_p = 2^{2p}-1=2^{q-1}-1$ Let: $W_q=\frac{2^q+1}{3}$ Wagstaff. Then: $2N_pM_p+3 = 2^q-2+3 = 2^q+1 = 3W_q$ Thus the property : $W_q = \frac{2}{3}N_pM_p+1$ . CQFD. $\alpha \mid W_q \Rightarrow \alpha = 1+2q\alpha'$ thus : $W_q = 1+2q\beta$ and $2q\beta = W_q-1 = \frac{2}{3}N_pM_p$ thus : $q \, \mid \, \frac{N_pM_p}{3}$ and thus either $q \mid N_p$ or $q \mid M_p$ . Examples : $q=11 , \, p=5 , \, q \mid N_p$ $q=17 , \, p=8 , \, q \mid M_p$ $q=47 , \, p=23 , \, q \mid M_p$ $q=59 , \, p=29 , \, q \mid N_p$ $q=257 , \, p=2^7 , \, q \mid M_p$ $q=65537 , \, p=2^{15} , \, q \mid ?_p$ Probably one should only consider cases where p is a prime or a power of 2. If $p = 2^n$ , then 3 divides $M_p$ since only numbers $k.2^{n+1}+1$ can divide a Fermat number. Can $k$ be $1$ ? If p is a prime, thus 3 cannot divide $M_p$ since only numbers $1+\alpha p$ can divide a Mersenne number, and thus 3 divides $N_p$ . So, when p is a prime, when does it divide $N_p$ and not $M_p$ and vice-versa ?? Last fiddled with by T.Rex on 2019-11-22 at 16:24

2019-11-23, 00:51	#2
GP2 Sep 2003 3²·7·41 Posts	Renaud and Henri Lifchitz mentioned this relation in a 2000 paper, see section 4. Note: they use N_p to denote what we call W_p. As they point out, this relation means that if W_2n+1 is PRP, then if either W_n or M_n are fully factored, then W_2n+1 can be proven prime by the N−1 method. (Note n does not need to be prime, only 2n+1). For instance, if we could fully factor M₄₇₆₈₄ or W₄₇₆₈₄ then we could prove that W₉₅₃₆₉ is not just PRP but prime. Spoiler alert: they are nowhere near fully-factored. Or we could look at all Mersenne primes M_p for which 2p+1 is also prime (OEIS A065406) and check to see if any unfactored W_2p+1 test PRP. Spoiler alert: they don't. M_43,112,609 is a Mersenne prime but W_86,225,219 is composite. In short, this relation doesn't have much practical use. Last fiddled with by GP2 on 2019-11-23 at 01:01

2019-11-23, 22:25	#5
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 1981₁₀ Posts	The Mersenne part has been known since 1775 as proven in this link first shown to me by sm: https://primes.utm.edu/notes/proofs/MerDiv2.html It is of practical use in proving factors of Mersenne numbers with prime exponents prime. 23 is guaranteed to be prime because it divides M11 and 23= 211+1 Last fiddled with by a1call on 2019-11-23 at 22:26*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Status of Wagstaff testing? and testing Mersenne primes for Wagstaff-ness	GP2	Wagstaff PRP Search	414	2020-12-27 08:11
Question about a mersenne-number property	sascha77	Math	43	2011-03-14 23:51
A conjecture on a new property of Mersenne primes	Thiele	Math	18	2010-05-23 05:35
Curious property of Mersenne numbers.	arithmeticae	Lounge	5	2008-10-27 06:15
A property of prime Mersenne numbers under LLT	T.Rex	Math	12	2005-09-12 07:56

2019-11-23, 22:46	#7
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 7·283 Posts	The Mersenne composite must have a prime exponent. Is 170 a prime number?