Un entero g tal que los residuos g^k (reduciendo modulo N) producen todas las clases de residuos coprimas con N; equivalentemente, g genera el grupo multiplicativo (Z/NZ)^×.

Principio

Si (Z/NZ)^× es cíclico, existe un elemento g con orden multiplicativo φ(N) cuyas potencias enumeran todas las unidades modulo N.

Demostración

Para N = 7, el entero 3 es una raíz primitiva porque las potencias 3^1,...,3^6 módulo 7 dan 3,2,6,4,5,1, cubriendo las seis unidades; por tanto 3 tiene orden φ(7)=6.

Aplicación incorrecta

Tratar a g como raíz primitiva cuando g no es coprimo con N o cuando (Z/NZ)^× no es cíclico (por ejemplo N = 8) conduce a errores sobre la generación de todas las unidades.

Consecuencia

Cuando existe una raíz primitiva, los logaritmos discretos respecto a ella proporcionan una biyección entre (Z/NZ)^× y Z/φ(N)Z, permitiendo argumentos basados en la estructura cíclica.

Inversión

La situación inversa es un elemento cuyas potencias generan sólo un subgrupo propio de (Z/NZ)^× (por ejemplo un elemento con orden que divide un divisor propio de φ(N)), de modo que no recorre todos los residuos coprimos.

Límite

Las raíces primitivas existen para N = 1, 2, 4, p^k y 2p^k con p primo impar; no existen para un N compuesto cualquiera. El concepto se aplica únicamente a enteros coprimos con N y al grupo multiplicativo de unidades modulo N.

Tensión semántica

Hay que distinguir raíz primitiva de un generador de un grupo aditivo o de cualquier elemento de orden máximo en un subgrupo; 'primitiva' significa aquí generador del grupo multiplicativo completo cuando éste es cíclico.

Síntesis

Una raíz primitiva modulo N es un entero generador que, si existe, convierte al grupo multiplicativo de las unidades modulo N en un grupo cíclico cuyas potencias recorren todas las clases invertibles.