Lección 1.3: Criterios de divisibilidad — Espinoza Olimpiadas

¿Por qué existen los criterios?

Dado un número grande escrito en decimal, ¿cómo saber si es divisible por $7$ sin hacer la división? La respuesta reposa en un hecho sencillo: el número $N$ con cifras $a_k a_{k-1} \cdots a_1 a_0$ es igual a $a_k \cdot 10^k + a_{k-1} \cdot 10^{k-1} + \cdots + a_1 \cdot 10 + a_0$ . Todo criterio de divisibilidad explota el comportamiento de las potencias de $10$ módulo el divisor que nos interesa.

Esta perspectiva convierte los criterios de divisibilidad en ejercicios de aritmética modular disfrazados. Aunque en esta lección no usamos la notación $\equiv$ formalmente (eso viene en el capítulo 3), el razonamiento subyacente es exactamente congruencial.

Los criterios más usados en olimpiadas son los de $2, 3, 4, 5, 9, 11$ , y el de $7$ (que es más elaborado). Veremos cada uno con su demostración, porque entender el porqué es lo que permite generalizarlos cuando el problema lo pide.

Criterios por 2, 4, 5 y 25: las últimas cifras mandan

**Divisibilidad por $2$ :** un número es divisible por $2$ si y solo si su última cifra es $0, 2, 4, 6$ u $8$ . Demostración: $N = 10k + a_0$ y $2 \mid 10k$ siempre, así $2 \mid N \iff 2 \mid a_0$ .

**Divisibilidad por $4$ :** un número es divisible por $4$ si y solo si el número formado por sus dos últimas cifras es divisible por $4$ . Demostración: $N = 100k + (10a_1 + a_0)$ y $4 \mid 100k$ , así $4 \mid N \iff 4 \mid (10a_1 + a_0)$ . Similarmente, $8 \mid N \iff 8 \mid$ (últimas 3 cifras), pues $8 \mid 1000$ .

**Divisibilidad por $5$ :** $N$ es divisible por $5$ iff su última cifra es $0$ o $5$ (pues $5 \mid 10k$ y $5 \mid a_0 \iff a_0 \in \{0, 5\}$ ). Para $25$ : últimas dos cifras, pues $25 \mid 100$ . En general, $5^k \mid N$ depende solo de las últimas $k$ cifras porque $5^k \mid 10^k$ .

4\mid N \iff 4\mid\overline{a_1 a_0} \qquad 8\mid N \iff 8\mid\overline{a_2 a_1 a_0}

Criterios por 3, 9 y 11: la suma de cifras

**Divisibilidad por $9$ :** $N$ es divisible por $9$ si y solo si la suma de sus cifras $S(N) = a_k + a_{k-1} + \cdots + a_0$ es divisible por $9$ . Demostración: $10 \equiv 1 \pmod{9}$ , así $10^i \equiv 1^i = 1 \pmod{9}$ para todo $i \ge 0$ . Por tanto $N = \sum a_i \cdot 10^i \equiv \sum a_i \cdot 1 = S(N) \pmod{9}$ . Para $3$ : exactamente igual, pues $10 \equiv 1 \pmod 3$ .

**Divisibilidad por $11$ : el criterio es la suma alternada de cifras**: $a_0 - a_1 + a_2 - a_3 + \cdots$ . Si este valor es divisible por $11$ , entonces $11 \mid N$ . Demostración: $10 \equiv -1 \pmod{11}$ , así $10^i \equiv (-1)^i \pmod{11}$ . Por tanto $N \equiv \sum a_i \cdot (-1)^i = a_0 - a_1 + a_2 - \cdots \pmod{11}$ .

Ejemplo: $N = 85294$ . Suma de cifras: $8+5+2+9+4=28$ , que no es múltiplo de $9$ ni $3$ . Suma alternada: $4-9+2-5+8=0$ , que es múltiplo de $11$ , así $11 \mid 85294$ . Verificación: $85294 / 11 = 7754$ . ✓

9\mid N \iff 9\mid S(N) \qquad 11\mid N \iff 11\mid (a_0-a_1+a_2-\cdots)

El criterio por 7: un algoritmo de reducción

No existe un criterio por $7$ tan elegante como los anteriores porque $10 \not\equiv \pm 1 \pmod 7$ . Sin embargo, $10 \equiv 3 \pmod 7$ , lo cual permite un criterio iterativo útil: **retira la última cifra $a_0$ , y comprueba si $7 \mid (N' - 2a_0)$ **, donde $N'$ es el número sin la última cifra.

Por qué: $N = 10N' + a_0$ . Si $7 \mid N$ entonces $7 \mid 10N' + a_0$ . Como $\gcd(7,10)=1$ y $5 \cdot 10 = 50 \equiv 1 \pmod{7}$ , multiplicamos por $5$ : $7 \mid N \iff 7 \mid N' + 5a_0 \iff 7 \mid N' - 2a_0$ (pues $5 \equiv -2 \pmod 7$ ). Cada paso reduce el número de cifras en 1.

Ejemplo: $N = 1001$ . $N' = 100$ , $100 - 2 \cdot 1 = 98 = 14 \cdot 7$ . Sí, $7 \mid 1001 = 7 \cdot 143$ . Otro: $N = 2023$ . $N' = 202$ , $202 - 2\cdot 3 = 196 = 4\cdot49=4\cdot7^2$ . Sí, $7 \mid 2023 = 7\cdot289=7\cdot17^2$ .

Criterio general en base $b$ y combinaciones

Criterio general: sea $N = \sum_{i=0}^{k} a_i b^i$ la representación de $N$ en base $b$ . Si $d \mid b-1$ , entonces $d \mid N \iff d \mid \sum a_i$ (suma de cifras en base $b$ ), pues $b \equiv 1 \pmod{d}$ . Si $d \mid b+1$ , entonces $d \mid N \iff d \mid \sum (-1)^i a_i$ (suma alternada). Si $d \mid b^k$ , entonces solo importan las últimas $k$ cifras.

**Divisibilidad por $6 = 2 \cdot 3$ :** como $\gcd(2,3)=1$ , un número es divisible por $6$ si y solo si es divisible por $2$ y por $3$ simultáneamente. En general, si $d = p_1^{e_1} \cdots p_r^{e_r}$ con los $p_i^{e_i}$ coprimos dos a dos, entonces $d \mid N \iff p_i^{e_i} \mid N$ para todo $i$ . Esta descomposición reduce cualquier criterio compuesto a criterios primos.

Aplicación olímpica clásica: un número de 5 cifras $\overline{abcba}$ (capicúa) es siempre divisible por $11$ . Demostración: la suma alternada es $a - b + c - b + a = 2a - 2b + c$ . Hmm, eso no siempre es múltiplo de $11$ . Mejor: $\overline{abcba} = 10001a + 1010b + 100c$ . Ahora $10001 = 11 \cdot 909 + 2$ ... Verificamos con el criterio directo: $a_0=a, a_1=b, a_2=c, a_3=b, a_4=a$ , suma alternada $= a - b + c - b + a = 2a + c - 2b$ . Esto no siempre es $0 \pmod{11}$ . La conclusión es que los capicúas de 5 cifras no son siempre divisibles por $11$ , aunque los de 4 cifras $\overline{abba}$ sí lo son porque la suma alternada es $a-b-b+a = 2(a-b)$ , y... depende de $a, b$ . El ejemplo muestra que hay que calcular con cuidado y no confiar en intuiciones.

d\mid b-1 \implies \bigl(d\mid N \iff d\mid \textstyle\sum a_i\bigr)

Problemas tipo ONEM: últimas cifras y sumas

Problema 1: ¿Cuántos enteros del $1$ al $1000$ son divisibles por $3$ pero no por $9$ ? Los divisibles por $3$ son $\lfloor 1000/3 \rfloor = 333$ . Los divisibles por $9$ son $\lfloor 1000/9 \rfloor = 111$ . Los divisibles por $3$ pero no $9$ : $333 - 111 = 222$ .

Problema 2: El número $N = \underbrace{44\cdots4}_{2023}$ (dos mil veintitrés cuatros). ¿Es divisible por $9$ ? La suma de cifras es $4 \times 2023 = 8092$ . Verificamos: $8+0+9+2=19$ , $1+9=10$ , $1+0=1$ . Como $9 \nmid 1$ , concluimos $9 \nmid N$ . ¿Por $3$ ? $3 \nmid 1$ tampoco. Pero $8092/4 = 2023$ , $2+0+2+3=7$ , $7$ no es múltiplo de $3$ , así $3\nmid 8092$ , así $3\nmid N$ .

Problema 3 (ONEM estilo): Halla el mayor número de 6 cifras divisible por $8$ , $9$ y $11$ simultáneamente. El mcm de $8, 9, 11$ es $8 \cdot 9 \cdot 11 = 792$ (son coprimos de a pares). El mayor número de 6 cifras es $999999$ . Dividimos: $999999 / 792 = 1262.62\ldots$ Así el mayor múltiplo es $1262 \times 792 = 999504$ . Verificación rápida: últimas 3 cifras $504 = 63 \cdot 8$ ✓; suma de cifras $9+9+9+5+0+4=36$ , $9\mid 36$ ✓; suma alternada $4-0+5-9+9-9=0$ , $11\mid 0$ ✓.

Criterios de divisibilidad