Divisibilidad

01Empezar con un paquete completo

1, 2, 3, … son enteros positivos y representan cantidades completas. Al añadir 0 y $-1$, $-2$, $-3$, … obtenemos los enteros, cuyo conjunto se suele representar por $\mathbb Z$. Los negativos pueden registrar movimientos en sentido contrario o disminuciones; no son medias fichas negativas. Por ahora el dibujo solo usa cantidades no negativas: cero o enteros positivos.

Pulsa primero «Siguiente paquete». Cada pulsación toma 4 fichas: un grupo cian es un paquete y las fichas grises esperan. Seis paquetes usan $6 \times 4 = 24$ fichas; de 26 quitamos 24 y quedan 2. Como 2 es menor que las 4 necesarias, no puede completarse otro paquete. El último paso marca esas 2 en dorado: ahora son el resto. Pulsa «Agrupar paquete a paquete» para iniciar, «Siguiente paquete» para avanzar uno y «Restablecer animación» para volver al principio; cambiar el total o el tamaño de paquete también reinicia.

Con 24 fichas y paquetes de 4 obtenemos exactamente 6 paquetes: $24 = 4 \times 6$, sin sobrantes. Escribimos «es un número entero de grupos» como $4 \mid 24$, leído «4 divide a 24». La barra no es división: expresa una afirmación verdadera o falsa. $4 \mid 24$ es verdadera y $4 \mid 26$ es falsa. La división $26 \div 4 = 6.5$ sí tiene valor, pero 6,5 no es entero y no cuenta paquetes completos.

Aquí $d$ es el tamaño del grupo, $n$ el total y $q$ el multiplicador entero. Esta línea es una definición: fija el significado de divisibilidad, no es un resultado que debamos demostrar. «Existe un entero $q$» solo exige encontrar uno que funcione, no que funcionen todos. Por ejemplo, $3 \mid 12$ se justifica con $q = 4$ porque $12 = 3 \times 4$. Para demostrar que 5 no divide a 12, examinamos múltiplos vecinos: $5 \times 2 = 10 < 12 < 15 = 5 \times 3$; no hay entero entre 2 y 3, así que no existe un $q$ válido.

Esta definición por igualdad va más allá de las fichas. $3 \mid 0$ porque $0 = 3 \times 0$; $3 \mid -12$ porque $-12 = 3 \times (-4)$; $-3 \mid 12$ porque $12 = (-3) \times (-4)$. Por tanto, todo entero no nulo divide a 0, y un signo negativo tampoco impide la divisibilidad. $d$ y $-d$ dividen exactamente los mismos números: basta cambiar el multiplicador $q$ por $-q$.

02Cuánto queda y por qué la respuesta es única

Las 26 fichas formaron 6 paquetes de 4 y sobraron 2, así que $26 = 4 \times 6 + 2$. Llamamos cociente al número de paquetes completos, 6, y resto a las 2 sobrantes. No basta escribir «divisor por cociente más resto» igual al total: 26 también es $4 \times 5 + 6$, pero con las 6 sobrantes aún cabe otro paquete. Para expresar que hemos terminado, el resto debe ser no negativo y estrictamente menor que el divisor.

Para un entero positivo $n$ podemos restar repetidamente $d$ hasta quedar por debajo de $d$. ¿Y con negativos? Al dividir $-17$ entre 5, $-2$ no sirve como resto estándar. Situamos $-17$ entre los múltiplos vecinos $-20$ y $-15$; desde $-20$ avanzamos 3 a la derecha hasta $-17$, de modo que $-17 = 5 \times (-4) + 3$. El cociente es $-4$ y el resto 3, cumpliendo aún $0 \le 3 < 5$. Es una posición dentro de un tramo de longitud 5 de la recta numérica.

¿Por qué cualquier entero $n$ puede escribirse así? Marca todos los múltiplos de $d$: …, $-2d$, $-d$, 0, $d$, $2d$, …; los vecinos están separados por $d$. $n$ queda entre algún múltiplo $dq$ y el siguiente $d(q + 1)$: puede coincidir con $dq$, pero aún no llega a $d(q + 1)$. Llamamos $r$ a la distancia desde $dq$ hacia la derecha hasta $n$. Entonces $n = dq + r$ y $0 \le r < d$. Así ocurría con $-17$: está entre $-20$ y $-15$, a distancia 3 de $-20$.

