Can you provide a proof or a counterexample for the following claim :
Let $n$ be a natural number , $n>2$ and $n \neq 9$ . Then $n$ is prime if and only if
$\displaystyle\sum_{k=1}^{n-1}\left(2^k-1\right)^{n-1} \equiv n \pmod{2^n-1}$
You can run this test here .
GUI application that implements this algorithm can be found here .
Android app that implements this algorithm can be found here .
I was searching for a counterexample using the following two PARI/GP programs :
CE1(n1,n2)=
{
forcomposite(n=n1,n2,
if((Mod(sum(k=1,n-1,(2^k-1)^(n-1)),2^n-1)==n),print("n="n)))
}
CE2(n1,n2)=
{
forprime(n=n1,n2,
if(!(Mod(sum(k=1,n-1,(2^k-1)^(n-1)),2^n-1)==n),print("n="n)))
}
Remark
More generally we can formulate the following criterion :
Let $b$ and $n$ be a natural numbers , $b\geq 2$ , $n>2$ and $n \neq 9$ . Then $n$ is prime if and only if
$\displaystyle\sum_{k=1}^{n-1}\left(b^k-1\right)^{n-1} \equiv n \pmod{\frac{b^n-1}{b-1}}$
EDIT
Improved PARI/GP programs for counterexample search :
CE1(b,n1,n2)=
{
forcomposite(n=n1,n2,
s=sum(k=1,n-1,lift(Mod(b^k-1,(b^n-1)/(b-1))^(n-1)));
if((Mod(s,(b^n-1)/(b-1))==n),print("n="n)))
}
CE2(b,n1,n2)=
{
forprime(n=n1,n2,
s=sum(k=1,n-1,lift(Mod(b^k-1,(b^n-1)/(b-1))^(n-1)));
if(!(Mod(s,(b^n-1)/(b-1))==n),print("n="n)))
}
Best Answer
This is a partial answer.
This answer proves that if $n$ is an odd prime and $b\ge 2$ is an integer, then $$\sum_{k=1}^{n-1}\left(b^k-1\right)^{n-1}\equiv n \pmod{\frac{b^n-1}{b-1}}$$ Proof :
Let $N:=\frac{b^n-1}{b-1}$.
By the binomial theorem, $$\begin{align}\sum_{k=1}^{n-1}\left(b^k-1\right)^{n-1}&=\sum_{k=1}^{n-1}\sum_{j=0}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=\sum_{j=0}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=\sum_{k=1}^{n-1}\binom{n-1}{0}(b^k)^{0}(-1)^{n-1-0}+\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=(n-1)\cdot (-1)^{n-1}+\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\tag1\end{align}$$
Since $n$ is an odd prime, we have $(-1)^{n-1}=1$, so
$$\begin{align}(1)&=n-1+\sum_{j=1}^{n-1}\sum_{k=1}^{n-1}\binom{n-1}{j}(b^k)^{j}(-1)^{n-1-j}\\\\&=n-1+\sum_{j=1}^{n-1}\binom{n-1}{j}(-1)^{n-1-j}\sum_{k=1}^{n-1}(b^j)^{k}\tag2\end{align}$$
By the way,
$$\sum_{k=1}^{n-1}(b^j)^{k}=\frac{(b^n)^{j}-b^j}{b^j-1}=\frac{((b-1)N+1)^j-b^j}{b^j-1}\tag3$$ By the binomial thorem, $$\begin{align}(3)&=\frac{\left(\displaystyle\sum_{m=0}^{j}\binom{j}{m}(b-1)^mN^m\right)-b^j}{b^j-1}\\\\&=\frac{\left(\displaystyle\sum_{m=1}^{j}\binom{j}{m}(b-1)^mN^m\right)+1-b^j}{b^j-1}\\\\&=\frac{1-b^j}{b^j-1}+\frac{\displaystyle\sum_{m=1}^{j}\binom{j}{m}(b-1)^mN^m}{b^j-1}\\\\&=-1+\frac{\displaystyle\sum_{m=1}^{j}\binom{j}{m}(b-1)^mN^m}{b^j-1}\\\\&=-1+\frac{N}{b^j-1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}\tag4\end{align}$$
Now, we use that if $n$ is an odd prime, then either $\gcd(N,b^j-1)=n$ and $b\equiv 1\pmod n$ or $\gcd(N,b^j-1)=1$ holds for $1\le j\le n-1$. (The proof is written at the end of this answer.)
Case 1 : When $\gcd(N,b^j-1)=n$ with $b\equiv 1\pmod n$, $$\begin{align}(4)&=-1+\frac{N}{(b-1)(b^{j-1}+b^{j-2}+\cdots +b+1)}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}\\\\&=-1+\frac{N}{b^{j-1}+b^{j-2}+\cdots +b+1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m-1}N^{m-1}\end{align}$$ Now, since $b^{j-1}+b^{j-2}+\cdots +b+1\equiv j\not\equiv 0\pmod n$, we have that $$\frac{1}{b^j-1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}=\frac{1}{b^{j-1}+b^{j-2}+\cdots +b+1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m-1}N^{m-1}$$ is an integer.
Case 2 : When $\gcd(N,b^j-1)=1$, we have that $$\frac{1}{b^j-1}\sum_{m=1}^{j}\binom{j}{m}(b-1)^{m}N^{m-1}$$ is an integer.
So, in either case, we have $$(4)\equiv -1\pmod N\tag5$$
Therefore, from $(1)(2)(3)(4)(5)$, we have $$\begin{align}(1)&\equiv n-1-\sum_{j=1}^{n-1}\binom{n-1}{j}(-1)^{n-1-j}\qquad\pmod{N}\\\\&\equiv n-\sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^{n-1-j}\cdot 1^j\qquad\pmod{N}\\\\&\equiv n-(1-1)^{j}\qquad \pmod{N}\\\\&\equiv n\qquad\pmod{N}\qquad\blacksquare\end{align}$$
Finally, let us prove that if $n$ is an odd prime and $b\ge 2$ is an integer, then either $\gcd(N,b^j-1)=n$ and $b\equiv 1\pmod n$ or $\gcd(N,b^j-1)=1$ holds for $1\le j\le n-1$ where $N=\frac{b^n-1}{b-1}$.
Proof :
Let $D=\gcd(N,b^j-1)$. Then, we have $b^n\equiv 1\pmod D$ and $b^j\equiv 1\pmod D$. Let $s$ be the smallest $t$ such that $b^t\equiv 1\pmod D$. There exist non-negative integers $u,r$ such that $n=us+r$ with $0\le r\lt s$. Then, $$1\equiv b^n=b^{us}\cdot b^r=(b^s)^u\cdot b^r\equiv b^r\implies r=0$$ So, $n=us$. Similarly, there exists a non-negative integer $v$ such that $j=vs$. Since $\gcd(n,j)=1$, we have $s=1$ and $b\equiv 1\pmod D$.
Now, $$0\equiv N=\frac{b^n-1}{b-1}=b^{n-1}+b^{n-2}+\cdots +b+1\equiv n\pmod D$$ from which we have $D=1$ or $D=n$.$\qquad\blacksquare$