mersenneforum.org Mn theorems +1 mod
 Register FAQ Search Today's Posts Mark Forums Read

 2021-03-11, 12:05 #1 PAT291   Feb 2017 Belgium 3·7 Posts Mn theorems +1 mod Is there any theorem that says that if Mn divides (a^(n-1)/2 + 1) for some a > 2 then Mn is prime? Where can I find related theorems. Thanks in advance
 2021-03-11, 13:16 #2 axn     Jun 2003 10011001100102 Posts Assuming that you meant to write a^(Mn-1)/2 + 1, have a look at https://en.wikipedia.org/wiki/Euler_pseudoprime
 2021-03-11, 13:54 #3 PAT291   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?
 2021-03-11, 14:58 #4 Dr Sardonicus     Feb 2017 Nowhere 105628 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^((P-1)/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 non-residue (mod P). We then have the familiar 3-PRP test If p > 2 is prime, and Mod(3, 2^p - 1)^(2^(p-1)) + 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 3-PRP fails to detect a composite Mp.
2021-03-11, 15:05   #5
LaurV
Romulan Interpreter

Jun 2011
Thailand

100100100111112 Posts

Quote:
 Originally Posted by Dr Sardonicus I am not aware of any examples where the 3-PRP fails to detect a composite Mp.
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 3-prp 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 3-pseudoprimes.

Last fiddled with by LaurV on 2021-03-11 at 15:11

2021-03-11, 16:16   #6
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

26628 Posts

Quote:
 Originally Posted by PAT291 Is there any theorem that says that if Mn divides (a^(n-1)/2 + 1) for some a > 2 then Mn is prime? Where can I find related theorems. Thanks in advance
So you want to say that if a^((mp-1)/2)==-1 mod mp for given a>2 then mp is prime.
It would follow that Mp is always prime(!), just use a=-1+mp. To see a non-trivial counterexample: let a=11 and p=11 then your equation holds, but m11=23*89 is composite.

2021-03-11, 16:40   #7
Dr Sardonicus

Feb 2017
Nowhere

2·7·11·29 Posts

Quote:
 Originally Posted by LaurV 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 3-prp 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.
Could you please post one of these, or, if previously posted, give a link?

I can only imagine the fun that would ensue if

Mod(3, 2^p - 1)^(2^(p-1)) + 3 == Mod(0, 2^p -1) but

LL test says 2^p - 1 is composite.

2021-03-11, 16:50   #8
PAT291

Feb 2017
Belgium

3·7 Posts

Quote:
 Originally Posted by R. Gerbicz So you want to say that if a^((mp-1)/2)==-1 mod mp for given a>2 then mp is prime. It would follow that Mp is always prime(!), just use a=-1+mp. To see a non-trivial counterexample: let a=11 and p=11 then your equation holds, but m11=23*89 is composite.

11 seems not a good 'a'. 3 seems a candidate. If I read well, there's no counterexemple for the 3-PRP test for Mn numbers

2021-03-11, 17:14   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

26628 Posts

Quote:
 Originally Posted by PAT291 11 seems not a good 'a'. 3 seems a candidate. If I read well, there's no counterexemple for the 3-PRP test for Mn numbers
It is a perfect counterexample to your claim in the first post. Likely a=11 seems to be equally good just as a=3, maybe there is no other counterexample for a=11. Let me check [only the first few odd primes as base, ofcourse a=2 is not good]:
Code:
? G(a)=forprime(p=2,2000,mp=2^p-1;if(Mod(a,mp)^((mp-1)/2)==Mod(-1,mp)&&isprime(mp)==0,print(p)))
%19 = (a)->forprime(p=2,2000,mp=2^p-1;if(Mod(a,mp)^((mp-1)/2)==Mod(-1,mp)&&isprime(mp)==0,print(p)))
? G(3)
? G(5)
? G(7)
? G(11)
11
? G(13)
? G(17)
?
(tesing only p<2000).

2021-03-11, 18:40   #10
PAT291

Feb 2017
Belgium

1516 Posts

Quote:
 Originally Posted by R. Gerbicz It is a perfect counterexample to your claim in the first post. Likely a=11 seems to be equally good just as a=3, maybe there is no other counterexample for a=11. Let me check [only the first few odd primes as base, ofcourse a=2 is not good]: Code: ? G(a)=forprime(p=2,2000,mp=2^p-1;if(Mod(a,mp)^((mp-1)/2)==Mod(-1,mp)&&isprime(mp)==0,print(p))) %19 = (a)->forprime(p=2,2000,mp=2^p-1;if(Mod(a,mp)^((mp-1)/2)==Mod(-1,mp)&&isprime(mp)==0,print(p))) ? G(3) ? G(5) ? G(7) ? G(11) 11 ? G(13) ? G(17) ? (tesing only p<2000).

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 2021-03-11 at 19:19

2021-03-11, 19:31   #11
paulunderwood

Sep 2002
Database er0rr

1110001000102 Posts

Quote:
 Originally Posted by PAT291 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
3 is special because kronecker(3,Mp)==-1 for all odd p.

Lehmer's test is an efficient implementation of Mod(Mod(x+2,Mp),x^2-3)^2^p==1

Last fiddled with by paulunderwood on 2021-03-11 at 19:48

 Similar Threads Thread Thread Starter Forum Replies Last Post jnml Miscellaneous Math 10 2019-04-21 15:33 ShiningArcanine Math 21 2012-04-27 01:38 fivemack Abstract Algebra & Algebraic Number Theory 10 2012-01-22 11:01 sghodeif Miscellaneous Math 18 2006-07-13 18:24

All times are UTC. The time now is 21:09.

Sat Apr 17 21:09:13 UTC 2021 up 9 days, 15:50, 0 users, load averages: 1.35, 1.43, 1.46