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 factoriza
Antes 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ápidamente
Tambié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).