Determinar el valor de inicio para la prueba de primalidad

Question

Esta pregunta es acerca de Lucasiano prueba de primalidad de los números de la forma $N=3\cdot 2^n-1$ .

Hay una instrucción siguiente en el artículo de la Wikipedia : Lucas-Lehmer-Riesel prueba :

"Si $k = 3$ : si $n = 0$ o $3$ mod $4$,$u_0 = 5778$."

Sin embargo, parece que los valores de $u_0 = 18$$u_0 = 488$, también encaja .

Aquí es Maxima la aplicación de la prueba con valor inicial $u_0 = 18$ e aquí usted puede encontrar una lista de los exponentes para que $3\cdot 2^n-1$ es primo .

Por lo tanto , mi pregunta es: ¿hay alguna razón especial por la $5778$ ha sido elegida para ser valor de inicio en lugar de $18$ o $488$ ?

Answer 1

(El caso con respecto a la secuencia, comenzando con 18-algunos de progreso).

En el artículo original de Lehmer demostrado que $V_{3\cdot 2^{n+1}}\equiv \ 0 \mod N \ ({\text{with}}\ N=3\cdot 2^n-1),$ donde $V_n=(\sqrt{5}-2)^n+(\sqrt{5}+2)^n\ ({\text{set}}\ a=\sqrt{5}-2,\ b=\sqrt{5}+2).$ Ahora se nota que la secuencia de $\{u_n\}=\{V_{3\cdot 2^{n+1}}\}.$ Para $n=0$ obtenemos $V_6=5778$ que se establece como $u_0$ (así que esta es la razón por la que 5778). La secuencia que se inicia con $18$ es el tiempo de la secuencia $\{V_{2^{n+1}}\}_{n\geq 1}=\{18,322,...\}.$ Usando la relación $V_{3\cdot 2^{n+1}}=V_{2^{n+1}}(V_{2^{n+1}}-1)$ (a partir de la propiedad de dar a $V_{n+m}=...$) llegamos $V_{2^{n+1}}(V_{2^{n+1}}-1)\equiv 0\mod N.$ Ahora es suficiente para demostrar que $\gcd(V_{2^{n+1}}-1,3\cdot 2^{n}-1)=1.$