Mn theorems +1 mod

[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

[axn]

Assuming that you meant to write a^(Mn-1)/2 + 1, have a look at https://en.wikipedia.org/wiki/Euler_pseudoprime

[PAT291]

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?

[Dr Sardonicus]

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.

[LaurV]

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.

[R. Gerbicz]

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.

[Dr Sardonicus]

Originally Posted by LaurV

<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.

[PAT291]

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

[R. Gerbicz]

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]:

? 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).

[PAT291]

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]:

? 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

[paulunderwood]

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