Prueba de primalidad para números de la forma$N=k \cdot 3^n-1$

Question

Puede usted proporcionar la prueba o contraejemplo para la declaración dada a continuación?

Inspirado por Lucas-Lehmer-Riesel primalidad de prueba que he formulado la siguiente declaración:

Deje $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Deje $N= k \cdot 3^{n}-1 $ donde $k$ es un número natural positivo incluso , $ k<2^n$ e $n\ge3$ . Deje $a$ ser un número natural mayor que dos, tales que $\left(\frac{a-2}{N}\right)=1$ e $\left(\frac{a+2}{N}\right)=-1$ donde $\left(\frac{}{}\right)$ denota el símbolo de Jacobi. Deje $S_i=S_{i-1}^3-3 S_{i-1}$ con $S_0$ igual a la de modular $P_{9k/2}(a)\phantom{5} \text{mod} \phantom{5} N$. A continuación, $N$ es primo si y sólo si $S_{n-2} \equiv -2 \pmod{N}$ .

Puede ejecutar esta prueba aquí .

Yo estaba buscando contraejemplo utilizando la siguiente PARI/GP código:

CEk31(k1,k2,n1,n2)=
{
forstep(k=k1,k2,[2],
for(n=n1,n2,
if(k<2^n,
N=k*3^n-1;
a=3;
while(!(kronecker(a-2,N)==1 && kronecker(a+2,N)==-1),a++);
S=Mod(2*polchebyshev(9*k/2,1,a/2),N);
ctr=1;
while(ctr<=n-2,
S=Mod(2*polchebyshev(3,1,S/2),N);
ctr+=1);
if(S==N-2 && !ispseudoprime(N),print("k="k,"n="n)))))
}

Answer 1

Esta es una respuesta parcial.

Esta respuesta demuestra que, si $N$ es primo, entonces $S_{n-2}\equiv -2\pmod N$.

Prueba :

Definamos $s,t$ como $$s:=\frac{a-\sqrt{a^2-4}}{2},\qquad t:=\frac{a+\sqrt{a^2-4}}{2}$$ where $st=1$.

Aquí, vamos a demostrar por inducción sobre $i$que $$S_i\equiv s^{3^{i+2}k/2}+t^{3^{i+2}k/2}\pmod N\tag1$$

Vemos que $(1)$ tiene por $i=0$ desde $$S_0\equiv P_{9k/2}(a)=s^{9k/2}+t^{9k/2}\pmod N$$ Supposing that $(1)$ holds for $i$da $$\begin{align}S_{i+1}& \equiv S_i^3-3S_i \\\\&\equiv (s^{3^{i+2}k/2}+t^{3^{i+2}k/2})^3-3(s^{3^{i+2}k/2}+t^{3^{i+2}k/2})\\\\&\equiv s^{3^{i+3}k/2}+t^{3^{i+3}k/2}\pmod N\quad\square\end{align}$$

Ahora, el uso de $(1)$ e $k\cdot 3^n=N+1$, obtenemos $$S_{n-2}\equiv s^{3^nk/2}+t^{3^nk/2}\equiv s^{(N+1)/2}+t^{(N+1)/2}\pmod N$$ El uso que $$\sqrt{\frac{a\pm\sqrt{a^2-4}}{2}}=\frac{\sqrt{a+2}\pm\sqrt{a-2}}{2}$$ tenemos $$\begin{align}2^{N+1}S_{n-2}&\equiv (\sqrt{a+2}-\sqrt{a-2})^{N+1}+(\sqrt{a+2}+\sqrt{a-2})^{N+1} \\\\&\equiv (\sqrt{a+2}-\sqrt{a-2})(\sqrt{a+2}-\sqrt{a-2})^{N} \\&\qquad\quad +(\sqrt{a+2}+\sqrt{a-2})(\sqrt{a+2}+\sqrt{a-2})^{N} \\\\&\equiv \sqrt{a+2}\sum_{i=0}^{N}\binom Ni(\sqrt{a+2})^i((-\sqrt{a-2})^{N-i}+(\sqrt{a-2})^{N-i}) \\&\qquad \quad +\sqrt{a-2}\sum_{i=0}^{N}\binom Ni(\sqrt{a+2})^i((\sqrt{a-2})^{N-i}-(-\sqrt{a-2})^{N-i}) \\\\&\equiv \sum_{j=1}^{(N+1)/2}\binom{N}{2j-1}(a+2)^{j}\cdot 2(a-2)^{(N-(2j-1))/2} \\& \qquad \quad +\sum_{j=0}^{(N-1)/2}\binom{N}{2j}(a+2)^{j}\cdot 2(a-2)^{(N-2j+1)/2}\pmod N\end{align}$$

Usando ese $\binom Nm\equiv 0\pmod N$ para $1\le m\le N-1$, obtenemos $$4\cdot 2^{N-1}S_{n-2}\equiv 2(a+2)(a+2)^{(N-1)/2}+2(a-2)(a-2)^{(N-1)/2}\pmod N$$

Desde $$2^{N-1}\equiv 1,\qquad (a-2)^{(N-1)/2}\equiv 1,\qquad (a+2)^{(N-1)/2}\equiv -1\pmod N$$ tenemos $$4S_{n-2}\equiv -2(a+2)+2(a-2)\equiv -8\pmod N$$ a partir de la cual $$S_{n-2}\equiv -2\pmod N$$ de la siguiente manera.$\quad\blacksquare$