Go Back > Extra Stuff > Blogorrhea > carpetpool

Thread Tools
Old 2020-01-18, 20:51   #1
carpetpool's Avatar
Nov 2016

52·13 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
Old 2020-01-19, 16:21   #2
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

23·7·89 Posts

Originally Posted by carpetpool View Post
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
This paper may be pertinent regarding the existence of counterexamples. In particular, it proves that there are Carmichael numbers composed entirely of primes p for which the given polynomial (mod p) splits into linear factors.

See also this paper.

Looking at the OEIS entry, I asked myself, "Why is this a divisibility sequence?"

The characteristic polynomial f = x^4 - x^3 - x^2 - x + 1 for the recurrence is a quartic with Galois group D4 (the dihedral group with 8 elements, AKA the "group of the square").

I knew that the sequence could be expressed in the form a(k) = trace(y*x^k) where y = Mod(p, f), with p a nonzero polynomial in x of degree less than 4.

Luckily, I know how to compute y. And what the computation showed was that for the given sequence, y^2 - 13 = 0. I'm sure that this is the key to the sequence being a divisibility sequence, but I'm too lazy to work out the details.

The field k1 = Q(sqrt(13)) is a subfield of the splitting field K of f; K/Q has degree 8. Also, f splits into two quadratic factors in k1[x], so K is a four-group extension of k1.

The splitting field K has two other quadratic subfields, k2 = Q(sqrt(-39)) and k3 = Q(sqrt(-3)). The polynomial f remains irreducible in k2[x] and k3[x], so K is a cyclic quartic extension of k2 and k3.

The field k3 is also the field of cube roots of unity.

The extension K/k2 is interesting because the class group of k2 is cyclic of order 4, and K is the Hilbert Class Field of k2.
Dr Sardonicus is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
Will the torture test, test ALL available memory? swinster Software 2 2007-12-01 17:54
A counterexample-anyone-II devarajkandadai Miscellaneous Math 3 2005-12-12 16:04
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 20:40.

Wed Oct 20 20:40:34 UTC 2021 up 89 days, 15:09, 1 user, load averages: 1.55, 1.33, 1.30

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.