Conjectured primality test

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

• @Vincent: note that my tries were anything but systematic, I made about 10 or 15 tries but didn't prove that it always works. – Evargalo Jun 19 '17 at 9:20
• When n is prime, n-1 is the Euler totient number for the prime. Therefore, the product is taken as k runs through all comprimes less than the prime. The modulus will always be true for primes. – Fred Kline Jun 19 '17 at 10:17
• nice, but it is not practically usable because of its exponential storage and running rime. – miracle173 Jun 19 '17 at 14:37
• @FredKline I'm not seeing it; I am assuming by "product" you are referring to the sum, but I don't know of any results relating the totient function working mod $2^n-1$ – alphacapture Jun 20 '17 at 20:41
• Not sure how far others have tested, but I've tested up to around 5400 and there were no other counterexamples other than 2 and 9. – Wojowu Jun 23 '17 at 17:32

2 Answers

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$

Just a remark which is a little long for a comment:

If we forget about the two and also about the generalization to other numbers for a second and look at polynomials instead, i.e. consider the polynomial $$p_n(x) := \sum_{k=1}^{n-1} (x^k-1)^{n-1}$$ and then reduce this modulo $x^n-1$, the reduced polynomials for $p_n$ when $n$ is prime have a very nice form, namely: $$p_n(x) \equiv n - \sum_{i=0}^{n-1} x^i \mod{x^n-1}.$$ Now it is clear that if we input $2$ (or $b$), the sum will exactly be $2^n-1$ resp $\frac{b^n-1}{b-1}$, so we get $n$ as claimed.

This is, unfortunately, not yet a proof for your claim, but it suggests that there is an even stronger structure behind it, that goes beyond natural numbers. Note that the polynomial $p_9$ does not have this nice structure, meaning that this strange case could be excluded when viewing it in the polynomial world.