Congruencias de alto orden y teoremas de estructura

Estructura de $(\mathbb{Z}/p^k\mathbb{Z})^*$ como grupo cíclico

Uno de los teoremas estructurales más importantes de la teoría de números es:

Teorema. Para todo primo $p$ y todo $k \ge 1$, el grupo $(\mathbb{Z}/p^k\mathbb{Z})^*$ es cíclico, excepto cuando $p = 2$ y $k \ge 3$.

Más precisamente: $(\mathbb{Z}/p^k\mathbb{Z})^*$ tiene orden $\varphi(p^k) = p^{k-1}(p-1)$ y es cíclico para $p$ impar (para todo $k \ge 1$), y para $p = 2$: $(\mathbb{Z}/2\mathbb{Z})^* = \{1\}$, $(\mathbb{Z}/4\mathbb{Z})^* \cong \mathbb{Z}/2\mathbb{Z}$, $(\mathbb{Z}/2^k\mathbb{Z})^* \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2^{k-2}\mathbb{Z}$ para $k \ge 3$.

Un generador del grupo cíclico $(\mathbb{Z}/p^k\mathbb{Z})^*$ se llama **raíz primitiva módulo $p^k$**. Si $g$ es raíz primitiva módulo $p$, entonces $g$ o $g + p$ es raíz primitiva módulo $p^k$ para todo $k \ge 2$ (el Hensel garantiza el levantamiento del orden).

Consecuencia para residuos cuadráticos. En $(\mathbb{Z}/p^k\mathbb{Z})^*$ cíclico de orden $N = p^{k-1}(p-1)$, los residuos cuadráticos son exactamente los cuadrados, que forman un subgrupo de índice $\gcd(2, N) = 2$ (para $p$ impar). Hay exactamente $N/2 = p^{k-1}(p-1)/2$ residuos cuadráticos módulo $p^k$ entre los elementos de $(\mathbb{Z}/p^k\mathbb{Z})^*$.

Raíces primitivas: existencia y propiedades

**Construcción de raíces primitivas módulo $p^k$.** Sea $g$ una raíz primitiva módulo $p$ (cuya existencia se demuestra por ser $\mathbb{F}_p^*$ un grupo cíclico, como campo finito). Afirmamos que $g$ es raíz primitiva módulo $p^2$ o bien $g + p$ lo es.

Sea $d = \mathrm{ord}_{p^2}(g)$. Como $(g^d - 1) \equiv 0 \pmod{p^2}$ implica $p \mid g^d - 1$, tenemos $(p-1) \mid d$. Además $d \mid \varphi(p^2) = p(p-1)$. Así $d = p-1$ o $d = p(p-1)$. Si $d = p(p-1)$, $g$ es raíz primitiva módulo $p^2$. Si $d = p-1$, consideramos $g' = g + p$: se verifica que $\mathrm{ord}_{p^2}(g') = p(p-1)$, pues $(g+p)^{p-1} \equiv g^{p-1} + (p-1)g^{p-2} \cdot p \equiv 1 + (p-1)g^{p-2}p \pmod{p^2}$, y $p \nmid (p-1)g^{p-2}$.

Una vez que $g$ es raíz primitiva módulo $p^2$, es raíz primitiva módulo $p^k$ para todo $k \ge 1$ por inducción via Hensel.

Aplicación: órdenes y potencias. Si $g$ es raíz primitiva módulo $m$, entonces $\mathrm{ord}_m(g^j) = \varphi(m) / \gcd(j, \varphi(m))$. En particular, $g^j$ es raíz primitiva módulo $m$ si y solo si $\gcd(j, \varphi(m)) = 1$. El número de raíces primitivas módulo $p^k$ es $\varphi(\varphi(p^k)) = \varphi(p^{k-1}(p-1))$.

