Q:

Primality test for $N=2^a3^b+1$

Can you prove or disprove the following claim:

Let $N=2^a3^b+1$ , $a>0 , b>0$ .  If there exists an integer $c$ such that $$c^{(N-1)/3}-c^{(N-1)/6} \equiv -1 \pmod{N}$$ then $N$ is a prime. 

You can run this test here.  I have verified this claim for all composite $N$ up to $2^{100} \cdot 3^{100}+1$ with $2 \le c \le 100$ , and for all prime $N$ from this list. 

A:

Yes.  Obviously this $c$ and $N$ are coprime.  We get $c^{(N-1)/2}+1=(c^{(N-1)/6}+1)(c^{(N-1)/3}-c^{(N-1)/6}+1)$ is divisible by $N$. Therefore $c^{N-1}-1$ is divisible by $N$, and $N-1$ is divisible by $k:={\rm {ord}}(c)$, where ${\rm ord}(x)$ denotes the multiplicative order of $x$ modulo $N$. But $(N-1)/2$ is not divisible by $k$, since $c^{(N-1)/2}\equiv -1\pmod N$. Assume that $(N-1)/3$ is divisible by $k$; then $c^{(N-1)/3}\equiv 1 \pmod N$, $c^{(N-1)/6}\equiv c^{(N-1)/3}+1\equiv 2 \pmod N$ and $$1\equiv c^{(N-1)/3}= (c^{(N-1)/6})^2\equiv 4\pmod N,$$
a contradiction.  So neither $(N-1)/2$ nor $(N-1)/3$ is divisible by $k$; thus, $k=N-1$. But $k$ must divide $\varphi(N)$, so $N-1\leqslant \varphi(N)$ and $N$ is prime.