Raíz primitiva módulo n

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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  \langle a \rangle = \mathbb{Z}_n^* , donde \mathbb{Z}_n^* denota los elementos invertibles módulo n. Dado que el orden de \mathbb{Z}_n^* es \phi(n), siendo φ la función phi de Euler, una raíz primitiva es un elemento que genere este orden.

Se puede demostrar sin mucha dificultad 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\}. Encontrar ese r fijados a y b es lo que se conoce como el problema del logaritmo discreto.

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.

Véase también[editar]

Referencias[editar]

Apostol, Tom (2002). «Raíces primitivas» (en español). 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.