Test de primalidad conjetural

Question

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

Deje $n$ ser un número natural , $n>2$$n \neq 9$ . A continuación, $n$ es primo si y sólo si

$\displaystyle\sum_{k=1}^{n-1}\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,
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))) 
}

Comentario

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

Deje $b$ $n$ ser números naturales , $b\geq 2$ , $n>2$ y $n \neq 9$ . A continuación, $n$ es primo si y sólo si

$\displaystyle\sum_{k=1}^{n-1}\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 una extraña primer y $b\ge 2$ es un número entero, entonces $$\sum_{k=1}^{n-1}\left(b^k-1\right)^{n-1}\equiv n \pmod{\frac{b^n-1}{b-1}}$$ Prueba :

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

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

Desde $n$ es una extraña prime, tenemos $(-1)^{n-1}=1$, por lo que

$$\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}$$

Por el camino,

$$\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$$ Por el binomio 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}$$

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 está escrito al final de esta respuesta.)

Caso 1 : Cuando el $\gcd(N,b^j-1)=n$$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}$$ 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{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}$$ es un número entero.

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

Así que, en cualquier caso, hemos $$(4)\equiv -1\pmod N\tag5$$

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

---

Por último, vamos a demostrar que si $n$ es una extraña primer y $b\ge 2$ es un número entero, 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$ donde $N=\frac{b^n-1}{b-1}$.

Prueba :

Deje $D=\gcd(N,b^j-1)$. Entonces, tenemos $b^n\equiv 1\pmod D$$b^j\equiv 1\pmod D$. Deje $s$ ser el más pequeño $t$ tal que $b^t\equiv 1\pmod D$. Existen enteros no negativos $u,r$ tal que $n=us+r$$0\le r\lt s$. A continuación, $$1\equiv b^n=b^{us}\cdot b^r=(b^s)^u\cdot b^r\equiv b^r\implies r=0$$ Por eso, $n=us$. Asimismo, existe un entero no negativo, $v$ tal que $j=vs$. Desde $\gcd(n,j)=1$,$s=1$$b\equiv 1\pmod D$.

Ahora, $$0\equiv N=\frac{b^n-1}{b-1}=b^{n-1}+b^{n-2}+\cdots +b+1\equiv n\pmod D$$ a partir de la cual hemos $D=1$ o $D=n$.$\qquad\blacksquare$