6
$\begingroup$

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}}$$

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

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.