Aplicaciones a divisibilidad

Una potencia muy grande, un residuo muy pequeño

Un problema clásico de olimpiada: ¿cuál es el residuo de $7^{100}$ al dividir por 6? Una calculadora no sirve: $7^{100}$ tiene más de 84 dígitos. La respuesta es que $7^{100} = (6+1)^{100}$, y el binomio de Newton hace el trabajo en dos líneas.

Este es el uso más directo del binomio en problemas de divisibilidad: escribir la base como $1 + m$ (o como $a + b$ donde $a$ o $b$ es múltiplo del divisor), expandir y observar qué términos son divisibles por la potencia que nos interesa.

La técnica funciona porque en la expansión de $(1 + mp)^n$, todos los términos excepto el primero ($1^n = 1$) contienen al menos un factor $p$, lo que controla perfectamente la divisibilidad.

Divisibilidad básica: $(1+p)^n \equiv 1 + np \pmod{p^2}$

Sea $p$ un entero cualquiera. Expandimos $(1 + p)^n$ por el binomio:

$$(1+p)^n = \binom{n}{0} + \binom{n}{1}p + \binom{n}{2}p^2 + \binom{n}{3}p^3 + \cdots$$

Los términos a partir del tercero contienen $p^2$ como factor (cada uno tiene $p^k$ con $k \ge 2$). Por tanto, módulo $p^2$:

$$(1+p)^n \equiv 1 + np \pmod{p^2}$$

Esta congruencia dice que al elevar $1+p$ a la $n$, el "error" respecto a 1 es exactamente $np$ módulo $p^2$. Ejemplo: $(1+3)^{10} = 4^{10} = 1048576$ y $1 + 10 \times 3 = 31$; efectivamente $4^{10} - 31 = 1048545 = 9 \times 116505$, que es divisible por $9 = 3^2$.

El pequeño teorema de Fermat vía el binomio

El pequeño teorema de Fermat dice: si $p$ es primo y $\gcd(a, p) = 1$, entonces $a^{p-1} \equiv 1 \pmod{p}$, o equivalentemente $a^p \equiv a \pmod{p}$.

Demostración combinatoria por el binomio (caso $a$ positivo entero): usamos inducción sobre $a$. Para $a=1$: $1^p = 1 \equiv 1 \pmod p$. Paso inductivo: asumiendo $a^p \equiv a \pmod p$, queremos probar $(a+1)^p \equiv a+1 \pmod p$.

Expandimos por el binomio: $(a+1)^p = \sum_{k=0}^p \binom{p}{k}a^k$. Para $0 < k < p$, el coeficiente $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ es divisible por $p$ (el numerador tiene el factor $p$ primo y el denominador no, pues $k < p$ y $p-k < p$). Así, todos los términos intermedios son $\equiv 0 \pmod p$, y queda $(a+1)^p \equiv a^p + 1^p \equiv a + 1 \pmod p$.

Este argumento muestra que $p \mid \binom{p}{k}$ para $1 \le k \le p-1$ cuando $p$ es primo, lo cual es en sí mismo un resultado valioso.

Técnica: residuo de una potencia grande

Para calcular $N^m \bmod d$, la estrategia con el binomio es escribir $N = d \cdot q + r$ (la división euclídea), de modo que $N \equiv r \pmod d$. Luego se escribe $N^m = (dq + r)^m$ y se expande:

$$(dq + r)^m = \sum_{k=0}^{m}\binom{m}{k}(dq)^k r^{m-k}$$

Todos los términos con $k \ge 1$ son divisibles por $d$ (pues contienen el factor $dq$). Así, $(dq+r)^m \equiv r^m \pmod d$. Hemos reducido el problema al residuo de $r^m$, donde $r < d$.

Si $r$ es pequeño (como 1, 2 o $-1$), el cálculo se hace trivial. Ejemplo: $7^{100} \bmod 6$. Como $7 = 6+1$, se tiene $7^{100} = (6+1)^{100} \equiv 1^{100} = 1 \pmod 6$. Respuesta: el residuo es $\boxed{1}$.

Problema olímpico resuelto: divisibilidad con el binomio

Problema (estilo ONEM regional): Demuestra que $8 \mid 3^{2n} - 1$ para todo entero $n \ge 1$.

Escritura clave: $3^{2n} = 9^n = (8+1)^n$. Expandimos por el binomio:

$$(8+1)^n = \sum_{k=0}^{n}\binom{n}{k}8^k = 1 + \binom{n}{1}\cdot 8 + \binom{n}{2}\cdot 64 + \cdots$$

Todos los términos con $k \ge 1$ son divisibles por $8$ (contienen el factor $8^k$ con $k \ge 1$). Por tanto $(8+1)^n \equiv 1 \pmod 8$, es decir $9^n - 1 \equiv 0 \pmod 8$, lo que prueba $8 \mid 3^{2n}-1$.

Extensión: ¿Cuándo divide $16$ a $3^{2n}-1$? Como $9 = 16 - 7$, se tiene $9 \equiv -7 \pmod{16}$, y $9^2 = 81 = 80+1 \equiv 1 \pmod{16}$, así $9^n \equiv 1 \pmod{16}$ si y solo si $n$ es par. Esto ilustra que la técnica del binomio es útil para módulos potencia de 2 también, aunque hay que elegir bien la escritura.