Por qué dos respuestas distintas no pueden cumplir la regla a la vez

Veámoslo primero con números: 26 también es $4 \times 5 + 6$, pero las 6 sobrantes permiten otro paquete y esa escritura no es válida. Exigir un resto menor que el tamaño del paquete deja una única respuesta. Repetimos ahora con letras; puedes omitirlo si todavía no lo entiendes. Supongamos que el mismo $n$ admite dos escrituras válidas $n = dq + r = dq' + r'$, con ambos restos entre 0 y $d - 1$. Restamos $dq'$ y $r$ para obtener $d(q - q') = r' - r$. La derecha está estrictamente entre $-d$ y $d$. La izquierda es un múltiplo entero de $d$: si $q - q' \ge 1$, es al menos $d$; si $q - q' \le -1$, es como máximo $-d$. Solo $q - q' = 0$ puede quedar en ese intervalo. Así, $q = q'$ y, al sustituir, $r = r'$. El cociente y el resto son únicos.

Por tanto, $d \mid n$ si y solo si el resto estándar es 0. Si el resto es 0, $n = dq$ cumple la definición de divisibilidad; a la inversa, si $n = dk$, $(k, 0)$ ya da un cociente y resto válidos, así que la unicidad obliga al resto estándar a ser 0. «Si y solo si» indica que ambos sentidos son válidos, y acabamos de comprobarlos por separado.

03Reescribir la divisibilidad como una igualdad que se puede usar

Cuando encuentres $d \mid a$, no veas la barra solo como un símbolo que memorizar. Sustitúyelo por $a = ds$ con $s$ entero y podrás sumar, restar y multiplicar. Por ejemplo, $6 \mid 18$ y $6 \mid 30$ dicen $18 = 6 \times 3$ y $30 = 6 \times 5$. Al sumar obtenemos $18 + 30 = 6 \times (3 + 5) = 6 \times 8$, así que 6 divide a su suma; al restar, $30 - 18 = 6 \times (5 - 3) = 6 \times 2$, así que también divide a su diferencia.

Escribamos el argumento general. Si $a = ds$ y $b = dt$, para cualesquiera enteros $u$ y $v$ tenemos $ua + vb = u(ds) + v(dt) = d(us + vt)$. El paréntesis $us + vt$ sigue siendo entero, porque sumas y productos de enteros dan enteros. Por tanto, $d \mid (ua + vb)$. $ua + vb$ se llama combinación lineal entera de $a$ y $b$: «combinación» indica que sumamos e «entera» que los multiplicadores son enteros. Pueden ser negativos, así que la resta ya está incluida.

También hay una regla para seguir una cadena de múltiplos. Si $a \mid b$ y $b \mid c$, escribimos $b = as$ y $c = bt$ y sustituimos la primera igualdad en la segunda: $c = (as)t = a(st)$. Como $st$ es entero, $a \mid c$. Por ejemplo, $3 \mid 12$ y $12 \mid 60$ implican $60 = 12 \times 5 = 3 \times 4 \times 5 = 3 \times 20$. Esta propiedad se llama transitividad, pero lo que permite usarla es la igualdad entera que acabamos de escribir.

04Por qué no se pierde el divisor común

A veces queremos repartir dos cantidades con el mismo tamaño de grupo. ¿Qué tamaños enteros positivos permiten repartir 18 y 30 sin restos? Los divisores de 18 son 1, 2, 3, 6, 9 y 18; los de 30 son 1, 2, 3, 5, 6, 10, 15 y 30. Se agrupan en pares $18 = 1 \times 18 = 2 \times 9 = 3 \times 6$ y $30 = 1 \times 30 = 2 \times 15 = 3 \times 10 = 5 \times 6$. Probando desde 1 hasta el número original y conservando solo el resto cero obtenemos la lista completa; la próxima sección explica por qué no hay divisores positivos mayores. Para 18, por ejemplo, $1 \times 18$, $2 \times 9$ y $3 \times 6$ contienen todos los pares. Los números 1, 2, 3 y 6 de ambas listas son divisores comunes, y el mayor es 6. Escribimos $\gcd (18,30) = 6$. $\gcd$ es la abreviatura inglesa de máximo común divisor.