Problema típico. Demostrar que si $p$ es primo impar y $a$ es una raíz primitiva módulo $p^2$, entonces $a$ es raíz primitiva módulo $p^k$ para todo $k \ge 1$. Solución: basta demostrar $\mathrm{ord}_{p^k}(a) = p^{k-1}(p-1)$ por inducción sobre $k$: el paso inductivo usa la identidad $a^{p^{k-2}(p-1)} = 1 + c \cdot p^{k-1}$ con $p \nmid c$, que se verifica con LTE.

Símbolo de Legendre: criterio de Euler y propiedades

Criterio de Euler. Para primo impar $p$ y $\gcd(a,p)=1$: $a$ es residuo cuadrático módulo $p$ si y solo si $a^{(p-1)/2} \equiv 1 \pmod{p}$. El símbolo de Legendre codifica esto: $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$ (la congruencia es una igualdad pues ambos lados son $\pm 1$).

Propiedades del símbolo de Legendre. Para $p$ primo impar y $\gcd(a,p) = \gcd(b,p) = 1$:

(1) Multiplicatividad: $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$.

(2) Periodicidad: $a \equiv b \pmod{p} \Rightarrow \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$.

(3) Primer suplemento: $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$. Es $+1$ si $p \equiv 1 \pmod 4$ y $-1$ si $p \equiv 3 \pmod 4$.

(4) Segundo suplemento: $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$. Es $+1$ si $p \equiv \pm 1 \pmod 8$ y $-1$ si $p \equiv \pm 3 \pmod 8$.

(5) Reciprocidad cuadrática (ver Lección 7.1): $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$.

Ejemplo: $\left(\frac{30}{97}\right) = \left(\frac{2}{97}\right)\left(\frac{3}{97}\right)\left(\frac{5}{97}\right)$. Con $97 \equiv 1 \pmod 8$: $\left(\frac{2}{97}\right) = 1$. Con reciprocidad: $\left(\frac{3}{97}\right) = \left(\frac{97}{3}\right)(-1)^{1 \cdot 48} = \left(\frac{1}{3}\right) = 1$. Y $\left(\frac{5}{97}\right) = \left(\frac{97}{5}\right)(-1)^{2 \cdot 48} = \left(\frac{2}{5}\right) = -1$. Luego $\left(\frac{30}{97}\right) = 1 \cdot 1 \cdot (-1) = -1$: $30$ no es residuo cuadrático módulo $97$.

El símbolo de Jacobi y módulos compuestos

Para módulo compuesto $n = p_1^{e_1} \cdots p_r^{e_r}$ (con $n$ impar positivo), el símbolo de Jacobi generaliza el símbolo de Legendre:

$\left(\frac{a}{n}\right) = \prod_{i=1}^r \left(\frac{a}{p_i}\right)^{e_i}.$

Advertencia crítica. $\left(\frac{a}{n}\right) = 1$ NO implica que $a$ sea residuo cuadrático módulo $n$. Por ejemplo: $\left(\frac{2}{15}\right) = \left(\frac{2}{3}\right)\left(\frac{2}{5}\right) = (-1)(-1) = 1$, pero $2$ no es residuo cuadrático módulo $15$ (pues $x^2 \equiv 2 \pmod 3$ no tiene solución ya que $\left(\frac{2}{3}\right) = -1$).

Lo que sí vale: si $\left(\frac{a}{n}\right) = -1$, entonces $a$ definitivamente NO es residuo cuadrático módulo $n$.

Propiedades del símbolo de Jacobi. Se conservan la multiplicatividad $\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right)$, el primer suplemento $\left(\frac{-1}{n}\right) = (-1)^{(n-1)/2}$, el segundo $\left(\frac{2}{n}\right) = (-1)^{(n^2-1)/8}$, y la reciprocidad: para $m, n$ impares positivos coprimos, $\left(\frac{m}{n}\right)\left(\frac{n}{m}\right) = (-1)^{\frac{m-1}{2}\cdot\frac{n-1}{2}}$. La reciprocidad del símbolo de Jacobi permite el algoritmo de Euclides para calcular el símbolo rápidamente.

