20210311, 12:05  #1 
Feb 2017
Belgium
3·7 Posts 
Mn theorems +1 mod
Is there any theorem that says that if Mn divides (a^(n1)/2 + 1) for some a > 2 then Mn is prime? Where can I find related theorems. Thanks in advance

20210311, 13:16  #2 
Jun 2003
1001100110010_{2} Posts 
Assuming that you meant to write a^(Mn1)/2 + 1, have a look at https://en.wikipedia.org/wiki/Euler_pseudoprime

20210311, 13:54  #3 
Feb 2017
Belgium
3×7 Posts 
Thanks. I wasalready given some information about pseudoprimes. Indeed sometimes they weretalking about pseudoprimes. It was always one direction. Apparently it's also the case for Eulerpseudoprimes.
If I amcorrect there exists no such theorem (as stated above). Is that true? My nextquestion. If somebody can proof that, under some conditions, the above holds,can it be helpful in calculations? Would it be interesting for this forum? 
20210311, 14:58  #4 
Feb 2017
Nowhere
10562_{8} Posts 
A specific instance has been discussed previously in this Forum, in, e.g. this thread.
If P is prime, and gcd(a, P) == 1 then a^((P1)/2) == (a/P) (mod P) [quadratic character; 1 if a is a quadratic residue mod P, 1 if not]. Multiplying through by "a" gives a convenient formula for a square root of a quadratic residue if P == 3 (mod 4). It also gives an especially convenient exponent if P = Mp = 2^p  1. If p > 2 and Mp = P is prime, 3 is a quadratic nonresidue (mod P). We then have the familiar 3PRP test If p > 2 is prime, and Mod(3, 2^p  1)^(2^(p1)) + 3 <> Mod(0, 2^p  1), then 2^p  1 is composite. If equality holds, it is possible AFAIK that 2^p  1 could still be composite, so an LL test would be required to be certain. I am not aware of any examples where the 3PRP fails to detect a composite Mp. 
20210311, 15:05  #5 
Romulan Interpreter
Jun 2011
Thailand
10010010011111_{2} Posts 
Albeit they are possible in theory (i.e. there is no proof of the contrary, and if they exist, they are called "pseudoprimes"), you would be more famous if you find one such pseudoprime, than if you find a 1 billion digits mersenne prime. Please note that when talking about composite mersenne factors, there are few known which are pseudoprime. It was my "belief" in the past that they do not exist (so a 3prp would be enough to decide if a cofactor is prime or composite), but I could not prove it, and later a forumite here provided me with counterexamples. Thinking by extrapolation, a composite mersenne is just a product of prime mersenne factors (similar to a composite cofactor), so there is no reason why some of them would not be 3pseudoprimes.
Last fiddled with by LaurV on 20210311 at 15:11 
20210311, 16:16  #6  
"Robert Gerbicz"
Oct 2005
Hungary
2662_{8} Posts 
Quote:
It would follow that Mp is always prime(!), just use a=1+mp. To see a nontrivial counterexample: let a=11 and p=11 then your equation holds, but m11=23*89 is composite. 

20210311, 16:40  #7  
Feb 2017
Nowhere
2·7·11·29 Posts 
Quote:
I can only imagine the fun that would ensue if Mod(3, 2^p  1)^(2^(p1)) + 3 == Mod(0, 2^p 1) but LL test says 2^p  1 is composite. 

20210311, 16:50  #8  
Feb 2017
Belgium
3·7 Posts 
Quote:
11 seems not a good 'a'. 3 seems a candidate. If I read well, there's no counterexemple for the 3PRP test for Mn numbers 

20210311, 17:14  #9  
"Robert Gerbicz"
Oct 2005
Hungary
2662_{8} Posts 
Quote:
Code:
? G(a)=forprime(p=2,2000,mp=2^p1;if(Mod(a,mp)^((mp1)/2)==Mod(1,mp)&&isprime(mp)==0,print(p))) %19 = (a)>forprime(p=2,2000,mp=2^p1;if(Mod(a,mp)^((mp1)/2)==Mod(1,mp)&&isprime(mp)==0,print(p))) ? G(3) ? G(5) ? G(7) ? G(11) 11 ? G(13) ? G(17) ? 

20210311, 18:40  #10  
Feb 2017
Belgium
15_{16} Posts 
Quote:
sorry, I believe it's true for a=3 and was looking for some theorems or whether there existed already some proof. At the same time I wondered if it was maybe true for other a. thanks for the quick reaction Last fiddled with by PAT291 on 20210311 at 19:19 

20210311, 19:31  #11  
Sep 2002
Database er0rr
111000100010_{2} Posts 
Quote:
Lehmer's test is an efficient implementation of Mod(Mod(x+2,Mp),x^23)^2^p==1 Last fiddled with by paulunderwood on 20210311 at 19:48 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Theorems about Mersenne numbers  jnml  Miscellaneous Math  10  20190421 15:33 
Mersenne theorems question  ShiningArcanine  Math  21  20120427 01:38 
Theorems about ideals  fivemack  Abstract Algebra & Algebraic Number Theory  10  20120122 11:01 
new theorems about primes  sghodeif  Miscellaneous Math  18  20060713 18:24 