¿Por qué existe ese «mayor»? Para enteros positivos $a$ y $b$, el 1 siempre divide a ambos, así que la lista no está vacía. Si el entero positivo $d$ divide a $a$, el $q$ de $a = dq$ debe ser positivo y al menos 1, de modo que $d \le a$. Igualmente, $d \le b$. Los divisores comunes positivos están entre 1 y el menor de los dos números: hay opciones finitas y existe una máxima. Si el máximo común divisor es 1, llamamos a los números coprimos; eso no exige que ambos sean primos.

Para números grandes, enumerar divisores es lento. Queremos sustituir la pareja por otra menor sin perder ningún divisor común. Probemos con 84 y 30: $84 = 2 \times 30 + 24$. Al quitar dos grupos de 30 queda 24. Cada pulsación de «Siguiente división» divide, a la misma escala, el dividendo en grupos completos y un resto dorado; después sustituye la pareja por «divisor y resto». Las igualdades se conservan abajo y puedes retroceder o reiniciar.

Demostrar que la sustitución conserva toda la lista de divisores comunes

Primero, si $d$ divide a 84 y 30, divide a su combinación lineal entera $84 - 2 \times 30 = 24$, así que $d$ es divisor común de 30 y 24. A la inversa, si $d$ divide a 30 y 24, divide a $2 \times 30 + 24 = 84$, así que $d$ también es divisor común de 84 y 30. No hemos conservado por casualidad solo el mayor: las dos listas de divisores comunes son idénticas, por lo que sus máximos coinciden.

El caso general sigue los mismos pasos: si un divisor común $d$ divide a $a$ y $b$, divide a $r = a - qb$; si divide a $b$ y $r$, divide a $a = qb + r$. Al repetir, 84 y 30 pasan a 30 y 24, después a 24 y 6, y finalmente a 6 y 0. Las tres líneas del modelo son $84 = 2 \times 30 + 24$, $30 = 1 \times 24 + 6$ y $24 = 4 \times 6 + 0$.

¿Por qué paramos aquí? Todo entero no nulo divide a 0, así que los divisores comunes positivos de 6 y 0 son precisamente los de 6, cuyo máximo es 6. Cada fila conserva los divisores comunes, de modo que el $\gcd (84,30)$ original también es 6. En general, $\gcd (a,0) = a$ para todo entero positivo $a$. Estas divisiones con resto repetidas forman el algoritmo de Euclides. Siempre termina: cada nuevo resto es un entero no negativo menor que el divisor positivo actual, y no puede haber un descenso estricto infinito dentro de 0, 1, …, $b - 1$. El resto cero no es la respuesta; lo es el último número no nulo que lo precede.

05Remontar el último resto hasta los números originales

Euclides no solo da la respuesta 6: registra cómo se obtiene cada resto de la pareja anterior. Queremos expresar ese 6 final solo con los números originales 84 y 30, para poder afirmar directamente que cualquier divisor de ambos también divide a 6. Empezamos en $6 = 30 - 24$, donde 24 aún no es uno de los originales; la primera línea dice $24 = 84 - 2 \times 30$, así que sustituimos la expresión completa.

El signo menos de la segunda línea afecta a todos los términos del paréntesis: restar «84 menos dos grupos de 30» equivale a restar 84 y devolver dos grupos de 30. Las tiras inferiores conservan el cálculo: 84 menos dos grupos de 30 da el resto; 30 menos ese resto da la nueva longitud; los tres grupos de 30 tras sustituir pueden unirse para comprobarlo. Los trazos rojos discontinuos representan longitudes restadas y el dorado la restante. Al elegir un paso, la imagen se detiene para compararla con cada línea.

