Índices y logaritmos discretos en olimpiadas

La analogía con el logaritmo real

El logaritmo real transforma productos en sumas: $\log(xy) = \log x + \log y$. El índice módulo $p^k$ hace exactamente lo mismo en aritmética modular.

Sea $p$ primo impar y $g$ una raíz primitiva módulo $p^k$. Para cada $a$ con $\gcd(a, p) = 1$, existe un único $j \in \{0, 1, \ldots, \phi(p^k)-1\}$ con $g^j \equiv a \pmod{p^k}$. Definimos $\text{ind}_g(a) = j$, llamado el **índice de $a$ en base $g$ módulo $p^k$**.

Las propiedades fundamentales son análogas al logaritmo: $\text{ind}_g(ab) \equiv \text{ind}_g(a) + \text{ind}_g(b) \pmod{\phi(p^k)}$ y $\text{ind}_g(a^n) \equiv n \cdot \text{ind}_g(a) \pmod{\phi(p^k)}$. Estas igualdades se demuestran directamente: si $a = g^r$ y $b = g^s$, entonces $ab = g^{r+s}$ y $a^n = g^{nr}$.

Aplicación 1: resolver $x^n \equiv a \pmod{p^k}$

Tomando índice de ambos lados, la ecuación $x^n \equiv a \pmod{p^k}$ se convierte en la congruencia lineal $n \cdot \text{ind}_g(x) \equiv \text{ind}_g(a) \pmod{\phi(p^k)}$.

Esta congruencia lineal tiene solución si y solo si $d = \gcd(n, \phi(p^k))$ divide a $\text{ind}_g(a)$. Cuando es soluble, tiene exactamente $d$ soluciones módulo $\phi(p^k)$, lo que da exactamente $d$ valores de $x$ módulo $p^k$.

Ejemplo IMO-nivel. ¿Cuántos $x \in \{1, \ldots, p^2\}$ con $\gcd(x,p) = 1$ satisfacen $x^{p-1} \equiv 1 \pmod{p^2}$? Tomando índice: $(p-1) \cdot \text{ind}_g(x) \equiv 0 \pmod{p(p-1)}$, es decir, $p \mid \text{ind}_g(x)$. Hay $\phi(p^2)/(p) = p-1$ múltiplos de $p$ en $\{0, 1, \ldots, p(p-1)-1\}$. Así exactamente $p-1$ elementos de $(\mathbb{Z}/p^2\mathbb{Z})^*$ satisfacen $x^{p-1} \equiv 1 \pmod{p^2}$. Estos son precisamente los llamados números de Wieferich base $x$ módulo $p^2$... o simplemente los $x$ que hacen trivial la condición de Fermat elevada.

Aplicación 2: ecuaciones $a^x \equiv b \pmod{p^k}$

La ecuación $a^x \equiv b \pmod{p^k}$ (con $\gcd(a,p) = \gcd(b,p) = 1$) también se reduce con el índice: $x \cdot \text{ind}_g(a) \equiv \text{ind}_g(b) \pmod{\phi(p^k)}$.

Esta es una congruencia lineal en $x$. Es soluble si y solo si $d = \gcd(\text{ind}_g(a), \phi(p^k))$ divide a $\text{ind}_g(b)$.

Caso especial relevante en olimpiadas: $a^x \equiv 1 \pmod{p^k}$. Aquí $\text{ind}_g(1) = 0$, así la condición es $d \mid 0$, que siempre se cumple. Las soluciones son $x \equiv 0 \pmod{\phi(p^k)/d}$, es decir, los múltiplos de $\phi(p^k)/\gcd(\text{ind}_g(a), \phi(p^k))$. Esto es exactamente $\text{ord}_{p^k}(a)$, consistente con la definición.

El poder del índice es que convierte un problema multiplicativo en un problema lineal, para el cual tenemos herramientas completas (algoritmo de Euclides, TCR, etc.).

Problema clásico: el índice en acción

Problema (IMO Shortlist 1999 N1 — variante): Sea $p$ primo impar. Demuestra que el número de pares $(x, y)$ con $1 \le x, y \le p-1$ y $x^y \equiv y^x \pmod{p}$ es $p - 1 + \tau(p-1)$, donde $\tau$ es la función divisores.

Solución. Tomando índice en base $g$ (raíz primitiva mod $p$) de ambos lados: $y \cdot \text{ind}(x) \equiv x \cdot \text{ind}(y) \pmod{p-1}$.

Sea $r = \text{ind}(x)$ y $s = \text{ind}(y)$, con $r, s \in \{0, 1, \ldots, p-2\}$ (donde $r = 0$ significa $x = 1$ y $s = 0$ significa $y = 1$). La condición se convierte en $ys \equiv xr$ ... espera, no: $yr \equiv xs \pmod{p-1}$.

Si $r = 0$: $x = 1$, la condición es $0 \equiv 0$, verdadera para cualquier $y$. Eso da $p-1$ pares.

Si $r \ne 0$ y $s = 0$: $y = 1$, la condición es $r \cdot 1 \equiv 0$, es decir $r \equiv 0 \pmod{p-1}$, lo que fuerza $r = 0$. Contradicción. Cero pares adicionales.

Si $r, s \ne 0$: la condición $yr \equiv xs \pmod{p-1}$ con $x = g^r$ y $y = g^s$ se lee $g^s \cdot r \equiv g^r \cdot s \pmod{p-1}$... el análisis completo requiere contar las soluciones de $r/s \equiv x/y$ en un sentido preciso. La respuesta final $\tau(p-1)$ cuenta los pares con $x/y = g^{r-s}$ una potencia de $g$ que coincide con $r/s$ módulo $p-1$. El resultado $p - 1 + \tau(p-1)$ es un ejercicio clásico de índices que ilustra cómo el álgebra de índices simplifica los conteos.

La tabla de índices y el cálculo práctico

En la práctica olímpica, el índice se usa en dos modos: teórico (para demostrar existencia o contar soluciones) y computacional (para resolver congruencias concretas). El modo computacional requiere conocer la tabla de índices para primos pequeños.

Para $p = 7$, $g = 3$ (raíz primitiva, pues $\text{ord}_7(3) = 6$): $\text{ind}_3(1) = 0$, $\text{ind}_3(3) = 1$, $\text{ind}_3(2) = 2$ (pues $3^2 = 9 \equiv 2$), $\text{ind}_3(6) = 3$ (pues $3^3 = 27 \equiv 6$), $\text{ind}_3(4) = 4$ (pues $3^4 = 81 \equiv 4$), $\text{ind}_3(5) = 5$ (pues $3^5 = 243 \equiv 5$).

Con esta tabla: $x^4 \equiv 2 \pmod{7}$ se convierte en $4 \cdot \text{ind}(x) \equiv 2 \pmod{6}$, es decir, $2 \cdot \text{ind}(x) \equiv 1 \pmod{3}$, así $\text{ind}(x) \equiv 2 \pmod{3}$. Las soluciones son $\text{ind}(x) \in \{2, 5\}$, dando $x \in \{2, 5\}$. Verificación: $2^4 = 16 \equiv 2$ ✓, $5^4 = 625 \equiv 2$ ✓.

En olimpiadas los problemas rara vez piden calcular el índice explícitamente —el valor de la herramienta está en el argumento estructural—, pero conocer el mecanismo computacional permite verificar y construir ejemplos con rapidez.