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

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

Ejemplos

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

${\displaystyle {\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 ${\displaystyle 3^{k}}$ módulo 5 para algún ${\displaystyle k\in \mathbb {Z} }$. De hecho (y esto ocurre para toda raíz primitiva) el ${\displaystyle k}$ puede elegirse entre 1 y ${\displaystyle 4=\varphi (5)}$.

Para ${\displaystyle n=14}$, tenemos que 5 es raíz primitiva:

${\displaystyle {\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}}}$

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

También puede demostrarse que si ${\displaystyle 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, ${\displaystyle 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 ${\displaystyle b\in \mathbb {Z} _{p}^{*}}$ se tiene ${\displaystyle b=g^{r}{\pmod {p}}}$ para un único ${\displaystyle 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