mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2021-03-11, 12:05   #1
PAT291
 
Feb 2017
Belgium

3·7 Posts
Default 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
PAT291 is offline   Reply With Quote
Old 2021-03-11, 13:16   #2
axn
 
axn's Avatar
 
Jun 2003

10011001100102 Posts
Default

Assuming that you meant to write a^(Mn-1)/2 + 1, have a look at https://en.wikipedia.org/wiki/Euler_pseudoprime
axn is offline   Reply With Quote
Old 2021-03-11, 13:54   #3
PAT291
 
Feb 2017
Belgium

3×7 Posts
Default

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?
PAT291 is offline   Reply With Quote
Old 2021-03-11, 14:58   #4
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

105628 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-03-11, 15:05   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100100100111112 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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
LaurV is offline   Reply With Quote
Old 2021-03-11, 16:16   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26628 Posts
Default

Quote:
Originally Posted by PAT291 View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2021-03-11, 16:40   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·7·11·29 Posts
Default

Quote:
Originally Posted by LaurV View Post
<snip>
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.
<snip>
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.
Dr Sardonicus is offline   Reply With Quote
Old 2021-03-11, 16:50   #8
PAT291
 
Feb 2017
Belgium

3·7 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
PAT291 is offline   Reply With Quote
Old 2021-03-11, 17:14   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26628 Posts
Default

Quote:
Originally Posted by PAT291 View Post
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).
R. Gerbicz is offline   Reply With Quote
Old 2021-03-11, 18:40   #10
PAT291
 
Feb 2017
Belgium

1516 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
PAT291 is offline   Reply With Quote
Old 2021-03-11, 19:31   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110001000102 Posts
Default

Quote:
Originally Posted by PAT291 View Post
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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Theorems about Mersenne numbers jnml Miscellaneous Math 10 2019-04-21 15:33
Mersenne theorems question ShiningArcanine Math 21 2012-04-27 01:38
Theorems about ideals fivemack Abstract Algebra & Algebraic Number Theory 10 2012-01-22 11:01
new theorems about primes 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.