3
$\begingroup$

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)))
} 
$\endgroup$
  • $\begingroup$ No counterexample upto $n=10^4$ $\endgroup$ – Peter Feb 1 at 8:02
  • 1
    $\begingroup$ 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$ $\endgroup$ – reuns Feb 5 at 2:03
  • 1
    $\begingroup$ How did you motivate/come up with this congruence? $\endgroup$ – YiFan Feb 5 at 3:21
  • 2
    $\begingroup$ @YiFan This claim was inspired by Vantieghems theorem $\endgroup$ – Peđa Terzić Feb 5 at 17:46
  • $\begingroup$ parforprime and Mod each term of the product may help. $\endgroup$ – Roddy MacPhee May 3 at 17:36

Your Answer

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

Browse other questions tagged or ask your own question.