Polinomios con valores enteros

Polinomios enteros: definición y ejemplos

Un polinomio $f(x)$ se llama polinomio entero (o polinomio de valores enteros) si $f(n) \in \mathbb{Z}$ para todo $n \in \mathbb{Z}$. Tener coeficientes enteros es suficiente pero no necesario: el polinomio $f(x) = \dfrac{x(x-1)}{2}$ tiene coeficientes no enteros ($\tfrac{1}{2}$) pero $f(n) = \binom{n}{2} \in \mathbb{Z}$ para todo entero $n$.

Los polinomios binomiales $\binom{x}{k} = \dfrac{x(x-1)(x-2)\cdots(x-k+1)}{k!}$ para $k = 0, 1, 2, \ldots$ son el ejemplo más importante de polinomios enteros sin coeficientes enteros. Forman una base del espacio de polinomios enteros: todo polinomio de grado $d$ que toma valores enteros en los enteros se escribe de manera única como $f(x) = c_0 \binom{x}{0} + c_1 \binom{x}{1} + \cdots + c_d \binom{x}{d}$ con $c_k \in \mathbb{Z}$.

Propiedad fundamental: si $f(x)$ tiene coeficientes enteros, entonces $f(a) - f(b) \equiv 0 \pmod{a-b}$ para cualesquiera enteros $a \neq b$. En particular, $f(a) \equiv f(b) \pmod{a-b}$. Esta es la "congruencia de valores de polinomios" y se usa extensamente en teoría de números olímpica.

Diferencias finitas y la fórmula de Newton hacia adelante

El operador diferencia $\Delta$ actúa sobre una sucesión $f$ por $\Delta f(n) = f(n+1) - f(n)$. Las diferencias sucesivas son $\Delta^k f(n) = \sum_{j=0}^k (-1)^{k-j}\binom{k}{j} f(n+j)$. Para polinomios, $\Delta$ reduce el grado en 1, de manera análoga a la derivada.

La fórmula de Newton hacia adelante expresa $f(n)$ en términos de las diferencias en $n = 0$: $f(n) = \sum_{k=0}^{d} \Delta^k f(0) \cdot \binom{n}{k}$. Esta fórmula muestra que los coeficientes en la base binomial son exactamente $c_k = \Delta^k f(0)$. En particular, si $f$ es un polinomio entero de grado $d$, entonces $\Delta^d f$ es una constante entera (el coeficiente líder multiplicado por $d!$).

Ejemplo: para $f(n) = n^2$, calculamos $\Delta f(n) = (n+1)^2 - n^2 = 2n+1$, $\Delta^2 f(n) = \Delta(2n+1) = 2$. Por Newton: $n^2 = \Delta^0 f(0)\binom{n}{0} + \Delta^1 f(0)\binom{n}{1} + \Delta^2 f(0)\binom{n}{2} = 0 + 1 \cdot n + 2 \cdot \dfrac{n(n-1)}{2} = n + n(n-1) = n^2$ ✓.

El resultado clave para olimpiadas: si $f(x)$ es un polinomio de grado $d$ con coeficientes racionales y $f(n) \in \mathbb{Z}$ para todo entero $n$, entonces $d! \cdot a_d \in \mathbb{Z}$, donde $a_d$ es el coeficiente líder. Por ejemplo, para un polinomio cuadrático $ax^2 + bx + c$ con valores enteros, se necesita $2a \in \mathbb{Z}$.

La congruencia de polinomios: $p(a) - p(b) \equiv 0 \pmod{a-b}$

Si $p(x) = a_n x^n + \cdots + a_1 x + a_0$ tiene coeficientes enteros, entonces para cualesquiera enteros $a$ y $b$: $(a - b) \mid (p(a) - p(b))$. La demostración usa que $a^k - b^k = (a-b)(a^{k-1} + a^{k-2}b + \cdots + b^{k-1})$, luego $p(a) - p(b) = \sum_{k=1}^n a_k(a^k - b^k)$, que es divisible por $(a-b)$.

