¿Cuándo existen las raíces primitivas?
La existencia de raíces primitivas es una pregunta fundamental en teoría de números que determina la estructura del grupo multiplicativo de los enteros módulo $n$, que escribimos como $\mathbb{Z}_n^$. Una raíz primitiva módulo $n$ es un entero $g$ tal que las potencias de $g$ generan todos los enteros coprimos con $n$ módulo $n$. En términos de teoría de grupos, existe una raíz primitiva si y solo si $\mathbb{Z}_n^$ es un grupo cíclico. Cuando existe una raíz primitiva $g$, puedes expresar cada elemento $a$ coprimo con $n$ de forma única como $g^k \pmod n$ para algún índice $k \in {1, \dots, \phi(n)}$, lo que te permite usar "logaritmos discretos" (índices) para transformar problemas de multiplicación en problemas de suma.
Nota que las raíces primitivas no existen para todos los módulos. El Teorema de Existencia de Raíces Primitivas da una clasificación completa de los enteros $n$ para los cuales $\mathbb{Z}_n^*$ es cíclico. Esta clasificación es crucial para problemas de olimpiada que tienen que ver con el orden de los elementos, residuos de potencias y la estructura de la aritmética modular. Para módulos compuestos que no tienen raíces primitivas, la estructura del grupo es un producto de grupos cíclicos más pequeños, y el orden máximo de un elemento lo da la función de Carmichael $\lambda(n)$, que es