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 :


  • $\begingroup$ How did you come up with this? $\endgroup$ – Mastrem Oct 8 '17 at 19:30
  • $\begingroup$ @Mastrem This claim is similar to the Vantieghem's theorem $\endgroup$ – 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)

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.