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


Inspired by Theorem 5 in [this paper](https://arxiv.org/pdf/1011.4836.pdf) 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](https://sagecell.sagemath.org/?z=eJxVjs1uwyAQhO88Bclp16VywFIulFOOUa3eo1giBkfIGCxMDm3Vdy_uT6redr6dmd26okdrZxroMmnvKTzxHdKqJqMSjSRBCUlaNVb7LjxwSbyeLkZDQPUWlqxTmU7ifOLnYo0h2cWZm4UW1btR197Anv0kWkQ5xARaCRYjcwOsa82KVfFVejdkeI7frIN7rDaIm2JJNt9SAI3ykqwesfR9EK3-XZWkFK0dc_T9a-8jCKY7gPaRYy0Qqztv_niD-PXFjs3JhQzbl-Qmu9nirz7EaY6LyytD-QkFmlsM&lang=gp&interacts=eJyLjgUAARUAuQ==). I have tested this claim for many random values of $k$ and $n$ and there were no counterexamples .


[Test implementation in PARI/GP](https://sagecell.sagemath.org/?z=eJx1jjFrAzEMhff7F8kkXV0Su5DFaOrcI3tIwKl9xThnB9u3NPS_V762gRY62DzpfU9SIKm72L6BQr87xQeWFzOdrYGI9B5LNZnVQR0P8shoitkVb2cHA9LN0turhZ34TgyIekwZDCmRkvAjNNsIRkm28uLHCi_pq3eCe2xjEVeMZFfnHMGgPmdnAvK8j87Qr626K5LKPEGgrZDiz8jQw_AocaNativqTqr_yKeF5OOa1V6R7PeLUqyW67fimn2ssN5nP7nVGn_q5zRdU_G19VB_AuxkYtM=&lang=gp&interacts=eJyLjgUAARUAuQ==) 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](https://sagecell.sagemath.org/?z=eJxVjk9PxCAQxe98CnZPMxXTpR6Rk0dj432zTdhCDSkFStmDGr-74J81XiYzb97vzbQNfTQmUk-3RTlH4Z4fkDYtmSUXxNcSZSfIKu8E6eXcQGxWHPxNWTi1nLUCj_LNb1ml0h2705GfChh8MpvVFwM9ynctX0ZdSfbD9IhiCgmU7FgIzE5QDYoVs-R1dHbK8BS-tQGuWKsRd8WSTL4kDwrFORk1Y8n7IEr-uytICaoZMbjxdXQBIlMDQH_LsY2IzVVf__QV8euLA4vJ-gz752QXs9vj7_wQlhg2m6uG4hMgy2AU&lang=gp&interacts=eJyLjgUAARUAuQ==).


[Test implementation in PARI/GP](https://sagecell.sagemath.org/?z=eJx1jz1vwyAQhnf-RTJxLlEKHdFNnWtljxKJFFwhx4ABL6n633u4baRW6gB67-5572NEqVloX0Kl2YxPmvU4djx1M5zDAxWuZrpYwwPgLZRqMqmjOh3liYwxZFe8XRzvAd8tvr3a5hTfnh5ADzFzg0rEKPzAG2AEwShbePVD5S_xK3fmd9veAmwIya4uOXAD-pKdGYH6fTCDv-ZqViSWZeIjPoq0k-JPUzqm30nYp-ZmRd3Z-X92XllasJXaK5Lq3aoUqfUCmpZ9qHx7yH5ymy38xM9xSrH42nKgPwFvFWjO&lang=gp&interacts=eJyLjgUAARUAuQ==) 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} $$
> 
> 
> 



Conjectured primality test for specific class of $N=k \cdot 6^n+1$
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}.$$


