Amazing 6

[paulunderwood]

Originally Posted by PAT291

what if it is only true for prime Mp for base 3, and never when Mn is not a prime? wasn't it the question at the beginning of the topic? amazing 6, or 3?

No, it was not the question at the beginning of the topic.

With only 51 known Mersenne prime < ~25 million digits and your condition being neccesary, we will probably never know of a contradiction in our lifetimes. Many people have looked in to this problem have not been able to produce a proof of it. It is an open question. Who knows? Infinity is big, really big.

Infinite: Bigger than the biggest thing ever and then some.
Much bigger than that in fact, really amazingly immense, a
totally stunning size, "wow, that's big", time. Infinity is just so
big that by comparison, bigness itself looks really titchy.
Gigantic multiplied by colossal multiplied by staggeringly
huge is the sort of concept we're trying to get across here.

[PAT291]

So if somebody can proof that “if (3^(Mn-1)/2 + 1)==0 (mod Mn) then Mn is prime”, it would be a kind of breakthrough J

It would be another primality test

[PAT291]

Originally Posted by PAT291

So if somebody can proof that “if (3^(Mn-1)/2 + 1)==0 (mod Mn) then Mn is prime”, it would be a kind of breakthrough J

It would be another primality test

correction: it would be a primality test for Mersenne numbers

[Dr Sardonicus]

Originally Posted by paulunderwood

<snip>
With only 51 known Mersenne prime < ~25 million digits and your condition being neccesary, we will probably never know of a contradiction in our lifetimes.
<snip>

I doubt a composite Mp which is a a strong base-3 PRP will be found any time soon.

But it is possible AFAIK that there could be a composite Mp with p < 1000000 or even p < 100000 which provides a counterexample. The reason I say this is that I'm sure the condition

Mod(3,Mp)^((Mp-1)/2) == Mod(-1, Mp)

was never tested on many such Mp, because they were proved composite by virtue of a proper factor being found. Of course, if q divides Mp and q == 5 (mod 6) the condition is guaranteed to fail, so no need to test.

I have no idea for how many p the above condition has actually been checked. IIRC I checked that it excluded all Mp except the known primes for p < 5000, and may have run it up a bit higher.

[PAT291]

Originally Posted by PAT291

So if somebody can proof that “if (3^(Mn-1)/2 + 1)==0 (mod Mn) then Mn is prime”, it would be a kind of breakthrough J

It would be another primality test

Originally Posted by PAT291

correction: it would be a primality test for Mersenne numbers

note: testing off course is only useful for well chosen n i.e. at least prime

[PAT291]

Originally Posted by Dr Sardonicus

I have no idea for how many p the above condition has actually been checked. IIRC I checked that it excluded all Mp except the known primes for p < 5000, and may have run it up a bit higher.

I verified myself for p<1000 (with limited resources). Then stopped and wanted to know if there existed any counterexample (or counterproof). When my assumption stands it would be a waste of time looking for counterexamples. Although, every run that doesn't yields to a counterexample, raises the probability of my assumption.


I'm sure that if my assumption stands primality can be proven in less then n steps, at least in some cases f.e. M13 in less then 8 steps. AFAIK the number of steps today is p-2 (Sp-2 == 0 mod Mp)

[paulunderwood]

Getting back on track for this thread...

• Let b != +-2^s
• Let a = b^r where kronecker(a^2-1,n) == -1
• Test1: (a^2-1,n)^((n-1)/2) == -1 (mod n)
• Test2: (b*x)^((n+1)/2) == b*kronecker(b*2*(a+1),n) (mod n, x^2-2*a*x+1)

Without solving the DLOG for the first condition can we let b=3?

[paulunderwood]

If n = 2^s+-3, letting b = 5 would mean 2^s-2 would okay for a base or 2^s -8 would also be okay for a base, since neither are powers ;
of 2. So apart from these corner cases taking b=3 should be fine. Maybe I should consider n=2^(k*s)-3^k too?

Testing is slow as it is a triple loop, I can test some larger numbers of 10 or more digits but again testing is slow. I will let things soak for a while before trying to think of an easy way to find a counterexample, maybe with b=3 in a double loop or by some CRT method on semi-primes.

Soon after I found a counterexample:

? [n,a]=V[1]                                                             
[6192880203469, 2798764784749]
? Mod(a,n)^((n-1)/2)==-1                                                             
1
? Mod(Mod(a*x,n),x^2-2*a*x+1)^((n+1)/2)==a*kronecker(a*2*(a+1),n)                
1
? znlog(a,Mod(2,n))                              
[]

[paulunderwood]

• Let a=2^r, r odd and minimal such that kronecker(a^2-1,n)==-1
• Test1. Mod(a^2-1.n)^((n-1)/2)==-1
• Test2. Mod(Mod(2*x,n),x^2-2*a*a+1)^((n+1)/2)==2*kronecker(a+1)

Interestingly counterexamples exist but only when gcd(z-1,r)==r or gcd(z-2,r)==r and r<z, where z is znorder(Mod(2,n)). This can be seen by running the following program:

{
forstep(n=3,1000000000,2,
if(!ispseudoprime(n)&&!issquare(n)&&Mod(2,n)^n==2,
z=znorder(Mod(2,n));forstep(r=1,z,2,
a=lift(Mod(2,n)^r);if(Mod(a^2-1,n)^((n-1)/2)==-1&&
Mod(Mod(2*x,n),x^2-2*a*x+1)^((n+1)/2)==2*kronecker(a+1,n),
print([n,z,r,gcd(z-1,r)==r||gcd(z-2,r)==r])))))
}

And the pattern breaks down for [n,z,r]=[16442311159, 3977337, 494917]