Contraejemplo de la prueba de primalidad

Question

Se trata de una generalización de esta reclamación .

¿Puede dar un contraejemplo de la siguiente afirmación?

Dejemos que $n$ sea un número natural mayor que dos . Sea $r$ sea el menor número primo impar tal que $r \nmid n$ y $n^2 \not\equiv 1 \pmod r$ . Sea $P_n^{(a)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right)$ , donde $a$ es un número entero no nulo coprimo a $n$ . Entonces $n$ es un número primo si y sólo si $P_n^{(a)}(x) \equiv x^n \pmod {x^r-1,n}$ .

Puede realizar esta prueba aquí .

He probado esta afirmación para muchos valores aleatorios de $n$ y $a$ y no hubo contraejemplos .

EDITAR

Aplicación del algoritmo en PARI/GP sin computar directamente $P_n^{(a)}(x)$ .

He verificado esta afirmación para $n \in [3,100000]$ con $a \in [-100,100]$ .

Answer 1

La afirmación es cierta.

---

Es cierto que si $n$ es un número primo, entonces $P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$ .

Prueba :

Tenemos, por el teorema del binomio, $$\begin{align}P_n^{(a)}(x)&=\frac 12\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right) \\\\&=\frac 12\sum_{i=0}^{n}\binom nix^{n-i}\bigg(\bigg(-\sqrt{x^2+a}\bigg)^i+\bigg(\sqrt{x^2+a}\bigg)^i\bigg) \\\\&=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}x^{n-2j}(x^2+a)^j \\\\&=x^n+\sum_{j=1}^{(n-1)/2}\binom{n}{2j}x^{n-2j}(x^2+a)^j\end{align}$$ Desde $\binom nm\equiv 0\pmod n$ para $1\le m\le n-1$ existe un polinomio $f$ con coeficientes enteros tales que $$P_n^{(a)}(x)=x^n+0\times (x^r-1)+nf$$ de la cual $$P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$$ sigue. $\quad\blacksquare$

---

Es cierto que si $P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$ entonces $n$ es un número primo.

Prueba :

Supongamos que $n$ es un número par. Entonces, existe un polinomio $f$ con coeficientes enteros y un número entero $s$ tal que $$P_n^{(a)}(x)=\sum_{i=0}^{n/2}\binom{n}{2i}x^{n-2i}(x^2+a)^i=x^n+s(x^r-1)+nf$$ Considerando $[x^{n}]$ donde $[x^k]$ denota el coeficiente de $x^k$ en $P_n^{(a)}(x)$ obtenemos $$\sum_{i=0}^{n/2}\binom{n}{2i}\equiv 1\pmod n,$$ es decir $$2^{n-1}\equiv 1\pmod n$$ que es imposible.

Así que, $n$ tiene que ser un número impar.

Existe un polinomio $\displaystyle g=\sum_{i=0}^{n}a_ix^i$ donde $a_i$ son números enteros y un número entero $t$ tal que

$$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}(x^2+a)^j=x^n+t(x^r-1)+ng$$

Considerando $[x^0]$ tenemos $$0=-t+na_0\implies t=na_0$$ Así, vemos que existe un polinomio $h$ con coeficientes enteros tales que $$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}(x^2+a)^j=x^n+nh\tag1$$

De ello se desprende que $[x^k]\equiv 0\pmod n$ para todos $k$ tal que $0\le k\le n-1$ .

Ahora, $(1)$ puede escribirse como

$$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\sum_{k=0}^{j}\binom n{2j}\binom jkx^{n-2(j-k)}a^{j-k}=x^n+nh$$

Así, vemos que $$\begin{align}&[x^3]\equiv 0\pmod n \\\\&\implies \left(\binom n{n-3}\binom {(n-3)/2}0+\binom n{n-1}\binom {(n-1)/2}1\right)a^{(n-3)/2}\equiv 0\pmod n \\\\&\implies \binom n{n-3}\equiv 0\pmod n\end{align}$$ desde $\gcd(a,n)=1$ .

Además, tenemos $$\begin{align}&[x^5]\equiv 0\pmod n \\\\&\implies \bigg(\binom n{n-5}\binom {(n-5)/2}0+\binom n{n-3}\binom {(n-3)/2}1 \\&\qquad\qquad+\binom n{n-1}\binom {(n-1)/2}2\bigg)a^{(n-5)/2}\equiv 0\pmod n \\\\&\implies \binom n{n-5}\equiv 0\pmod n\end{align}$$ Así, podemos obtener (se puede demostrar por inducción) $$\begin{align}&[x^3]\equiv [x^5]\equiv [x^7]\equiv\cdots\equiv [x^{n-2}]\equiv 0\pmod n \\\\&\implies\binom n{n-3}\equiv\binom n{n-5}\equiv\binom n{n-7}\equiv\cdots\equiv\binom{n}{2}\equiv 0\pmod n \\\\&\implies\binom{n}{2}\equiv \binom{n}{3}\equiv \binom n4\cdots \equiv\binom n{n-2}\equiv 0\pmod n\tag2\end{align}$$

Supongamos que $\displaystyle n=\prod_{i=1}^mp_i^{b_i}$ es un número compuesto donde $p_1\lt p_2\lt\cdots\lt p_m$ son primos y $b_i$ son enteros positivos.

Dejemos que $[[N]]$ sea el número del factor primo $p_i$ en $N$ .

Entonces, tenemos lo siguiente :

• $[[1!]]=[[2!]]=\cdots =[[(p_i-1)!]]=0$

• $[[p_i!]]=1$

• $[[(n-1)!]]=[[(n-2)!]]=\cdots =[[(n-p_i)!]]$

Utilizando esto, vemos que $$\binom n1=\frac{n!}{1!(n-1)!}=n,\binom n2=\frac{n!}{2!(n-2)!},\cdots, \binom{n}{p_i-1}=\frac{n!}{(p_i-1)!(n-(p_i-1))!}$$ son divisibles por $p_i^{b_i}$ y que $$\binom n{p_i}=\frac{n!}{p_i!(n-p_i)!}$$ no es divisible por $p_i^{b_i}$ .

Por lo tanto, vemos que $$\binom n1=\frac{n!}{1!(n-1)!}=n,\binom n2=\frac{n!}{2!(n-2)!},\cdots, \binom{n}{p_1-1}=\frac{n!}{(p_1-1)!(n-(p_1-1))!}$$ son divisibles por $n$ y que $$\binom{n}{p_1}=\frac{n}{p_1!(n-p_1)!}$$ no es divisible por $n$ que se contradice con $(2)$ .

De ello se desprende que $n$ es un número primo. $\quad\blacksquare$