En teoría de números, el test de Lucas es un test de primalidad para un número natural n y requiere que los factores primos de n − 1 sean conocidos.
Si existe un número natural a menor que n y mayor que 1 que verifica las condiciones
![{\displaystyle a^{n-1}\ \equiv \ 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/99e54655d0ef48a660f8c552d043077c3fa8421f)
así como
![{\displaystyle a^{({n-1})/q}\ \not \equiv \ 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba847e29f089e645bcbc6d4c69e539cc82d87a27)
para todos los factores primos q de n − 1, entonces n es primo. Si no puede encontrarse tal a, entonces n es un número compuesto.
Este algoritmo es correcto ya que si a pasa el primer paso, podemos deducir que a y n son coprimos. Si a también pasa el segundo paso, entonces el orden de a en el grupo (Z/nZ)* es igual a n − 1, lo que significa que el orden de ese grupo es n − 1, implicando que n es primo. Recíprocamente, si n es primo, entonces existe una raíz primitiva módulo n y cualquier raíz primitiva pasará ambos pasos del algoritmo.
Ejemplo
Por ejemplo, tómese n = 71. Entonces, n − 1 = 70 = (2)(5)(7).
Tómese ahora a = 11. En primer lugar:
![{\displaystyle 11^{70}\ \equiv \ 1{\pmod {71}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b401c4490149e00515fd4c3263fa89b1bbeb9f5b)
Esto no demuestra que el orden multiplicativo de 11 mod 71 es 70, porque algún factor de 70 aún podría funcionar arriba. Verificamos entonces 70 dividido por sus factores primos:
![{\displaystyle 11^{35}\ \equiv \ 70\ \not \equiv \ 1{\pmod {71}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f6d84b6c5d6e7b2e670bba9d8de2b284b92ed84)
![{\displaystyle 11^{14}\ \equiv \ 54\ \not \equiv \ 1{\pmod {71}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/667f85b9f29b2cbef0866f0b815010b8ff8bb59d)
![{\displaystyle 11^{10}\ \equiv \ 32\ \not \equiv \ 1{\pmod {71}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d9873dab00a95891efe5d848e6369f0bd3f6acf)
Entonces, el orden multiplicativo de 11 mod 71 es 70 y de esta manera, 71 es primo.
Para realizar estas potencias modulares debería usarse el método acelerado de exponenciación binaria.
Véase también
Referencias