Mn theorems +1 mod

[Dr Sardonicus]

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

This is going to miss cases when (a/Mp) = +1 if Mp is prime (which I'm guessing would be about half the cases for a given a > 3).

For example, (5/Mp) = +1 if Mp is prime and p == 1 (mod 4), but (5/Mp) = -1 if Mp is prime and p == 3 (mod 4). (IIRC this came up in a test devised by Lucas, but I'm too lazy to track it down.)

[LaurV]

Originally Posted by Dr Sardonicus

Could you please post one of these, or, if previously posted, give a link?

I remember discussions many years ago, but my memory is getting weak.... I mean I have a good memory but I don't remember exactly where I put it...

Long time ago I believed that mersenne factors behave in some similar way to fermat numbers (there are many reasons why that should be), and some similar "pepin test" would work for them (which is essentially a 3-PRP test), but I could not prove it. That would mean a 3-prp test, eventually with a "small tweak", could show if a cofactor is composite or not. Such "trick" would have been very useful and extremely valuable for our cofactoring ("disbelievers...") thread and people who do the PRP-CF work. Unfortunately, I was wrong, or just unable to find the "tweak". That's how we all learn...

Here is a discussion about rarity of PSP numbers (read following 3-4 posts too, before RDS jumped in and killed everybody ), and here is an example of a 3-PSP cofactor (i.e. it is 3-PRP, but still composite). There are not many of those, but they are enough. Some "didactic" implementation of a PSP-finder that also popped up with the search, and some may find it useful, is here (hey, don't jump to my head, it is didactic, i.e. to teach how it is done, not an optimized one!)

Edit: Here is another post which made it through the search filter. I would put it in a frame (the post, not the filter!) and stick it on a wall for the beginners who join the forum and ask the same questions again and again (HA! in the past I was more clever, and I had more patience, I totally forgot I was posting things like that on the forum )

[PAT291]

So thereexists no proof nor counterexample for a=3 yet? A proof is still possible?
“If (3^(Mn-1)/2+ 1)==0 (mod Mn) then Mn is prime”. It may still be possible to prove this. And it's worthwhile
If itstands, I believe it’s possible to speed up some calculations.
If I read well there are still some "strong believers" to it

[PAT291]

Now, I am trying to prove whether there exists some kind of induction for the Catalan sequence 3, 7, 127, … (if Ci divides 3^(Ci-1)/2 + 1==0 (mod Ci) for i=n,n+1,n+2 then it holds for i=n+3 or something like that) or a kind of maximum number of iterations f.e. 5. But I am not that strong with modulo calculations. I do notice some things running small macro’s.

I believe there is no MMn when there’s a r<n/4 for which 3^r + 1 == 0 (mod Mn), f.e. 3^445 + 1 == 0 (mod M13). The same goes for M31. Note, it can been proved in less than 10 steps that M12 is prime (if my assumption stands). This might be equivalent to the zero’s appearing in the sequence 2^k-1 == 0 (mod Mn) for n=11 and k < Mn-1.

Even if my assumption doesn’t stand it might be interesting if someone can give a feedback on the observations I made. Persons strong in modulo calculus certainly can give quickly some comments.

[Dr Sardonicus]

Originally Posted by LaurV

<snip>
Interesting enough, you can find small multiple-base-PSP very easy for small composite factors of mersenne numbers, for example 10974881 is both 2-PRP and 3-PRP, but it not a prime (it is a PSP product of 1913 and 5737, prime factors of M239).

Pepin's test works for Fermat numbers because if P = F_n the only prime factor of P - 1 is 2. If n > 0 and P is prime, 3 is a quadratic non-residue (mod P) so Mod(3,P)^((P-1)/2) = Mod(-1,P).

Conversely, if Mod(3, P)^((P-1)/2) = Mod(-1,P) then Mod(3,P) has multiplicative order exactly P-1, so P is prime.

The situation for Mersenne numbers is alas more complicated. We know that if p > 2 is prime, any prime factor q of 2^p - 1 is of the form q = 2*k*p + 1. This means that all the q-1 have the common factor 2*p, which is also a factor of any product of the q's minus 1. (As axn already noted back when) Since the exact multiplicative order of 2 (mod q) is always p, and p divides q-1 for every q, you can be sure that any product of the q's is a base-2 Fermat pseudoprime. It is also easy to see that any such product will "pass" the Euler test.

If we want a product of q's to be a base-3 Fermat pseudoprime, we want the lcm of the znorder(Mod(3, q)) to divide the product of the q's minus 1.

For the factors 1913 and 5737 of M239 (Thank you very much!) we have 1913 = 2*4*239 + 1 and 5737 = 2*12*239 + 1. The gcd of the q-1 values is 8*239.

It happens that znorder(Mod(3, 5737)) = 4*239, which guarantees n = 1913*5737 is a base-3 Fermat pseudoprime.

Note, however, that Mod(n,12) = Mod(5,12) so kronecker(3,n) == -1, but Mod(3,n)^((n-1)/2) == Mod(1, n) so the Euler test detects it as composite.

[PAT291]

Thx. So 3^(M239-1)/2 == 1 (mod M239). It’s not a counterexample to my assumption?

[Dr Sardonicus]

Originally Posted by PAT291

Thx. So 3^(M239-1)/2 == 1 (mod M239). It’s not a counterexample to my assumption?

I didn't say that. I said that 3^((n-1)/2) == 1 (mod n) where n= 1913*5737 is a small composite factor of M239.

I suggest you stop responding to posts as if you hadn't read them.

[PAT291]

Originally Posted by Dr Sardonicus

I didn't say that. I said that 3^((n-1)/2) == 1 (mod n) where n= 1913*5737 is a small composite factor of M239.

I suggest you stop responding to posts as if you hadn't read them.

Sorry if you take it that way. I didn’t catch the meaning of your post. I know about the q=2kp+1 and Pepin’s test for Fermat numbers.

I still believe “If (3^(Mn-1)/2 + 1)==0 (mod Mn)then Mn is prime” (Mn being a Mersenne number) is provable (and that I can proof it). If I read well the topics no proof or counterexample exists yet. So a proof is possible. But maybe I made an error somewhere or missed something that already exists.

[PAT291]

Let me rephrase my original post.

I claim that if (3^(Mn-1)/2 + 1)==0 (mod Mn) then Mn is prime. Mn being a Mersenne number.

Maybe it holds also for other bases <> 3 (and 2).

[PAT291]

I spend a lot of time trying to prove it. It was a big puzzle. A few weeks ago I believe to have found the last piece. Maybe I made a mistake along the way, that’s why I am very careful. Verification still has to be done. But is useless to verify if somebody tells it’s not possible or if there exists a counterexample. That means that I have to look for the error(s) …

I am afraid, and nervous :-), I made an error somewhere after all …

[Dr Sardonicus]

Originally Posted by PAT291

I spend a lot of time trying to prove it. It was a big puzzle. A few weeks ago I believe to have found the last piece. Maybe I made a mistake along the way, that’s why I am very careful. Verification still has to be done. But is useless to verify if somebody tells it’s not possible or if there exists a counterexample. That means that I have to look for the error(s) …

I am afraid, and nervous :-), I made an error somewhere after all …

Nobody said a proof was not possible. A number of people have pointed out that no proof is known. There is AFAIK no known composite Mp the test has failed to detect. There are however known composite factors of Mp's which are base-3 Fermat pseudoprimes.

I note that the 3-PRP test was probably not done on any Mp for which a prime factor q was found during initial factorization attempts. In such a case, it might be possible to prove that Mp is not a 3-PRP without actually running the test on Mp itself. If the multiplicative order of Mod(3,q) does not divide Mp - 1, then Mp is not a 3-PRP. (For example, 2^11 - 1 = 23*89, and the multiplicative order of Mod(3,89) is 88, which, being divisible by 4, does not divide 2^11 - 2.)

Recognizing the possibility of having made a mistake is a sign of maturity. If you want to know for sure, submit your argument to scrutiny by others. If your argument is wrong, acknowledge it, learn from it, and move on.