31
$\begingroup$

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)))
}
$\endgroup$
  • 3
    $\begingroup$ @Vincent: note that my tries were anything but systematic, I made about 10 or 15 tries but didn't prove that it always works. $\endgroup$ – Evargalo Jun 19 '17 at 9:20
  • 4
    $\begingroup$ 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. $\endgroup$ – Fred Kline Jun 19 '17 at 10:17
  • 3
    $\begingroup$ nice, but it is not practically usable because of its exponential storage and running rime. $\endgroup$ – miracle173 Jun 19 '17 at 14:37
  • 3
    $\begingroup$ @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$ $\endgroup$ – alphacapture Jun 20 '17 at 20:41
  • 3
    $\begingroup$ 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. $\endgroup$ – Wojowu Jun 23 '17 at 17:32
12
+100
$\begingroup$

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$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.