Test de Lucas

En teoria de números, el test de Lucas és un test de primalidad per a un número natural n i requerix que els factors primers de n − 1 siguen coneguts.

Si existix un número natural a menor que n i major que 1 que verifica les condicions

$a^{n-1}\equiv 1(\mathrm{mod}n)$

aixina com

$a^{(n-1)/q}\equiv ̸1(\mathrm{mod}n)$

per a tots els factors primers q de n − 1, llavors n és primer. Si no pot trobar-se tal a, llavors n és un número compuesto.

Este algoritme és correcte ya que si a pansa el primer pas, podem deduir que a i n són coprimos. Si a també passa el segon pas, llavors l'orde de a en el grup (Z/nZ)* és igual a n − 1, lo que significa que l'orde d'eixe grup és n − 1, implicant que n és primer. Recíprocamente, si n és primer, llavors existix una raïl primitiva mòdul n i qualsevol raïl primitiva passarà abdós passos de l'algoritme.

Eixemple

Per eixemple, prenga's n = 71. Llavors, n − 1 = 70 = (2)(5)(7). Prenga's ara a = 11. En primer lloc:

$11^{70}\equiv 1(\mathrm{mod}71)$

Açò no demostra que l'orde multiplicativo d'11 mod 71 és 70, perque algun factor de 70 encara podria funcionar dalt. Verifiquem llavors 70 dividit pels seus factors primers:

$11^{35}\equiv 70\equiv ̸1(\mathrm{mod}71)$

$11^{14}\equiv 54\equiv ̸1(\mathrm{mod}71)$

$11^{10}\equiv 32\equiv ̸1(\mathrm{mod}71)$

Llavors, l'orde multiplicativo d'11 mod 71 és 70 i d'esta manera, 71 és primer.

Per a realisar estes potències modular deuria usar-se el método accelerat d'exponenciación binaria.

Vore també

• Edouard Lucas
• Test de Lucas-Lehmer
• Número primo

Referències

• (2005) Prime Numbers: a Computational Perspective (2nd edition), Springer, p. 173. ISBN 0-387-25282-7.
• (2001) 17 Lectures on Fermat Numbers: From Number Theory to Geometry (vol. 9), Canadian Mathematical Society/Springer, p. 41. ISBN 0-387-95332-9.