# Conjectured primality test for specific class of $N=k \cdot 6^n+1$

Can you provide a proof or a counterexample for the claim given below?

Inspired by Theorem 5 in this paper I have formulated the following claim:

Let $$N=k \cdot 6^n+1$$ , $$k<6^n$$ and $$\operatorname{gcd}(k,6)=1$$. Assume that $$a \in \mathbb{Z}$$ is a 6-th power non-residue . Let $$\Phi_n(x)$$ be the n-th cyclotomic polynomial, then:

$$N \text{ is a prime iff } \Phi_2\left(a^{\frac{N-1}{2}}\right)\cdot \Phi_3\left(a^{\frac{N-1}{3}}\right) \equiv 0 \pmod{N}$$

You can run this test here. I have tested this claim for many random values of $$k$$ and $$n$$ and there were no counterexamples .

Test implementation in PARI/GP without directly computing cyclotomic polynomials.

EDIT

More generally we can formulate the following claim:

Let $$N=k \cdot (p \cdot q)^n+1$$ , where $$p$$ and $$q$$ are distinct prime numbers, $$k<(p \cdot q)^n$$ and $$\operatorname{gcd}(k,p\cdot q)=1$$. Assume that $$a \in \mathbb{Z}$$ is a $$p \cdot q$$-th power non-residue . Let $$\Phi_n(x)$$ be the n-th cyclotomic polynomial, then:

$$N \text{ is a prime iff } \Phi_p\left(a^{\frac{N-1}{p}}\right)\cdot \Phi_q\left(a^{\frac{N-1}{q}}\right) \equiv 0 \pmod{N}$$

You can run this test here.

Test implementation in PARI/GP without directly computing cyclotomic polynomials.

EDIT 2

It seems that this claim can be generalized even further:

Let $$N=k \cdot b^n+1$$ , $$k and $$\operatorname{gcd}(k,b)=1$$. Let $$p_1,p_2,\ldots,p_n$$ be a distinct prime factors of $$b$$. Assume that $$a \in \mathbb{Z}$$ is a $$p_1\cdot p_2\cdot \ldots \cdot p_n$$-th power non-residue . Let $$\Phi_n(x)$$ be the n-th cyclotomic polynomial, then: $$N \text{ is a prime iff } \Phi_{p_1}\left(a^{\frac{N-1}{p_1}}\right)\cdot \Phi_{p_2}\left(a^{\frac{N-1}{p_2}}\right)\cdot \ldots \cdot \Phi_{p_n}\left(a^{\frac{N-1}{p_n}}\right) \equiv 0 \pmod{N}$$

In one direction (wnen $$N$$ is prime) the statement is trivial. In the reverse direction, it's false however.
Here is just one counterexample: $$n=4$$, $$k=133$$, and $$a=11$$ with $$N=172369=97\cdot 1777$$, where we already have $$\Phi_2(11^{\frac{172369-1}2})\equiv 0\pmod{172369}.$$
• If we use $a=2$ test returns "Composite" for this combination of $k$ and $n$. On the other hand $11$ is 6-th power non-residue so you are right. Maybe, I should add some additional constraints to the claim. Thank you for investigation. May 26 '20 at 17:25