Polinomios sobre cuerpos finitos

El anillo $\mathbb{F}_p[x]$ y sus propiedades

Sea $p$ un primo. El anillo de polinomios $\mathbb{F}_p[x]$ tiene una estructura muy parecida a $\mathbb{Z}$: es un dominio euclídeo (hay división con resto), un dominio de ideales principales, y un dominio de factorización única.

El algoritmo de división: dado $f, g \in \mathbb{F}_p[x]$ con $g \ne 0$, existen únicos $q, r \in \mathbb{F}_p[x]$ con $f = qg + r$ y $\deg r < \deg g$ (o $r = 0$). Esto permite definir el $\gcd$ por el algoritmo de Euclides.

A diferencia de $\mathbb{Z}$, el grupo de unidades de $\mathbb{F}_p[x]$ son exactamente los polinomios constantes no nulos $\mathbb{F}_p^*$. Los polinomios irreducibles juegan el papel de los primos en $\mathbb{Z}$.

El número de polinomios mónicos de grado $n$ sobre $\mathbb{F}_p$ es $p^n$. El número de polinomios mónicos irreducibles de grado $n$ se denota $\pi_p(n)$ y hay una fórmula exacta via la inversión de Möbius.

El cuerpo $\mathbb{F}_{p^n}$

Si $f \in \mathbb{F}_p[x]$ es irreducible de grado $n$, el cociente $\mathbb{F}_p[x]/(f)$ es un cuerpo con $p^n$ elementos, denotado $\mathbb{F}_{p^n}$.

Todos los cuerpos con $p^n$ elementos son isomorfos (no importa el polinomio irreducible $f$ que se use): el cuerpo $\mathbb{F}_{p^n}$ es único salvo isomorfismo. Sus elementos pueden pensarse como "números módulo $f(x)$".

Teorema fundamental. Todo elemento de $\mathbb{F}_{p^n}$ es raíz del polinomio $x^{p^n} - x$. Demostración: el grupo multiplicativo $\mathbb{F}_{p^n}^*$ tiene $p^n - 1$ elementos, así todo $a \ne 0$ satisface $a^{p^n-1} = 1$, luego $a^{p^n} = a$. El cero también satisface $0^{p^n} = 0$. Por tanto $x^{p^n} - x$ tiene exactamente $p^n$ raíces: todos los elementos de $\mathbb{F}_{p^n}$.

Factorización de $x^{p^n} - x$

Teorema. El polinomio $x^{p^n} - x$ es el producto de todos los polinomios mónicos irreducibles sobre $\mathbb{F}_p$ cuyo grado divide a $n$:

$x^{p^n} - x = \prod_{d \mid n} \prod_{f \text{ irred. mónico de grado } d} f(x)$

Demostración. Un elemento $\alpha$ de la clausura algebraica $\overline{\mathbb{F}_p}$ es raíz de $x^{p^n}-x$ si y solo si $\alpha \in \mathbb{F}_{p^n}$. Esto ocurre si y solo si $[\mathbb{F}_p(\alpha):\mathbb{F}_p] \mid n$, es decir, el grado del polinomio mínimo de $\alpha$ sobre $\mathbb{F}_p$ divide $n$. Por tanto $x^{p^n} - x$ es divisible exactamente por los irreducibles de grado $d \mid n$. Como $x^{p^n}-x$ no tiene raíces múltiples (su derivada es $-1$, sin raíces comunes), la factorización es como producto sin repeticiones.

Conteo de polinomios irreducibles

Comparando grados en la factorización de $x^{p^n}-x$: $p^n = \sum_{d \mid n} d \cdot \pi_p(d)$ donde $\pi_p(d)$ es el número de polinomios mónicos irreducibles de grado $d$ sobre $\mathbb{F}_p$.

Por inversión de Möbius: $n \cdot \pi_p(n) = \sum_{d \mid n} \mu(n/d) p^d$, así

$\pi_p(n) = \frac{1}{n} \sum_{d \mid n} \mu(n/d)\, p^d$.

Para $n = 1$: $\pi_p(1) = p$ (hay $p$ polinomios lineales mónicos $x - a$ con $a \in \mathbb{F}_p$). Para $n = 2$: $\pi_p(2) = \frac{1}{2}(p^2 - p) = \frac{p(p-1)}{2}$. Para $n = 3$: $\pi_p(3) = \frac{1}{3}(p^3 - p) = \frac{p(p-1)(p+1)}{3}$. Con $p=2$: $\pi_2(2) = 1$, $\pi_2(3) = 2$, $\pi_2(4) = 3$.

El pequeño teorema de Fermat para polinomios

El **Pequeño Teorema de Fermat para $\mathbb{F}_p[x]$** dice: si $f \in \mathbb{F}_p[x]$ es irreducible de grado $d$ y $g \in \mathbb{F}_p[x]$ con $f \nmid g$, entonces $g^{p^d - 1} \equiv 1 \pmod{f}$.

Demostración: $\mathbb{F}_p[x]/(f) = \mathbb{F}_{p^d}$ es un cuerpo con $p^d$ elementos; su grupo multiplicativo tiene orden $p^d - 1$. La imagen de $g$ en este cociente es no nula (pues $f \nmid g$), así su $(p^d-1)$-ésima potencia es la identidad.

Aplicación: test de irreducibilidad. Para verificar que $f$ de grado $n$ es irreducible sobre $\mathbb{F}_p$: basta comprobar que $\gcd(x^{p^d} - x, f) = 1$ en $\mathbb{F}_p[x]$ para todo primo $d \mid n$, $d < n$. Si esto vale, $f$ no tiene factores de grado $d < n$, luego es irreducible.

Raíces de polinomios sobre $\mathbb{F}_p$ y relevancia olímpica

Teorema (Chevalley-Warning, enunciado). Si $f_1, \ldots, f_r \in \mathbb{F}_p[x_1, \ldots, x_s]$ son polinomios con $\sum_i \deg f_i < s$, entonces el número de soluciones comunes es divisible por $p$. En particular, si los polinomios tienen un cero en común (la solución trivial), tienen otro más.

El contexto olímpico más directo: el número de raíces de $f \in \mathbb{F}_p[x]$ es a lo sumo $\deg f$. Un polinomio de grado $d < p$ con $d+1$ raíces en $\mathbb{F}_p$ es divisible por $(x-r_1)\cdots(x-r_{d+1})$ en $\mathbb{F}_p[x]$, lo que es imposible salvo que el polinomio sea el cero.

Problema. Para $p$ primo, prueba que $\sum_{a=0}^{p-1} a^k \equiv -1 \pmod p$ si $(p-1) \mid k$, y $\equiv 0 \pmod p$ si $(p-1) \nmid k$ (para $k \ge 1$). Solución: usando que las potencias $a^{p-1} \equiv [a \ne 0] \pmod p$ por Fermat, y que $\sum_{a=1}^{p-1} a^k = \sum a^{k \bmod (p-1)}$ ya que el grupo multiplicativo tiene orden $p-1$. Esta es una aplicación directa de la estructura multiplicativa de $\mathbb{F}_p^*$.