# Conjecture: $n>2$ is prime iff $\sum_{k=1}^{n-1}\left(3^k-2\right)^{n-1} \;\equiv\; n \cdot 2^{n-1}-1 \pmod{\frac{3^n-1}{2}}$

This question is closely related to: Conjectured primality test

Can you provide a proof or a counterexample for the following claim :

Conjecture. Let $$n$$ be a natural number greater than $$2$$. Then $$n$$ is prime if and only if

$$\sum_{k=1}^{n-1}\left(3^k-2\right)^{n-1} \;\equiv\; n \cdot 2^{n-1}-1 \pmod{\frac{3^n-1}{2}}$$

You can run this test here.

I was searching for a counterexample using the following two PARI/GP programs :

CE1(n1,n2)=
{
forcomposite(n=n1,n2,
s=sum(k=1,n-1,lift(Mod(3^k-2,(3^n-1)/2)^(n-1)));
if((Mod(s,(3^n-1)/2)==n*2^(n-1)-1),print("n="n)))
}
CE2(n1,n2)=
{
forprime(n=n1,n2,
s=sum(k=1,n-1,lift(Mod(3^k-2,(3^n-1)/2)^(n-1)));
if(!(Mod(s,(3^n-1)/2)==n*2^(n-1)-1),print("n="n)))
}


REMARK

More generally we can formulate the following criterion :

Let $$b$$ , $$a$$ and $$n$$ be a natural numbers, $$b>a\geq 1$$, $$n>2$$ and $$n \not\in \{4,8,9\}$$. Then $$n$$ is prime if and only if $$\displaystyle\sum_{k=1}^{n}\left(b^k\pm a\right)^{n-1} \equiv n \cdot a^{n-1} \pmod{\frac{b^n-1}{b-1}}$$

• To how high a value of $n$ is it known to hold? – Oscar Lanzi Feb 2 at 10:50
• @OscarLanzi For all $n$ up to $5000$. – Peđa Terzić Feb 2 at 12:54