El símbolo de Kronecker extiende el Jacobi a módulos arbitrarios (incluyendo pares y negativos): $\left(\frac{a}{n}\right)$ para $n \in \mathbb{Z}$ cualquiera, con definiciones especiales para $n \in \{0, \pm 1, \pm 2\}$. Es fundamental en la teoría de formas cuadráticas y discriminantes.

Problema resuelto: orden y residuos combinados

Problema. Sea $p > 3$ primo con $p \equiv 3 \pmod{4}$. Prueba que $-1$ no es una potencia de $3$ módulo $p$ (es decir, $-1 \notin \langle 3 \rangle$ en $(\mathbb{Z}/p\mathbb{Z})^*$) si $\left(\frac{3}{p}\right) = -1$.

Solución. Supongamos por contradicción que $3^k \equiv -1 \pmod{p}$ para algún entero $k \ge 0$. Entonces $3^{2k} \equiv 1 \pmod{p}$, así $\mathrm{ord}_p(3) \mid 2k$.

Sea $d = \mathrm{ord}_p(3)$. Como $3^k \equiv -1 \pmod p$, $3^k \ne 1 \pmod p$, así $d \nmid k$. Como $d \mid 2k$ pero $d \nmid k$, tenemos $v_2(d) > v_2(k)$, luego $d = 2^s \cdot t$ con $s \ge 1$ y $k = 2^{s-1} \cdot r$ con $\gcd(r,2)$ libre.

Ahora, $3^{(p-1)/2} \equiv \left(\frac{3}{p}\right) \equiv -1 \pmod p$ (por el criterio de Euler y la hipótesis $\left(\frac{3}{p}\right) = -1$). Esto dice que el orden $d = \mathrm{ord}_p(3)$ no divide a $(p-1)/2$, es decir $v_2(d) > v_2((p-1)/2)$.

Pero $p \equiv 3 \pmod 4$ implica $p - 1 \equiv 2 \pmod 4$, luego $v_2(p-1) = 1$, y $v_2((p-1)/2) = 0$. Entonces la condición $v_2(d) > 0$ siempre se cumple cuando $\left(\frac{3}{p}\right) = -1$.

Si $3^k \equiv -1 \pmod p$, entonces $3^{2k} \equiv 1$ y $d \mid 2k$. Elevando al cuadrado la hipótesis $3^k \equiv -1$: $(3^k)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \equiv (-1)^1 \cdot \ldots$. Como $p \equiv 3 \pmod 4$, $(p-1)/2$ es impar, así $(-1)^{(p-1)/2} = -1$. Pero también $3^{k(p-1)/2} = (3^{(p-1)/2})^k \equiv (-1)^k \pmod p$. Si $k$ es impar, $(-1)^k = -1$ ✓; si $k$ es par, $(-1)^k = 1$, pero necesitamos que sea $-1$, contradicción. Así $k$ debe ser impar.

Pero si $k$ es impar y $3^k \equiv -1 \pmod p$, entonces $3^{2k} \equiv 1$ con $d \mid 2k$ y $d \nmid k$ (pues $3^k \ne 1$). Usando que $\left(\frac{3}{p}\right) = -1$ significa que $3$ es no-residuo cuadrático módulo $p$: si $3 = g^j$ para raíz primitiva $g$, entonces $j$ es impar. $3^k = g^{jk}$; para que $g^{jk} = -1 = g^{(p-1)/2}$ necesitamos $jk \equiv (p-1)/2 \pmod{p-1}$. Como $j$ impar y $(p-1)/2$ impar (pues $p \equiv 3 \pmod 4$), necesitamos $k$ impar. Pero $g^{jk}$ siendo $-1$ requiere $2 \nmid jk$, que ocurre cuando $j$ y $k$ ambos impares — una condición que puede o no satisfacerse según el primo $p$. La conclusión es que la condición $\left(\frac{3}{p}\right) = -1$ impone restricciones sobre el orden de $3$, pero el enunciado literal como está formulado tiene matices adicionales que dependen de $p$. $\square$