División y teorema del resto

El algoritmo de división de polinomios

Dado cualquier polinomio $p(x)$ de grado $n$ y un divisor $d(x)$ de grado $m \leq n$, existe una única escritura $p(x) = d(x) \cdot q(x) + r(x)$ donde $q(x)$ es el cociente (grado $n - m$) y $r(x)$ es el resto (con $\deg r < \deg d$, o bien $r = 0$). Esta es la división euclídea de polinomios, análoga a la división entera.

El algoritmo es la división larga de polinomios, que se ejecuta column por columna: en cada paso, se divide el término líder del dividendo actual por el término líder del divisor, se multiplica el resultado por el divisor entero, y se resta. Se repite hasta que el grado del remanente sea menor que el del divisor.

Ejemplo: divide $p(x) = x^3 + 2x^2 - x + 5$ entre $d(x) = x - 2$. Primer paso: $x^3 \div x = x^2$; $x^2(x-2) = x^3 - 2x^2$; resta: $4x^2 - x + 5$. Segundo paso: $4x^2 \div x = 4x$; $4x(x-2) = 4x^2 - 8x$; resta: $7x + 5$. Tercer paso: $7x \div x = 7$; $7(x-2) = 7x - 14$; resta: $19$. Resultado: $p(x) = (x-2)(x^2 + 4x + 7) + 19$.

El resto $19$ se puede obtener sin hacer la división completa, usando el teorema del resto: $p(2) = 8 + 8 - 2 + 5 = 19$ ✓. Esto ahorra mucho tiempo en olimpiadas.

El teorema del resto y el teorema del factor

El teorema del resto afirma que el resto de dividir $p(x)$ entre $(x - a)$ es exactamente $p(a)$. La demostración ya la vimos: $p(x) = (x-a)q(x) + R$, evaluando en $x = a$ da $p(a) = R$.

El teorema del factor es el corolario inmediato: $(x-a)$ divide exactamente a $p(x)$ (es decir, $R = 0$) si y solo si $p(a) = 0$. Este teorema es el motor de la factorización de polinomios en olimpiadas: para factorizar $p(x)$, buscamos un valor $a$ con $p(a) = 0$, luego dividimos $p(x)$ entre $(x-a)$, y repetimos con el cociente.

En olimpiadas, los candidatos naturales para $a$ son los divisores del término constante (cuando el polinomio tiene coeficientes enteros). Si $p(x) = x^n + \cdots + a_0$ y $a \in \mathbb{Z}$ es raíz, entonces $a \mid a_0$. Esta es la versión mónica del criterio de raíces racionales.

Ejemplo olímpico: factoriza $p(x) = x^4 - 1$. Probamos $p(1) = 0$, luego $(x-1) \mid p(x)$. División: $x^4-1 = (x-1)(x^3+x^2+x+1)$. En el cúbico, $p(-1) = -1+1-1+1 = 0$, luego $(x+1) \mid (x^3+x^2+x+1)$. Cociente: $x^2+1$ (irreducible en $\mathbb{R}$). Factorización completa: $x^4-1 = (x-1)(x+1)(x^2+1)$.

División por polinomios cuadráticos

Cuando el divisor es cuadrático, por ejemplo $d(x) = x^2 - bx + c$, el resto es de la forma $r(x) = Ax + B$. Para hallar $A$ y $B$ sin hacer la división completa, se utilizan las dos raíces $\alpha, \beta$ de $d(x)$ (reales o no): $p(\alpha) = A\alpha + B$ y $p(\beta) = A\beta + B$. Esto da un sistema lineal en $A$ y $B$.

Ejemplo: halla el resto de dividir $p(x) = x^{10}$ entre $d(x) = x^2 - 1$. Las raíces de $d$ son $\alpha = 1$ y $\beta = -1$. El resto es $Ax + B$ con $p(1) = A + B = 1$ y $p(-1) = -A + B = 1$. Sumando: $2B = 2$, luego $B = 1$. Restando: $2A = 0$, luego $A = 0$. Resto: $r(x) = 1$. Verificación: $x^{10} - 1 = (x^2-1)(x^8 + x^6 + x^4 + x^2 + 1)$ ✓.

Esta técnica es especialmente poderosa cuando $p(x) = x^n$ y el divisor tiene raíces especiales como $\pm 1$, las raíces de la unidad, o números enteros pequeños. Es mucho más eficiente que ejecutar la división larga de un polinomio de grado 10.

Otro caso frecuente en olimpiadas: halla el resto de $x^{100} + x^{50} + 1$ al dividir entre $x^2 + x + 1$. Las raíces de $x^2+x+1=0$ son $\omega = e^{2\pi i/3}$ y $\bar{\omega}$. Como $\omega^3 = 1$, tenemos $\omega^{100} = \omega^1 = \omega$ (pues $100 = 33 \cdot 3 + 1$), $\omega^{50} = \omega^2$ (pues $50 = 16 \cdot 3 + 2$). Entonces $p(\omega) = \omega + \omega^2 + 1 = 0$ (pues $1 + \omega + \omega^2 = 0$). Igualmente $p(\bar\omega) = 0$. El resto $Ax + B$ satisface $A\omega + B = 0$ y $A\bar\omega + B = 0$, lo que implica $A = 0$ y $B = 0$. El resto es $0$, es decir, $x^2+x+1 \mid x^{100}+x^{50}+1$.

Aplicaciones olímpicas de la división polinomial

**Divisibilidad por $(x-1)^2$:** el polinomio $p(x)$ es divisible por $(x-a)^2$ si y solo si $p(a) = 0$ y $p'(a) = 0$ (la derivada también se anula en $a$). Para $p(x) = x^n - nx + (n-1)$: $p(1) = 1 - n + n - 1 = 0$ ✓. $p'(x) = nx^{n-1} - n$, y $p'(1) = n - n = 0$ ✓. Por lo tanto $(x-1)^2 \mid x^n - nx + (n-1)$ para todo entero $n \geq 2$.

Problema ONEM tipo: demuestra que $(x+y)$ divide a $x^n + y^n$ para todo $n$ impar positivo. Evaluando en $x = -y$: $p(-y) = (-y)^n + y^n = -y^n + y^n = 0$ (pues $n$ es impar). Por el teorema del factor, $(x - (-y)) = (x+y)$ divide a $x^n + y^n$. ✓

Esta es una de las identidades más usadas en olimpiadas: $x^n + y^n = (x+y)(x^{n-1} - x^{n-2}y + \cdots + y^{n-1})$ para $n$ impar. Junto con $x^n - y^n = (x-y)(x^{n-1} + x^{n-2}y + \cdots + y^{n-1})$ para todo $n$, forman el arsenal básico de divisibilidad polinomial.