Este resultado es extraordinariamente útil en competencias. Aplicación directa: si $p(x)$ es un polinomio con coeficientes enteros y $p(c) = d$ para algún entero $c$, entonces $p(x) = d$ no puede tener dos soluciones enteras $a \neq b$ a menos que $(a-b) \mid 0$. Más útil: si $p(a) = p(b)$, entonces $(a-b) \mid 0$, imposible si $a \neq b$. Es decir, $p$ es inyectivo en los enteros si $(a-b) \nmid (p(a)-p(b))$ implica $a = b$... Esto se usa para acotar soluciones.

Aplicación concreta: si $p(x)$ tiene coeficientes enteros y $p(n) = n^2 + 1$ para $n = 0, 1, 2$, ¿qué dice la congruencia sobre $p(3)$? Como $(3-0) \mid (p(3) - p(0))$ y $p(0) = 1$, tenemos $3 \mid (p(3) - 1)$. Como $(3-1) \mid (p(3)-p(1))$ y $p(1) = 2$, tenemos $2 \mid (p(3)-2)$, es decir $p(3)$ es par. Como $(3-2) \mid (p(3) - p(2))$ y $p(2) = 5$, no hay nueva restricción. Si $\deg p = 2$ y coincide con $n^2+1$ en tres puntos, entonces $p(x) = x^2 + 1$ y $p(3) = 10$.

Problema ONEM clásico: Si $p(x)$ es un polinomio con coeficientes enteros y $p(a) = p(b) = p(c) = 1$ para distintos enteros $a, b, c$, demuestra que $p$ no tiene raíces enteras. Supón que $p(r) = 0$ para $r \in \mathbb{Z}$. Entonces $(r-a) \mid (p(r)-p(a)) = 0 - 1 = -1$, luego $r - a \in \{1, -1\}$. Igualmente $r - b \in \{1,-1\}$ y $r - c \in \{1,-1\}$. Pero $a, b, c$ son distintos, entonces $r-a, r-b, r-c$ son tres enteros distintos, y no pueden ser todos en $\{1,-1\}$ (que solo tiene dos elementos). Contradicción.

Polinomios enteros y residuos: aplicaciones a olimpiadas

Resultado clave: si $p(x)$ es un polinomio con coeficientes enteros de grado $d$, entonces $p$ toma todos los residuos módulo $m$ cuando $x$ recorre $\{0, 1, \ldots, m-1\}$ si y solo si $p$ es inyectivo módulo $m$. Para polinomios cuadráticos, esto nunca ocurre con módulo par (pues el polinomio siempre omite ciertos residuos cuadráticos).

Ejemplo: demuestra que $n^2 + n + 1 \geq 1$ para todo entero $n$ y que este valor es siempre impar. Para la paridad: $n^2 + n = n(n+1)$ es siempre par (producto de consecutivos), luego $n^2+n+1$ es siempre impar. Para la desigualdad: $n^2+n+1 = (n+\tfrac{1}{2})^2 + \tfrac{3}{4} > 0$, o bien $n(n+1) \geq 0$ para $n \leq -1$ o $n \geq 0$, y $= -1 \cdot 0 = 0$ en ningún entero. El valor mínimo es en $n = 0$ o $n = -1$: $0 + 0 + 1 = 1$.

Otro resultado: el número de enteros en $\{0, 1, \ldots, n-1\}$ que son ceros de un polinomio de grado $d$ (módulo $n$) no supera $d$ si $n$ es primo. Esto es el **Teorema de Lagrange para polinomios módulo $p$**: un polinomio no nulo de grado $d$ con coeficientes en $\mathbb{Z}/p\mathbb{Z}$ tiene a lo más $d$ raíces. Este resultado es fundamental en teoría de números olímpica de nivel intermedio.