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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ My implementation of the test gives correct result. See here $\endgroup$ – Peđa Terzić May 26 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$ – Peđa Terzić May 26 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.