Orden y Raíces Primitivas

Teoría

El orden multiplicativo de un entero $a$ módulo $n$, que puedes escribir como $\text{ord}_n(a)$, es el entero positivo más pequeño $k$ tal que $a^k \equiv 1 \pmod n$. Este concepto solo está definido cuando $\gcd(a, n) = 1$. Por el Teorema de Euler, ya sabes que $a^{\phi(n)} \equiv 1 \pmod n$, lo que significa que el orden siempre existe y es a lo mucho $\phi(n)$. Si el orden de $a$ es exactamente igual a $\phi(n)$, entonces a $a$ le decimos raíz primitiva módulo $n$. En el lenguaje de teoría de grupos, el conjunto de unidades módulo $n$ forma un grupo bajo la multiplicación, que puedes denotar como $(\mathbb{Z}/n\mathbb{Z})^\times$. Si existe una raíz primitiva, este grupo es cíclico, y la raíz primitiva es un generador del grupo.

Entender el orden es fundamental para resolver congruencias exponenciales y analizar la estructura de las potencias módulo $n$. Las potencias de un número $a$ se repiten con un periodo igual a $\text{ord}_n(a)$. Las raíces primitivas son especialmente poderosas porque te permiten relacionar la estructura multiplicativa con la estructura aditiva. Si $g$ es una raíz primitiva módulo $n$, entonces para cualquier entero $x$ coprimo con $n$, existe un