# Congruence satisfied by primes and only by primes

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

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

$$\displaystyle\prod_{k=1}^{n-1}\left(3^k+2\right) \equiv \frac{2^n+1}{3} \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,
if((Mod(prod(k=1,n-1,3^k+2),(3^n-1)/2)==(2^n+1)/3),print("n="n)))
}


CE2(n1,n2)=
{
forprime(n=n1,n2,
if(!(Mod(prod(k=1,n-1,3^k+2),(3^n-1)/2)==(2^n+1)/3),print("n="n)))
}

• How did you come up with this? – Mastrem Oct 8 '17 at 19:30
• @Mastrem This claim is similar to the Vantieghem's theorem – Peđa Terzić Oct 9 '17 at 7:27

This is only a partial answer, proving that the congruence holds for all odd primes. The beginnings of a proof that the congruence doesn't hold for odd composite $n$ is there as wellm but I'm still working on it. Throughout this 'proof', I will use results from Vanthieghem's paper. The proof I give is basically a modified version of Vanthieghem's proof.
First, a result from the paper (Corollary of Lemma 1), namely a congruence in $\Bbb{Z}[X,Y]$. For all $n\in\mathbb{Z}_{\ge 1}$, we have: $$\prod_{j=1}^{n-1}(X-Y^j)\equiv\sum_{i=0}^{n-1}X^i\pmod{\Phi_n(Y)}$$ Put $X=-2$ and $Y=3$ and suppose that $n$ is prime. This means that $$\Phi_n(Y)=\frac{Y^n-1}{Y-1}$$ and therefore: \begin{align*} \prod_{j=1}^{n-1}(-2-3^j)&\equiv\sum_{i=0}^{n-1}(-2)^i\equiv \frac{(-1)^{n-1}2^n+1}{3}\pmod{\frac{3^n-1}{2}} \end{align*} Multiplyinh both sides by $(-1)^{n-1}$ yields: $$\prod_{j=1}^{n-1}(3^j+2)\equiv\frac{2^n+(-1)^{n-1}}{3}\pmod{\frac{3^n-1}{2}}$$ For odd primes, this is the congruence you give. And since all primes greater than $2$ are odd, we've proven that the congruence holds if $n$ prime and $n>2$.
That was the easy part. Now, we have to prove that the congruence doesn't hold if $n>2$ and $n$ composite.
Suppose $n$ is composite. Let $c$ be a proper divisor of $n$ and write $d=n/c$. Now, if the congruence holds, we have after multiplication by $3$: $$\prod_{i=0}^{n-1}(3^i+2)\equiv \prod_{j=0}^{c-1}\left(\prod_{k=0}^{d-1}(3^{jd+k}+2)\right)\equiv2^n+1\pmod{\frac{3^n-1}{2}}$$ Now, take the identity $$X^n-1=\prod_{d\mid n}\Phi_d(X)$$ We put $X=3$ and since $d\neq 1$ and $\Phi_1(3)=2$, we have $\Phi_d(3)\mid\frac{3^n-1}{2}$, so the above congruence also holds modulo $\Phi_d(3)$. The identity also gives $\Phi_d(3)\mid 3^d-1$, so $3^d\equiv 1\pmod{\Phi_d(3)}$. Hence, for all integer $0\le j\le c-1$: $$\prod_{k=0}^{d-1}(3^{jd+k}+2)\equiv \prod_{j=0}^{d-1}(3^k+2)\pmod{\Phi_d(3)}$$ Now, another congruence in Vanthieghem's paper (Lemma 1) is that for every integer $n>0$ we have: $$\prod_{j=0}^{n-1}(X-Y^j)\equiv X^n-1\pmod{\Phi_n(Y)}$$ Putting $n=d$, $X=-2$ and $Y=3$ gives after a sign change $$\prod_{j=0}^{d-1}(3^j+2)\equiv -(-2)^d+1\pmod{\Phi_d(3)}$$ Putting those last three congruences together yields: \begin{align*} 2^n+1&\equiv\prod_{j=0}^{c-1}\left(\prod_{k=0}^{d-1}(3^{jd+k}+2)\right)\\ &\equiv\prod_{j=0}^{c-1}\left(\prod_{k=0}^{d-1}(3^k+2)\right)\\ &\equiv\prod_{j=0}^{c-1}(-(-2)^d+1)\\ &\equiv (-(-2)^d+1)^c\pmod{\Phi_d(3)} \end{align*} Suppose that $n$ is odd, this means that both $d$ is odd as well and therefore: $$2^n+1\equiv(2^d+1)^c\pmod{\Phi_d(3)}$$ Here, I'm stuck (for now)