Aquí $A$ y $B$ son los dos números conservados en ese paso; $u$, $v$, $s$ y $t$ cuentan sus respectivas cantidades de $a$ y $b$. Si hay demasiadas letras, mira primero el ejemplo numérico y vuelve después. ¿Por qué funciona la sustitución hacia atrás con otros enteros positivos? Inicialmente, $a = 1a + 0b$ y $b = 0a + 1b$ ya son combinaciones lineales enteras. Si los números actuales son $A = ua + vb$ y $B = sa + tb$, el siguiente resto $R = A - qB$ equivale a $(u - qs)a + (v - qt)b$. Sus nuevos coeficientes siguen siendo enteros. Así, los números iniciales y todos los conservados mantienen esta forma. A veces el último no nulo es uno inicial: con $6 = 2 \times 3 + 0$, por ejemplo, la respuesta 3 se expresa como $0 \times 6 + 1 \times 3$ y no como un nuevo resto no nulo. Junto con la demostración del algoritmo, concluimos que siempre existen enteros $u$ y $v$ tales que $au + bv = \gcd (a,b)$. Es la identidad de Bézout. Su razón está en el registro de sustituciones, no en una fórmula aparecida de la nada.

Cuándo se pueden separar los factores de un producto

Volvamos a la inferencia que no podíamos usar libremente. Supongamos ahora $\gcd (a,b) = 1$ y $a \mid bc$. Bézout da $au + bv = 1$. Multiplicamos por $c$ para hacer aparecer el producto conocido $bc$: $acu + bcv = c$. El término acu es múltiplo entero de $a$; bcv también, porque $bc = ak$ para algún entero $k$ y, por tanto, $bcv = a(kv)$. La suma da $c = a(cu + kv)$ con paréntesis entero, de modo que $a \mid c$. Cada paso usa las condiciones: si $\gcd (a,b)$ no fuera 1, no podríamos empezar con esa igualdad a 1.

Por ejemplo, 4 y 9 son coprimos porque $9 - 2 \times 4 = 1$: cualquier divisor común debe dividir a 1 y solo puede ser 1. Si sabemos $4 \mid 9c$, podemos concluir $4 \mid c$; concretamente, $c = 9c - 2 \times 4c$ y ambos términos son divisibles entre 4. En cambio, $6 \mid 2 \times 3$ no implica $6 \mid 3$ porque $\gcd (6,2) = 2$ y no se cumple la condición de coprimalidad.

06Por qué los primos son las piezas de la multiplicación

Tras escribir 60 como $6 \times 10$, podemos descomponer 6 en $2 \times 3$ y 10 en $2 \times 5$. Obtenemos $60 = 2 \times 3 \times 2 \times 5 = 2^{2} \times 3 \times 5$. $2^{2}$ abrevia el producto de dos factores 2. Los factores finales, mayores que 1, no tienen divisores positivos salvo 1 y ellos mismos: no pueden dividirse en dos enteros positivos mayores que 1. Se llaman números primos. Un entero mayor que 1 que no es primo es compuesto; el 1 queda aparte, ni primo ni compuesto.

Esto explica por qué excluimos el 1 de los primos: si fuera una pieza de la factorización, podríamos añadir arbitrariamente muchos factores 1 sin cambiar el número y la cantidad de piezas dejaría de ser única. La factorización prima solo registra factores mayores que 1 que cambian el producto. Debemos demostrar dos cosas: que todo entero mayor que 1 puede descomponerse hasta el final y que las piezas finales no dependen del camino elegido.

Primero, demostrar que siempre se puede descomponer: no queda ninguna excepción

Supongamos que algunos enteros mayores que 1 no pueden escribirse como producto de primos y elijamos el menor $N$, usando otra vez que todo conjunto no vacío de enteros positivos tiene mínimo. $N$ no puede ser primo, pues un primo ya es un producto de un solo factor primo. Así, $N$ es compuesto y se escribe $N = ab$ con $a$ y $b$ mayores que 1. Como $b \ge 2$, tenemos $a = N/b < N$; igualmente, $b < N$. $a$ y $b$ son menores que la mínima excepción $N$, por lo que ambos tienen factorización prima. Multiplicarlas produce una factorización de $N$ y contradice la suposición. No hay excepciones.

Después, demostrar la unicidad de las piezas: un factor primo debe aparecer en ambos lados

Añadamos la herramienta necesaria. Si un primo $p$ divide a $ab$, o bien $p$ divide a $a$, o bien $p$ no divide a $a$. En el primer caso ya tenemos el resultado. En el segundo, los únicos divisores positivos de $p$ son 1 y $p$, y $p$ no divide a $a$, así que $\gcd (p,a) = 1$. La cancelación coprima demostrada da $p \mid b$. Por tanto, un primo que divide al producto de dos números divide al menos a uno. Con más factores, separamos «primero» y «producto de los demás» y repetimos la misma regla sobre lo restante hasta encontrar un factor divisible entre $p$. Hay finitos factores, así que el proceso termina.

