Conjeturó primalidad de la prueba II

Question

Esta cuestión está estrechamente relacionada con mi pregunta anterior .

Puede usted dar una prueba o un contraejemplo para la siguiente aseveración :

Deje $n$ ser un número natural , $n>1$$n \not\in \{4,8,9\}$ . A continuación, $n$ es primo si y sólo si

$\displaystyle\sum_{k=1}^{n}\left(2^k+1\right)^{n-1} \equiv n \pmod{2^n-1}$

Puede ejecutar esta prueba aquí .

Yo estaba buscando un contraejemplo mediante las siguientes dos PARI/GP programas :

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

He probado esta reclamación hasta 10000 y no hubo contraejemplos .

Comentario

Más generalmente, se puede formular el siguiente criterio :

Deje $b$ $n$ ser números naturales , $b\geq 2$ , $n>1$ y $n \not\in \{4,8,9\}$ . A continuación, $n$ es primo si y sólo si

$\displaystyle\sum_{k=1}^{n}\left(b^k+1\right)^{n-1} \equiv n \pmod{\frac{b^n-1}{b-1}}$

Answer 1

Esta es una respuesta parcial.

Esta respuesta demuestra que, si $n$ es un primer e $b\ge 2$ es un número entero, entonces $$\displaystyle\sum_{k=1}^{n}\left(b^k+1\right)^{n-1} \equiv n \pmod{\frac{b^n-1}{b-1}}$$

Prueba : (Esta prueba es similar a la que en esta respuesta a su pregunta anterior.)

Para $n=2$, tenemos $$\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}$$

En la siguiente, $n$ es una extraña prime.

Deje $N:=\frac{b^n-1}{b-1}$.

Por el teorema del binomio, $$\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}$$ Por el camino, $$\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$$ Por el teorema del binomio, $$\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}$$

Tenga en cuenta que $\gcd(b^j,b^{j}-1)=1$.

Ahora, utilizamos el si $n$ es un extraño primo, entonces cualquiera de las $\gcd(N,b^j-1)=n$ $b\equiv 1\pmod n$ o $\gcd(N,b^j-1)=1$ mantiene para $1\le j\le n-1$. (La prueba se puede ver al final de esta respuesta.)

Caso 1 : Cuando el $\gcd(N,b^j-1)=n$$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}$$ Ahora, desde la $b^{j-1}+b^{j-2}+\cdots +b+1\equiv j\not\equiv 0\pmod n$, $$\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}$$ es un número entero.

Caso 2 : Cuando el $\gcd(N,b^j-1)=1$, $$\frac{1}{b^j-1}\sum_{m=1}^{j}\binom jm(b-1)^mN^{m-1}$ $ es un número entero.

Así que, en cualquier caso, hemos $$(3)\equiv 0\pmod N\tag4$$

Por lo tanto, de $(1)(2)(3)(4)$, tenemos $$\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}$$