This question is closely related to my previous question .
Can you provide a proof or a counterexample for the following claim :
Let $n$ be a natural number , $n>1$ and $n \not\in \{4,8,9\}$ . Then $n$ is prime if and only if
$\displaystyle\sum_{k=1}^{n}\left(2^k+1\right)^{n-1} \equiv n \pmod{2^n-1}$
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,lift(Mod(2^k+1,2^n-1)^(n-1)));
if((Mod(s,2^n-1)==n),print("n="n)))
}
CE2(n1,n2)=
{
forprime(n=n1,n2,
s=sum(k=1,n,lift(Mod(2^k+1,2^n-1)^(n-1)));
if(!(Mod(s,2^n-1)==n),print("n="n)))
}
I've tested this claim up to 10000 and there were no counterexamples .
Remark
More generally we can formulate the following criterion :
Let $b$ and $n$ be a natural numbers , $b\geq 2$ , $n>1$ and $n \not\in \{4,8,9\}$ . Then $n$ is prime if and only if
$\displaystyle\sum_{k=1}^{n}\left(b^k+1\right)^{n-1} \equiv n \pmod{\frac{b^n-1}{b-1}}$
This is a partial answer.
This answer proves that if $n$ is a prime and $b\ge 2$ is an integer, then $$\displaystyle\sum_{k=1}^{n}\left(b^k+1\right)^{n-1} \equiv n \pmod{\frac{b^n-1}{b-1}}$$
Proof : (This proof is similar to the one in this answer to your previous question.)
For $n=2$, we have $$\displaystyle\sum_{k=1}^{2}\left(b^k+1\right)\equiv (b+1)+(b^2+1)\equiv (b+1)^2-2(b+1)+2 \equiv 2 \pmod{b+1}$$
In the following, $n$ is an odd prime.
Let $N:=\frac{b^n-1}{b-1}$.
By the binomial theorem, $$\begin{align}\displaystyle\sum_{k=1}^{n}\left(b^k+1\right)^{n-1}&=\sum_{k=1}^n\sum_{j=0}^{n-1}\binom{n-1}{j}(b^k)^{j}\cdot 1^{n-1-j}\\\\&=\sum_{j=0}^{n-1}\sum_{k=1}^n\binom{n-1}{j}(b^k)^{j}\\\\&=\sum_{k=1}^n\binom{n-1}{0}(b^k)^{0}+\sum_{j=1}^{n-1}\sum_{k=1}^n\binom{n-1}{j}(b^k)^{j}\\\\&=n+\sum_{j=1}^{n-1}\sum_{k=1}^n\binom{n-1}{j}(b^k)^{j}\\\\&=n+\sum_{j=1}^{n-1}\binom{n-1}{j}\sum_{k=1}^n(b^j)^{k}\tag1\end{align}$$ By the way, $$\sum_{k=1}^n(b^j)^{k}=\frac{(b^{n+1})^j-b^j}{b^j-1}=\frac{(b(b-1)N+b)^j-b^j}{b^j-1}\tag2$$ By the binomial theorem, $$\begin{align}(2)&=\frac{\left(\displaystyle\sum_{m=0}^{j}\binom{j}{m}(b(b-1)N)^{m}b^{j-m}\right)-b^j}{b^j-1}\\\\&=\frac{\left(\displaystyle\sum_{m=1}^{j}\binom{j}{m}(b(b-1)N)^{m}b^{j-m}\right)+b^j-b^j}{b^j-1}\\\\&=\frac{b^jN}{b^j-1}\sum_{m=1}^{j}\binom jm(b-1)^mN^{m-1}\tag3\end{align}$$
Note here that $\gcd(b^j,b^{j}-1)=1$.
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 can be seen at the end of this answer.)
Case 1 : When $\gcd(N,b^j-1)=n$ with $b\equiv 1\pmod n$,
$$\begin{align}(3)&=\frac{b^jN}{(b-1)(b^{j-1}+b^{j-2}+\cdots +b+1)}\sum_{m=1}^{j}\binom jm(b-1)^mN^{m-1}\\\\&=\frac{b^jN}{b^{j-1}+b^{j-2}+\cdots +b+1}\sum_{m=1}^{j}\binom jm(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 jm(b-1)^mN^{m-1}=\frac{1}{b^{j-1}+b^{j-2}+\cdots +b+1}\sum_{m=1}^{j}\binom jm(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 jm(b-1)^mN^{m-1}$$ is an integer.
So, in either case, we have $$(3)\equiv 0\pmod N\tag4$$
Therefore, from $(1)(2)(3)(4)$, we have $$\begin{align}(1)&\equiv n+\sum_{j=1}^{n-1}\binom{n-1}{j}\cdot 0\qquad\pmod N\\\\&\equiv n\qquad \pmod N\qquad \blacksquare\end{align}$$