Supongamos ahora dos factorizaciones primas del mismo entero positivo. El primer primo de la izquierda, $p$, divide al producto izquierdo y, por igualdad, al derecho. La herramienta anterior implica que $p$ divide a algún primo derecho $q$. Los divisores positivos de $q$ son 1 y $q$; como $p > 1$, resulta $p = q$. Colocamos ese $q$ al principio y dividimos ambos miembros entre el no nulo $p$, cancelando un par igual. Repetimos hasta que un lado no tenga factores. El otro tampoco puede tenerlos: el producto vacío vale 1, mientras uno o más primos mayores que 1 tienen producto al menos 2. Ambas factorizaciones tienen, por tanto, los mismos primos con las mismas multiplicidades; solo puede variar el orden.

La existencia de factorización y su unicidad salvo el orden forman el teorema fundamental de la aritmética. El nombre identifica el resultado; lo justifican las dos demostraciones anteriores. Ahora podemos contar factores primos sin que el recuento cambie según la descomposición elegida.

07Copias comunes y copias suficientes

Compara la factorización $60 = 2^{2} \times 3 \times 5$ con $72 = 2^{3} \times 3^{2}$. La de 72 puede comprobarse paso a paso: $72 = 2 \times 36 = 2 \times 2 \times 18 = 2 \times 2 \times 2 \times 9 = 2^{3} \times 3^{2}$. Cada fila inferior contiene un solo primo y cada bloque representa una copia de ese factor. Observa cuántas copias aportan ambas columnas: dos de 2 y una de 3; el 5 no aparece en ambas. Los bloques cian emparejan las copias comunes.

¿Por qué las multiplicidades permiten comprobar divisibilidad? Si $d \mid a$, escribimos $a = dk$ con $k$ positivo. Factorizamos $d$ y $k$ y multiplicamos para obtener $a$. La unicidad dice que las copias de cada primo en $d$ más las de $k$ son exactamente las de $a$. Así, $d$ no puede contener más copias de ningún primo que $a$. A la inversa, si cada multiplicidad de $d$ no supera la de $a$, retiramos de la factorización de $a$ las copias necesarias para $d$; el producto restante es un entero $k$ y obtenemos $a = dk$. Ambos sentidos son válidos.

Para dividir a ambos números, de cada primo solo podemos tomar la menor multiplicidad. La parte común es $2^{2} \times 3 = 4 \times 3 = 12$. Sí divide a ambos: $60 = 12 \times 5$ y $72 = 12 \times 6$. Las multiplicidades de cualquier otro divisor común no la superan, de modo que todos los divisores comunes positivos dividen a 12 y no son mayores que 12. Esto demuestra $\gcd (60,72) = 12$, no es una conjetura basada en los bloques.

Invirtamos la pregunta: buscamos el menor entero positivo que sea múltiplo tanto de 60 como de 72. Se llama mínimo común múltiplo y se escribe $\operatorname{lcm}$. Para contener ambos, debemos tomar al menos la mayor multiplicidad de cada primo. Elegimos $2^{3} \times 3^{2} \times 5 = 8 \times 9 \times 5 = 360$ y obtenemos $360 = 60 \times 6 = 72 \times 5$. Cualquier otro múltiplo común positivo contiene al menos esas copias, así que es un múltiplo entero positivo de 360 y no puede ser menor. Por tanto, $\operatorname{lcm} (60,72) = 360$. Exigimos que sea positivo porque 0 también es múltiplo de ambos y cambiaría el problema.

En general, si un primo aparece $\alpha$ veces en $a$ y $\beta$ veces en $b$, el máximo común divisor toma la cantidad menor y el mínimo común múltiplo la mayor. Al multiplicarlos, la suma de cantidades es $\alpha + \beta$: si $\alpha \le \beta$, es $\alpha + \beta$; si $\beta < \alpha$, es $\beta + \alpha$. Es justamente la multiplicidad en $ab$. Vale para cada primo y la unicidad de factorización da $\gcd (a,b) \times \operatorname{lcm} (a,b) = ab$. En el ejemplo, $12 \times 360 = 4320 = 60 \times 72$.

