20110519, 11:54  #1 
Aug 2010
SPb
22_{16} Posts 
New test for Mersenne prime
Post of Russia
http://dxdy.ru/post447534.html#p447534 sequence in the OEIS A190213 Numbers n such that a==0(mod k) and b==0(mod k), where k=2^n1, m=(2^n1)*(n1)n+2, x=m*(2^n1), 2^(x1)==(a+1)(mod x), m^(x1)==(b+1)(mod x) 1, 3, 4, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217 EXAMPLE n=3 k=2^31=7 m=(2^31)*(31)3+2=13 x=m*(2^n1)=13*7=91 2^(x1)==(a+1)(mod x);2^90==(63+1)(mod 91), a=63 m^(x1)==(b+1)(mod x);13^90==(77+1)(mod 91), b=77 test conditions a==0(mod k), 63==0(mod 7) b==0(mod k), 77==0(mod 7)  All odd numbers are of Mersenne exponents: primes n such that 2^n  1 is prime A000043 4 is the only even number why not 2? I do not know ..... 
20110519, 12:51  #2 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2×5,399 Posts 

20110519, 13:39  #3  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:
Code:
(10:34)>test(n)= k=2^n1;m=(2^n1)*(n1)n+2;x=m*(2^n1);a=((2^(x1))%x)1;b=((2^(x1))%x)1;if(a%k==0 && b%k==0,print(n)) %167 = (n)>k=2^n1;m=(2^n1)*(n1)n+2;x=m*(2^n1);a=((2^(x1))%x)1;b=((2^(x1))%x)1;if(a%k==0&&b%k==0,print(n)) (10:36)>for(n=1,100,test(n)) 1 2 3 4 5 7 9 11 *** _^_: length (lg) overflow 

20110519, 14:23  #4  
"Forget I exist"
Jul 2009
Dartmouth NS
10000011100010_{2} Posts 
Quote:
Quote:


20110519, 17:49  #5 
Bemusing Prompter
"Danny"
Dec 2002
California
3·829 Posts 
Inb4miscmaththreads.

20110519, 19:19  #6  
Einyen
Dec 2003
Denmark
3,413 Posts 
Testing natural numbers from 2 to 11213, this conjecture is true only for the exponents of the 23 first prime mersenne numbers except 2 is missing and 4 is included:
3,4,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213 Quote:
k=2^{n}1, m=k*(n1)n+2, x=m*k Now your conditions is equivalent to: 2^{x1} = 1 (mod k) AND (kn+2)^{x1} = 1 (mod k) Explanation: Since x=m*k: 2^(x1)==(a+1)(mod m*k) => 2^(x1) = m*k*c1 + a+1 for some constant c1 and a==0(mod k) => a = k*c2 for some constant c2. Inserting k*c2 for a in the first equation gives: 2^(x1) = m*k*c1 + k*c2 + 1 = 1 (mod k) In the same way it can be shown: m^(x1) = 1 (mod k) But instead of m it's faster to use m mod k: m = k*(n1)n+2 = n+2 (mod k) = kn+2 (mod k) (n+2 is negative, so if we want we can add k to make it positive) So: m^(x1) = (n+2)^(x1) = (kn+2)^(x1) = 1 (mod k) This is why n=2 doesn't work since kn+2 = k and k^(x1) = 0 (mod k) Last fiddled with by ATH on 20110519 at 19:26 

20110519, 20:01  #7  
"Forget I exist"
Jul 2009
Dartmouth NS
2×3×23×61 Posts 
Quote:


20110519, 20:33  #8 
Einyen
Dec 2003
Denmark
3,413 Posts 

20110519, 20:39  #9 
"Forget I exist"
Jul 2009
Dartmouth NS
2·3·23·61 Posts 
it gave the list he gave different before it ran into the length overflow. and you can check my test I posted the code. % is mod in this case.
Last fiddled with by science_man_88 on 20110519 at 20:40 
20110519, 21:05  #10 
"Forget I exist"
Jul 2009
Dartmouth NS
20E2_{16} Posts 
tried your suggestions to him and I got a length overflow using only primes before I saw 11 ( and I saw 11 in the version I was originally using).

20110519, 21:09  #11 
Einyen
Dec 2003
Denmark
110101010101_{2} Posts 
Actually only the condition (kn+2)^{x1} = 1 (mod k) is needed, I get the same results just searching for numbers fulfilling this.
Last fiddled with by ATH on 20110519 at 21:09 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED!  dabaichi  News  571  20201026 11:02 
Another way to PRP test Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170126 20:33 
How do I test if it is a mersenne prime on GIMPS?  spkarra  Math  21  20150123 18:13 
another mersenne prime test  jocelynl  Math  8  20061020 19:36 
The 40th known Mersenne prime, 2209960111 is not PRIME!  illmanq  Miscellaneous Math  33  20040919 05:02 