View Single Post
Old 2020-01-18, 20:51   #1
carpetpool's Avatar
Nov 2016

32610 Posts
Post Counterexample to test ?

Is anyone able to come up with a counterexample to the following test? I'm sure there are some, I just can't construct any. Please let me know.

Define a(n) (case where b=1 see below) to be

Let n = 2 mod 3 and Jacobi(13 | n) = -1. If a(n^2+1) = 0 mod n, then n is prime.

In general, there should be an integer b such that

Jacobi([4*b-7] | n) = -1 and Jacobi([b^2+4*b+8] | n) = -1 and a similar test would apply. This stems from the discriminant of the characteristic polynomial: x^4 + x^3 - b*x^2 - x + 1. This polynomial has discriminant (4*a - 7)^2*(a^2 + 4*a + 8).

The reasoning for the above test is similar to that of Fermat's Little Theorem. If n is prime and:

n = 1 mod 3, then a(n-1) divides n.
n = 2 mod 3 and J(13 | n)=1, then a(n+1) divides n.
n = 2 mod 3 and J(13 | n)=-1, then a(n^2+1) divides n.

The first two conditions, counterexamples are easily construable. But the third is a little difficult. Here's how to construct one (if they exists):

We all know the properties of Carmichael numbers: p-1 | N-1 for all primes p | N. And then there is something similar for other numbers N, which is that p+1 | N+1 for all primes p | N. And finally we look at integers N such that p^2+1 | N^2+1 for all primes p | N. While I have been able to verify that if N > 10^9 if such an N exists, I have not been able to prove that they exist. I imagine they would be very difficult to construct, but still possible. So if someone is able to prove that they do NOT exist at all, then the test is proved. Otherwise, it will remain a theoretical PRP test.
carpetpool is offline   Reply With Quote