08Construir demostraciones completas con estas herramientas

Ejemplo 1: dos enteros consecutivos no tienen ningún divisor común mayor que 1

Sea $n$ un entero positivo. Si un entero positivo $d$ divide a $n$ y $n + 1$, también divide a la combinación lineal $(n + 1) - n = 1$. Si el positivo $d$ divide a 1, los valores $d$ y $k$ de $1 = dk$ son al menos 1, y solo $d = k = 1$ permite producto 1. Así, todo divisor común positivo es 1, y 1 sí divide a ambos: $\gcd (n,n + 1) = 1$. No lo dedujimos de unos cuantos números vecinos: $n$ sigue siendo arbitrario y solo usamos que difieren en 1.

Ejemplo 2: el producto de tres enteros consecutivos siempre es divisible por 6

Sea $n$ cualquier entero, también negativo, y escribamos $P = n(n + 1)(n + 2)$. Busquemos primero un factor 2. La división con resto dice que $n$ deja 0 o 1 al dividir entre 2. Si $n = 2k$, $n$ contiene un factor 2; si $n = 2k + 1$, entonces $n + 1 = 2(k + 1)$ y también encontramos el factor. Por tanto, $P$ se escribe $2u$ con $u$ entero. Hemos cubierto todos los restos; no hay un tercer caso.

Busquemos un factor 3. $n$ solo puede dejar resto 0, 1 o 2: si $n = 3k$, $n$ es múltiplo de 3; si $n = 3k + 1$, $n + 2 = 3(k + 1)$; si $n = 3k + 2$, $n + 1 = 3(k + 1)$. Por tanto, $3 \mid P$. No basta decir sin justificar «tiene 2 y 3, así que tiene 6». Ya tenemos $P = 2u$ y $3 \mid 2u$. Como $\gcd (3,2) = 1$, la cancelación coprima da $3 \mid u$, es decir, $u = 3v$. Sustituyendo, $P = 2 \times 3v = 6v$ y, por tanto, $6 \mid P$.

Ejemplo 3: ninguna lista finita puede contener todos los primos

Supongamos que alguien afirma haber enumerado todos los primos: $p_{1}$, $p_{2}$, …, $p_{k}$. La lista es finita e incluye al menos el primo 2. Multiplicamos todos y sumamos 1 para obtener $N = p_{1}p_{2}\cdots p_{k} + 1$. Como $N > 1$, la existencia de factorización prima ya demostrada garantiza que $N$ tiene algún factor primo $q$. Si $q$ estuviera en la lista, dividiría al producto $p_{1}p_{2}\cdots p_{k}$; además $q \mid N$, así que $q$ dividiría a su diferencia 1. Pero el primo $q > 1$ no puede dividir a 1. Por tanto, $q$ no está en la lista, contradiciendo que estuviera completa. No puede haber solo un número finito de primos.

Solo hemos demostrado que $N$ tiene un factor primo nuevo, no que $N$ sea siempre primo. Por ejemplo, para 2, 3, 5, 7, 11 y 13, los productos sucesivos son 6, 30, 210, 2310 y 30030; al sumar 1 obtenemos 30031, y $30031 = 59 \times 509$ porque $59 \times (500 + 9) = 29500 + 531 = 30031$. Que sea compuesto no afecta al argumento: basta un factor primo nuevo. En una demostración de concurso debemos distinguir qué se ha probado realmente.

09Practicar explicando el razonamiento

Escribe la respuesta y la justificación de cada ejercicio y compáralas con la solución desplegable. Comprueba también si el razonamiento inverso funciona, si falta algún caso entero o de restos y si cada división tiene un divisor permitido.

Volvamos a los paquetes: ahora sabemos más que calcular restos. La definición de divisibilidad mediante múltiplos enteros permite combinar igualdades; esas combinaciones explican por qué Euclides conserva los divisores comunes; y la sustitución hacia atrás justifica cancelar factores en productos bajo coprimalidad. Esta cadena seguirá en Congruencias y Ecuaciones diofánticas. Las páginas posteriores recordarán los pasos necesarios al usarlos, sin exigir conectarlos solo de memoria.