Raíz primitiva módulo n

Dado un número natural n, decimos que a es una raíz primitiva módulo n (abreviado mod n), si a genera como grupo a , es decir, si existe tal que . Aquí denota los elementos invertibles módulo n.

Dado que el orden de es , siendo φ la función phi de Euler, una raíz primitiva es un elemento con ese orden.

Ejemplos

Si entonces 3 es raíz primitiva módulo 5:

Si observamos bien, todo resto coprimo con 5 (1,2,3 y 4) es congruente con módulo 5 para algún . De hecho (y esto ocurre para toda raíz primitiva) el puede elegirse entre 1 y .

Para tenemos que 5 es raíz primitiva:

, o sea que obtenemos todos los elementos de como potencias de 5.

Other Languages