5
$\begingroup$

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<b^n$ 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} $$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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}.$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ My implementation of the test gives correct result. See here $\endgroup$
    – Pedja
    Commented May 26, 2020 at 17:23
  • $\begingroup$ 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. $\endgroup$
    – Pedja
    Commented May 26, 2020 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .