Teoría de divisibilidad II

1.1 El problema: residuo de una potencia

Imagina que te piden hallar el residuo al dividir $8^{20}$ entre 7. Si intentas calcular $8^{20}$, obtienes un número enorme. Pero no hace falta: $8 = 7+1$. Entonces, $$8^{20} = (7+1)^{20}$$ Cuando desarrollamos $(7+1)^{20}$ por el binomio de Newton, todos los términos excepto el último son múltiplos de 7 porque contienen una potencia de 7. El último término es $1^{20} = 1$. Por lo tanto: $$(7+1)^{20} = \overset{\circ}{7} + 1$$ así que el residuo es 1.

Este es el corazón de los restos potenciales.

1.2 Propiedad fundamental de los restos potenciales

Teorema. Si $A = \overset{\circ}{n} + r$, entonces para todo entero positivo $k$, $$A^k = \overset{\circ}{n} + r^k$$ donde $r^k$ debe reducirse al residuo correspondiente si es mayor que $n$.

Justificación:
Escribimos $A = nq + r$, con $q$ entero. Al elevarlo a la $k$, el binomio de Newton da: $$(nq + r)^k = (nq)^k + \binom{k}{1} (nq)^{k-1} r + \binom{k}{2} (nq)^{k-2} r^2 + \cdots + \binom{k}{k-1} (nq) r^{k-1} + r^k$$ Todos los términos, salvo el último $r^k$, tienen un factor $nq$ y por lo tanto son múltiplos de $n$. Así, $$(nq + r)^k = \overset{\circ}{n} + r^k$$ como queríamos.

Ejemplo numérico:
¿Cuál es el residuo de $9^{30}$ al dividir entre 8?
Solución: $9 = 8+1$, entonces $9^{30} = (8+1)^{30} = \overset{\circ}{8} + 1^{30} = \overset{\circ}{8} + 1$. Residuo: $1$.

1.3 Potencias con residuo por exceso

Si el número se expresa como $A = \overset{\circ}{n} - r$, entonces al elevarlo a $k$ se obtiene: $$A^k = (\overset{\circ}{n} - r)^k = \overset{\circ}{n} + (-r)^k$$ Así, el signo depende de la paridad del exponente $k$:

• Si $k$ es par, $(-r)^k = r^k$, por lo tanto $A^k = \overset{\circ}{n} + r^k$.
• Si $k$ es impar, $(-r)^k = -r^k$, por lo tanto $A^k = \overset{\circ}{n} - r^k$. Al expresarlo como residuo por defecto, $\overset{\circ}{n} - r^k = \overset{\circ}{n} + (n - r')$, donde $r'$ es el residuo de $r^k$ módulo $n$.

Ejemplo:
Determinar el residuo de $6^{75}$ al dividir entre 7.

Solución: $6 = 7 - 1$, entonces $$6^{75} = (7-1)^{75} = \overset{\circ}{7} + (-1)^{75}$$ Como 75 es impar, $(-1)^{75} = -1$. Luego $$6^{75} = \overset{\circ}{7} - 1 = \overset{\circ}{7} + 6$$ porque $\overset{\circ}{7} - 1$ equivale a un múltiplo de 7 menos 1, que al sumarle 7 queda un múltiplo de 7 más 6. Residuo: $6$.

Nota importante: el residuo siempre debe ser un número entre $0$ y $n-1$. Si en algún cálculo obtienes $\overset{\circ}{n} + 10$ con $n=7$, debes reducirlo: $\overset{\circ}{7} + 10 = \overset{\circ}{7} + 3$, porque 10 deja residuo 3 al dividir entre 7.

1.4 Periodicidad de los restos potenciales

En muchos problemas el residuo de una potencia no es evidente de inmediato, pero las potencias sucesivas de un número módulo $n$ presentan un comportamiento cíclico. Observemos las potencias de 2 módulo 7:

$$\begin{aligned} 2^1 &\equiv 2 \pmod{7}\\ 2^2 &\equiv 4 \pmod{7}\\ 2^3 &\equiv 8 \equiv 1 \pmod{7}\\ 2^4 &\equiv 2 \pmod{7}\\ 2^5 &\equiv 4 \pmod{7}\\ 2^6 &\equiv 1 \pmod{7} \end{aligned}$$

Vemos que los residuos se repiten en ciclos de longitud 3: $2, 4, 1, 2, 4, 1, \dots$
Esto significa que para hallar $2^{100} \pmod{7}$, basta dividir el exponente entre 3:

$$100 = 3 \times 33 + 1$$ Entonces $$2^{100} = (2^3)^{33} \cdot 2^1 \equiv 1^{33} \cdot 2 = 2 \pmod{7}$$ Por lo tanto, el residuo de $2^{100}$ al dividir entre 7 es 2.

Este método de buscar el período de los restos es muy útil cuando la base no está inmediatamente relacionada con el módulo. En general, para hallar el período se calculan las potencias sucesivas hasta encontrar un residuo igual a 1, o se utiliza alguna propiedad particular.

Ciclo: 2 → 4 → 1 → 2 → 4 → 1 (se repite cada 3 potencias).
Para reducir exponentes grandes: divide el exponente entre 3; p. ej. 100 = 3×33 + 1 → 2^100 ≡ 1^33 · 2 ≡ 2 (mód 7).

Tabla de residuos de potencias de 2 módulo 7

Ejemplo adicional (con periodicidad).
Hallar el residuo de $3^{100}$ al dividir entre 7.
Observamos que $3^3 = 27 = 28 - 1 = \overset{\circ}{7} - 1$. Entonces $3^3 \equiv -1 \pmod{7}$. Elevando: $$3^{100} = (3^3)^{33} \cdot 3^1 \equiv (-1)^{33} \cdot 3 = -3 \equiv 4 \pmod{7}$$ porque $-3 + 7 = 4$. Residuo: $4$.

Este truco de buscar una potencia que dé $\pm 1$ módulo el divisor es muy frecuente.

Un criterio de divisibilidad es una regla que permite determinar si un número entero es divisible por otro sin efectuar la división, analizando solo sus cifras o pequeñas operaciones con ellas. En el sistema decimal, estos criterios se deducen de los restos de las potencias de 10 módulo el divisor.

Recordemos que un número $N$ de cifras $a_n a_{n-1} \dots a_2 a_1 a_0$ se escribe: $$N = a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \cdots + a_2 \cdot 10^2 + a_1 \cdot 10 + a_0$$ (donde $a_0$ es la cifra de las unidades, $a_1$ decenas, etc.).

2.1 Criterios para 2, 5 y 10

Observamos que $10 \equiv 0 \pmod{2}$ y $10 \equiv 0 \pmod{5}$. Por lo tanto, todas las potencias $10^k$ con $k \ge 1$ son 0 módulo 2 y módulo 5. Entonces: $$N \equiv a_0 \pmod{2} \quad \text{y} \quad N \equiv a_0 \pmod{5}$$ De aquí:

• Divisibilidad por 2: la última cifra debe ser par (0, 2, 4, 6, 8).
• Divisibilidad por 5: la última cifra debe ser 0 o 5.
• Divisibilidad por 10: como $N \equiv a_0 \pmod{10}$, debe ser $a_0 = 0$.

Ejemplo:
$12354$ es divisible por 2 porque termina en 4. No es divisible por 5 (no termina en 0 ni 5). No es divisible por 10.

2.2 Criterios para 4 y 8

Sabemos que $100 = 10^2 \equiv 0 \pmod{4}$. Entonces todas las potencias $10^k$ con $k \ge 2$ son 0 módulo 4. Luego: $$N \equiv a_1 \cdot 10 + a_0 \pmod{4}$$ Es decir, basta examinar el número formado por las dos últimas cifras ($a_1 a_0$).

• Divisibilidad por 4: el número formado por sus dos últimas cifras debe ser múltiplo de 4.

Para $8$, $1000 = 10^3 \equiv 0 \pmod{8}$, así que todas las potencias desde $10^3$ en adelante son 0 módulo 8. Entonces: $$N \equiv a_2 \cdot 100 + a_1 \cdot 10 + a_0 \pmod{8}$$

• Divisibilidad por 8: el número formado por sus tres últimas cifras debe ser múltiplo de 8.

Ejemplo:
$123456$ es divisible por 4 porque $56 \div 4 = 14$. Para 8, $456 \div 8 = 57$, también divisible. Entonces es divisible por 8.

2.3 Criterios para 3 y 9

Observamos que $10 \equiv 1 \pmod{9}$. Entonces $10^k \equiv 1^k = 1 \pmod{9}$ para todo $k$. Por lo tanto, en la representación: $$N \equiv a_n \cdot 1 + a_{n-1} \cdot 1 + \cdots + a_1 \cdot 1 + a_0 \equiv a_n + a_{n-1} + \cdots + a_1 + a_0 \pmod{9}$$ Es decir, $N$ deja el mismo residuo que la suma de sus cifras al dividir entre 9.

• Divisibilidad por 9: la suma de las cifras debe ser múltiplo de 9.

Como $10 \equiv 1 \pmod{3}$, exactamente el mismo razonamiento da:

• Divisibilidad por 3: la suma de las cifras debe ser múltiplo de 3.

Ejemplo:
$N = 2574$: suma de cifras $2+5+7+4 = 18$, que es múltiplo de 9 y de 3. Por lo tanto $2574$ es divisible por 9 y por 3.

Observación importante: Si un número es divisible por 9, automáticamente es divisible por 3. Lo recíproco no es cierto: 12 es divisible por 3 pero no por 9.

2.4 Criterio para 11

Aquí usamos que $10 \equiv -1 \pmod{11}$, porque $10 = 11 - 1$. Entonces: $$10^k \equiv (-1)^k \pmod{11}$$ Por lo tanto, $$N \equiv a_0 - a_1 + a_2 - a_3 + \cdots \pmod{11}$$ donde los signos alternan empezando por $+$ para las unidades, $-$ para las decenas, etc.

• Divisibilidad por 11: la suma alternada de las cifras (empezando por la cifra de las unidades con signo $+$) debe ser múltiplo de 11. También se enuncia como: la diferencia entre la suma de las cifras de posiciones impares y la suma de las cifras de posiciones pares es múltiplo de 11.

Ejemplo:
$N = 759$.
Suma alternada: $9 - 5 + 7 = 11$, que es múltiplo de 11. Por lo tanto 759 es divisible por 11 (759 = 11 × 69).

Otro ejemplo: $N = 123456$.
Suma alternada: $6 - 5 + 4 - 3 + 2 - 1 = 3$, no es múltiplo de 11, así que no es divisible por 11.

2.5 Criterios combinados (6, 12, 18, 15, etc.)

Para saber si un número es divisible por un divisor compuesto $D$, descomponemos $D$ en factores coprimos (o primos) y aplicamos los criterios correspondientes. La regla general es:

• Si $D = p \cdot q$ con $\gcd(p,q)=1$, entonces $N$ es divisible por $D$ si y solo si es divisible por $p$ y por $q$.

Ejemplos:

• Divisible por 6: divisible por 2 y por 3.
• Divisible por 12: divisible por 3 y por 4 (porque 12 = 3 × 4, y son coprimos).
• Divisible por 15: divisible por 3 y por 5.
• Divisible por 18: divisible por 2 y por 9.
• Divisible por 45: divisible por 5 y por 9.

Cuidado: No se puede combinar criterios si los factores no son coprimos. Por ejemplo, para saber si un número es divisible por 24, no basta que sea divisible por 4 y por 6, porque $4$ y $6$ no son coprimos (su MCD es 2). Un contraejemplo: 12 es divisible por 4 y por 6, pero no por 24. La forma correcta es $24 = 3 \times 8$, con 3 y 8 coprimos: divisible por 3 y por 8.

Ejemplo:
¿Es $1536$ divisible por 12?

• Divisible por 3: suma de cifras $1+5+3+6=15$, que es múltiplo de 3.
• Divisible por 4: últimas dos cifras $36$, que es múltiplo de 4.
  Entonces 1536 es divisible por 12. De hecho, $1536 = 12 \times 128$.

2.6 Criterios para 7, 13 y otros divisores usando restos de 10

Para divisores como 7 o 13 no hay una regla tan simple como las anteriores, pero se puede usar la misma idea: analizar los restos de $10^k$ módulo el divisor.

Potencias de 10 módulo 7:

$$\begin{aligned} 10^0 &= 1\\ 10^1 &= 10 \equiv 3 \pmod{7}\\ 10^2 &= 100 \equiv 2 \pmod{7}\\ 10^3 &= 1000 \equiv 6 \equiv -1 \pmod{7}\\ 10^4 &\equiv -10 \equiv -3 \equiv 4 \pmod{7}\\ 10^5 &\equiv -100 \equiv -2 \equiv 5 \pmod{7}\\ 10^6 &\equiv -1000 \equiv 1 \pmod{7} \end{aligned}$$

Observamos que el período es 6 para 7. Entonces, para un número $N = \overline{a_n \dots a_0}$, su residuo módulo 7 se puede calcular como: $$N \equiv a_0 + 3a_1 + 2a_2 + 6a_3 + 4a_4 + 5a_5 + a_6 + 3a_7 + \cdots \pmod{7}$$ pero esta suma ponderada rara vez se usa manualmente; es más práctico separar en bloques de tres cifras.

Método de bloques de tres cifras para 7, 11 y 13:
Observa que $$1001 = 7 \times 11 \times 13$$ Entonces $10^3 \equiv -1$ módulo 7, 11 y 13. Por lo tanto, $$N = \overline{a_n \dots a_0} = a_0 a_1 a_2 \cdot 10^0 + a_3 a_4 a_5 \cdot 10^3 + a_6 a_7 a_8 \cdot 10^6 + \cdots$$ y como $10^3 \equiv -1$, $10^6 \equiv 1$, $10^9 \equiv -1$, etc., se obtiene: $$N \equiv (\text{bloque 1}) - (\text{bloque 2}) + (\text{bloque 3}) - (\text{bloque 4}) + \cdots \pmod{7,11,13}$$ donde los bloques son grupos de tres cifras desde la derecha.

Ejemplo:
¿Es $N = 123456$ divisible por 7?
Bloques desde la derecha: $456$ y $123$.
Alternando: $456 - 123 = 333$.
Como $333$ no es múltiplo de 7 ($333=7×47+4$), $N$ no es divisible por 7.
Para 11: $456 - 123 = 333$, $333$ no es múltiplo de 11, así que no es divisible por 11.
Para 13: $333$ no es múltiplo de 13, así que no es divisible por 13.

Ejemplo de que sí funciona:
$N = 123123$. Bloques: $123$ y $123$. Diferencia: $123 - 123 = 0$, que es divisible por 7, 11 y 13. Por lo tanto $123123$ es divisible por 7, 11 y 13 (y por su producto $1001$).

3.1 Representación posicional en base $b$

En un sistema de numeración de base $b$, un número $$(a_n a_{n-1} \dots a_2 a_1 a_0)_b$$ tiene cifras $a_i$ entre 0 y $b-1$, y su valor decimal es: $$N = a_n \cdot b^n + a_{n-1} \cdot b^{n-1} + \cdots + a_2 \cdot b^2 + a_1 \cdot b + a_0$$ La misma idea de criterios por restos de potencias de la base se puede aplicar.

3.2 Divisibilidad por $b$, $b-1$ y $b+1$

Por $b$:
Como $b \equiv 0 \pmod{b}$, todas las potencias $b^k$ con $k \ge 1$ son 0. Entonces $N \equiv a_0 \pmod{b}$. Por lo tanto:

• En base $b$, un número es divisible por $b$ si su última cifra es 0.

Por $b-1$:
Como $b \equiv 1 \pmod{b-1}$, se tiene $b^k \equiv 1$. Entonces: $$N \equiv a_n + a_{n-1} + \cdots + a_1 + a_0 \pmod{b-1}$$

• En base $b$, un número es divisible por $b-1$ si la suma de sus cifras es múltiplo de $b-1$.

Por $b+1$:
Como $b \equiv -1 \pmod{b+1}$, entonces $b^k \equiv (-1)^k$. Así: $$N \equiv a_0 - a_1 + a_2 - a_3 + \cdots \pmod{b+1}$$

• En base $b$, un número es divisible por $b+1$ si la suma alternada de sus cifras es múltiplo de $b+1$.

Ejemplo en base 6:
Consideremos $(2315)_6$.

• Suma de cifras: $2+3+1+5 = 11$. Para $b-1=5$, $11 \equiv 1 \pmod{5}$. Entonces el residuo al dividir entre 5 es 1.
• Suma alternada desde las unidades: $5 - 1 + 3 - 2 = 5$. Para $b+1=7$, el residuo al dividir entre 7 es 5.

Estos criterios son análogos a los de 9 y 11 en el sistema decimal, porque en base 10, $b-1 = 9$ y $b+1 = 11$. Por eso, el criterio del 9 es “suma de cifras” y el del 11 es “suma alternada”.

3.3 Divisores de potencias de la base

Si un divisor $d$ divide exactamente a una potencia de la base, $d \mid b^k$, entonces las potencias $b^k$ en adelante son 0 módulo $d$. Por lo tanto, solo importan las últimas $k$ cifras.

Ejemplos:

• En base 8 ($b=8$), el número es divisible por 4 si su última cifra es divisible por 4, porque $4 \mid 8$.
• En base 16, el número es divisible por 256 ($16^2$) si el número formado por sus dos últimas cifras es divisible por 256.
• En base 10, esto da los criterios para 2, 5, 4, 8, etc., ya que $2 \mid 10$, $4 \mid 100$, $8 \mid 1000$, etc.

3.4 Última cifra en otras bases: una aplicación de restos potenciales

En muchos problemas se pide hallar la última cifra de $a^n$ al expresarlo en base $b$. La última cifra es el residuo de dividir $a^n$ entre $b$, es decir, $a^n \pmod{b}$. Luego se aplican restos potenciales.

Ejemplo:
Hallar la última cifra de $12^{20}$ al expresarlo en base 7.
Esto es hallar $12^{20} \pmod{7}$.
Como $12 = 7+5$, entonces $12 \equiv 5 \pmod{7}$. Además $5 = 7-2$, así que $5 \equiv -2 \pmod{7}$. Entonces $$12^{20} \equiv (-2)^{20} = 2^{20} \pmod{7}$$ Ahora, $2^3 = 8 \equiv 1 \pmod{7}$. Por lo tanto, $2^{20} = (2^3)^6 \cdot 2^2 \equiv 1^6 \cdot 4 = 4 \pmod{7}$.
La última cifra en base 7 es 4.

4.1 Principio de Arquímedes

Enunciado: Si $A \cdot B = \overset{\circ}{n}$ y $\gcd(A,n)=1$ (es decir, $A$ y $n$ son coprimos), entonces $B = \overset{\circ}{n}$.

Interpretación: Si el producto de dos números es múltiplo de $n$ y uno de los factores no comparte divisores con $n$, entonces el otro factor debe ser múltiplo de $n$.

Ejemplo:
Si $7x = \overset{\circ}{5}$, como $\gcd(7,5)=1$, entonces $x = \overset{\circ}{5}$.

Ejemplo en problema:
Si $11 \cdot ab = \overset{\circ}{9}$, y $11$ es coprimo con $9$, entonces $ab = \overset{\circ}{9}$.

Esta propiedad es muy útil para resolver ecuaciones donde se busca el valor de una variable bajo condiciones de divisibilidad.

4.2 Múltiplos comunes con restos

Si un número $N$ deja el mismo residuo $r$ al dividirse entre varios módulos $a$, $b$, $c$, entonces $N$ se puede expresar como: $$N = \operatorname{MCM}(a,b,c) \cdot k + r$$ para algún entero $k$. Esto permite acotar la búsqueda de valores de $N$.

Ejemplo:
Si $N$ deja residuo 3 al dividir entre 4, 5 y 6, entonces $$N = \operatorname{MCM}(4,5,6) + 3 = 60k + 3$$ Así, los posibles valores son 3, 63, 123, 183, etc.

También se puede generalizar con distintos restos por exceso/defecto, transformándolos a un mismo residuo.