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 $\mathbb {Z} _{n}^{*}$, es decir, si $\forall b\in \mathbb {Z} _{n}^{*}$ existe $k\in \mathbb {Z}$ tal que $a^{k}\equiv b{\pmod {n}}$. Aquí $\mathbb {Z} _{n}^{*}$ denota los elementos invertibles módulo n.

Dado que el orden de $\mathbb {Z} _{n}^{*}$ es $\varphi (n)$, siendo φ la función phi de Euler, una raíz primitiva es un elemento con ese orden.

Ejemplos

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

${\begin{array}{l}3^{1}=3\\3^{2}=9\equiv 4{\pmod {5}}\\3^{3}=3^{2}\times 3\equiv 4\times 3=12\equiv 2{\pmod {5}}\\3^{4}=3^{3}\times 3\equiv 2\times 3=6\equiv 1{\pmod {5}}\\\end{array}}$

Si observamos bien, todo resto coprimo con 5 (1, 2, 3 y 4) es congruente con $3^{k}$ módulo 5 para algún $k\in \mathbb {Z}$. De hecho (y esto ocurre para toda raíz primitiva) el $k$ puede elegirse entre 1 y $4=\varphi (5)$.

Para $n=14$, tenemos que 5 es raíz primitiva:

${\begin{array}{l}5^{0}=1\\5^{1}=5\\5^{2}=25\equiv 11{\pmod {14}}\\5^{3}=5^{2}\times 5\equiv 11\times 5=55\equiv 13{\pmod {14}}\\5^{4}=5^{3}\times 5\equiv 13\times 5=65\equiv 9{\pmod {14}}\\5^{5}=5^{4}\times 5\equiv 9\times 5=45\equiv 3{\pmod {14}}\\\end{array}}$

$\mathbb {Z} _{14}^{*}=\{1,3,5,9,11,13\}$, o sea que obtenemos todos los elementos de $\mathbb {Z} _{14}^{*}$ 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 $\mathbb {Z} _{p}$ 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 $a=b^{r}{\pmod {p}}$ para un único $r\in \{1,2,...,p-1\}$.

También puede demostrarse que si $n=p^{k}$ 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, $n=2p^{k}$, 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 $b\in \mathbb {Z} _{p}^{*}$ se tiene $b=g^{r}{\pmod {p}}$ para un único $r\in \{1,2,...,p-1\}$. Encontrar ese r fijados a y b es lo que se conoce como el problema del logaritmo discreto.

Véase también

• Aritmética modular
• Logaritmo discreto

Referencias

• Apostol, Tom (2002). «Raíces primitivas». Introducción a la teoría analítica de números (2 edición). España: Reverté. pp. 255-265. ISBN 84-291-5006-4. 

• de Oliveira Santos, José Plínio (2009). «6 - Raízes primitivas». Introducao à teoria dos numeros (en portugués) (3 edición). Río de Janeiro: IMPA. pp. 116-127. ISBN 978-85-244-0142-8. 

• Datos: Q948010