# Congruence satisfied by primes and only by primes II

This question is closely related to: 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 and $$n \neq 4$$ . Then n is prime if and only if

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

• No counterexample upto $n=10^4$ – Peter Feb 1 at 8:02
• If $n$ is prime, $N=\frac{3^n-1}{2}$ is square-free and odd $=\prod_j p_j$, then $n = ord(3 \bmod N)$, let $r_j = order(3 \bmod p_j)$, $r_j \ne 1$ and $r_j |n$ so $r_j = n$, then $\prod_{k=1}^{n-1} (3^k-2) \equiv (-1)^{n+1}\prod_{k=1}^n (2-3^k) \equiv 2^n-1 \bmod p_j$, since this is true for every $p_j$ then $\prod_{k=1}^{n-1} (3^k-2) \equiv 2^n-1 \bmod N$. If $n$ is not prime it becomes $\prod_{k=1}^{n-1} (3^k-2) \equiv (2^{r_j}-1)^{n/r_j} \bmod p_j$ so $\prod_{k=1}^{n-1} (3^k-2) \equiv \sum_j \frac{N}{p_j}b_j (2^{r_j}-1)^{n/r_j} \bmod N$ where $\frac{N}{p_j} b_j\equiv 1 \bmod p_j$ – reuns Feb 5 at 2:03
• How did you motivate/come up with this congruence? – YiFan Feb 5 at 3:21
• @YiFan This claim was inspired by Vantieghems theorem – Peđa Terzić Feb 5 at 17:46
• parforprime and Mod each term of the product may help. – Roddy MacPhee May 3 at 17:36