Raíz primitiva módulo n para niños
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.
Existencia de raíces primitivas
Se puede demostrar que si p es un número primo, entonces existe alguna raíz primitiva módulo p (para la demostración se utiliza el hecho de que 
es un cuerpo cuando p es primo). Fijada b una raíz primitiva módulo p, cualquier entero a que no sea divisible entre p puede escribirse como 
para un único 
.
También puede demostrarse que si 
con p un primo impar (mayor que 2), entonces existen raíces primitivas módulo n, así como también existen raíces primitivas módulo n cuando n=1, 
, siendo p, como antes, un primo impar. Éstos, junto con el valor n=4, son los únicos números n que permiten raíces primitivas módulo n.
Aplicaciones
Al utilizar el protocolo criptográfico Diffie-Hellman suelen escogerse un primo p y g una raíz primitiva módulo p. Como dijimos, dado 
se tiene 
para un único . Encontrar ese r fijados a y b es lo que se conoce como el problema del logaritmo discreto.
Véase también
En inglés: Primitive root modulo n Facts for Kids
- Aritmética modular
- Logaritmo discreto
