Número pseudoprimo de Lucas

Si n es compuesto, entonces esta congruencia generalmente no se cumple.Ejemplos: si P = 3, Q = −1 y D = 13, la secuencia de U es (sucesión A006190 en OEIS): U0 = 0 , U1 = 1, U2 = 3, U3 = 10, etc. Primero, sea n = 19.En este caso, 19 es primo, por lo que no es un pseudoprimo de Lucas.De hecho, 119 es el pseudoprimo más pequeño para P = 3, Q = −1.Como se analiza más abajo, para verificar la ecuación (2) para una n dada, no se necesita calcular todos los primeros n + 1 términos en la secuencia U.Sea Q = −1, entonces, los pseudoprimos de Lucas más pequeños para P = 1, 2, 3, ... son Aquí se factorizaAntes de iniciar una prueba de primos probables, generalmente se verifica que n, el número del que se va a probar su primalidad, es impar, no es un cuadrado perfecto y no es divisible por ningún primo pequeño menor que un límite conveniente.Es una buena idea comprobar que n no tiene factores primos en común con P o Q.Este método de elegir D, P y Q fue sugerido por John Selfridge.Esta búsqueda nunca tendrá éxito si n es un cuadrado y, por el contrario, si tiene éxito, es una prueba de que n no es un cuadrado.Dados D, P y Q, existen relaciones de recurrencia que permiten calcular rápidamenteTambién se calculan los términos del mismo número en la secuencia V, junto con Q1, Q2, Q4, Q5, Q 10, Q11, Q22 y Q44.Al final del cálculo, se habrán obtenido Un+1, Vn+1 y n+1X, (mod n).A continuación se verifica la congruencia (2) usando el valor conocido de Un+1.Cuando se eligen D, P y Q como se describe anteriormente, los primeros 10 pseudoprimos de Lucas fuertes son: 5459, 5777, 10877, 16109, 18971, 22499, 24569 , 25199, 40309 y 58519 (sucesión A217255 en OEIS).Con este método para seleccionar D, P y Q, los primeros 10 pseudoprimos de Lucas extra fuertes son 989, 3239, 5777, 10877, 27971, 29681, 30739, 31631, 39059 y 72389 (sucesión A217719 en OEIS).Si resulta que n es compuesto, estas condiciones adicionales pueden ayudar a descubrir ese hecho.Si la congruencia (2) o la (3) es falsa, esto constituye una prueba de que n no es primo.Si ambas congruencias son verdaderas, entonces es aún más probable que n sea primo que si se hubiera verificado solo la congruencia (2).permanezcan sin cambios y P = Q = 5 (véanse las Relaciones algebraicas en el artículo sucesión de Lucas).Si se usa este método mejorado para elegir P y Q, entonces 913 = 11·83 es el único compuesto menor que 108 para el cual la congruencia (3) es verdadera (véase la página 1409 y la Tabla 6 de;[1]​).Cálculos más extensos demuestran que, con este método de elegir D, P y Q, solo hay cinco números compuestos impares menores que 1015 para los cuales la congruencia (3) es verdadera., entonces se puede establecer una condición de congruencia adicional que implica muy pocos nuevos cálculos.La otra se produce cuando n = p(p+2) es el producto de dos primos gemelos.Tal n es fácil de factorizar, porque en este caso, n+1 = (p+1)2 es un cuadrado perfecto.Un pseudoprimo de Fibonacci suele ser[2]​: 264,  [3]​: 142,  [4]​: 127 definido como un número compuesto n no divisible por 5 para el cual se cumple la congruencia (1) con P = 1 y Q = −1 (pero n lo es).[4]​: 129  Hoggatt y Bicknell estudiaron las propiedades de estos pseudoprimos en 1974.[12]​ Jacobsen enumera todos los 111.443 de estos pseudoprimos menores que 1013.[13]​ Se ha demostrado que ni siquiera existen pseudoprimos de Fibonacci tal como los define la ecuación (5).[14]​[15]​ Sin embargo, los pseudoprimos de Fibonacci sí que existen (sucesión A141137 en OEIS) bajo la primera definición dada por (1).