El Algoritmo de la División

En esta clase desarrollaremos el algoritmo de la división como el principio que formaliza, para enteros, la descomposición única b=qa+r con 0\le r<|a|. Se demuestra primero la existencia del cociente y el resto y luego su unicidad. Finalmente, se interpreta el significado del resto, se vincula la teoría con el algoritmo largo de la división como procedimiento de cálculo, y se anticipa su conexión natural con la aritmética modular y aplicaciones computacionales.

Objetivos de Aprendizaje

Al completar esta clase el estudiante será capaz de:

1. Identificar los conceptos y roles básicos de la división entera (dividendo, divisor, cociente, resto) y la noción de divisibilidad como caso exacto.
2. Explicar el enunciado del algoritmo/teorema de la división euclidiana, incluyendo las condiciones que fijan el resto (0\le r<|a|) y su propósito para evitar ambigüedades.
3. Aplicar la descomposición euclidiana b=qa+r para determinar q y r en ejemplos concretos, verificando la cota del resto.
4. Analizar el tratamiento de casos según el signo del dividendo y del divisor, justificando por qué la convención euclidiana mantiene un resto no negativo.
5. Ejecutar el algoritmo largo de la división como procedimiento mecánico basado en representación posicional para obtener q y r.

ÍNDICE DE CONTENIDOS:
División y divisibilidad
Teorema de la división euclidiana
Demostración de la división euclidiana
Interpretación del cociente y el resto
Algoritmo largo de la división
Conclusión
Ejercicios propuestos y resueltos

División y divisibilidad

En aritmética, la divisibilidad describe el caso «exacto»: a\mid b significa que b se escribe exactamente como múltiplo de a. Sin embargo, aunque no siempre hay divisibilidad entre dos enteros cualesquiera, aún podemos preguntarnos «cuántas veces calza un número dentro de otro y, si no lo hace exactamente, qué es lo que sobra». Este es el contexto en el que surge el algoritmo de la división, que garantiza que un entero cualquiera b puede escribirse como un múltiplo de a más un «resto».

A modo de ejemplo, consideremos a=3 y b=16. Es claro que 3 no divide a 16. Sin embargo, sí es posible encontrar un cociente y un resto para la operación de división, porque

16 = 5\cdot 3 + 1

En consecuencia, al dividir b=16 por a=3 (donde b es el dividendo y a es el divisor), representado por 16/3 o 16\div 3, se obtiene como cociente q=5 y como resto r=1. En general, el algoritmo de la división afirma que, para cualesquiera enteros a (divisor) y b (dividendo) con a\neq 0, existen enteros únicos q y r tales que

b=qa+r,\qquad 0\le r<|a|

En este ejemplo, 16=3\cdot 5+1, y la condición 0\le r<|a| se cumple porque 0\le 1<3. Esta formulación evita ambigüedades cuando el divisor (o el dividendo) puede ser negativo y garantiza que el resto sea siempre no negativo y estrictamente menor que el valor absoluto del divisor.

Teorema de la división euclidiana

El resultado de aplicar el algoritmo de la división es lo que se conoce como división euclidiana y se sustenta en el siguiente resultado.

Teorema: Sean a,b\in\mathbb{Z} con a\neq 0. Entonces existen q,r\in\mathbb{Z} únicos tales que

b=qa+r,\qquad 0\le r<|a|.

El entero q se llama cociente y r se llama resto de la división de b por a.

Demostración de la división euclidiana

Esta demostración se divide en dos partes: primero se demuestra que el cociente y el resto existen; y luego, dado que existen, son únicos.

Existencia

Sean a,b\in\mathbb{Z} con a\neq 0 y definamos d=|a|, de modo que d>0. Probaremos primero el caso b\ge 0: mostraremos que existen q,r\in\mathbb{Z} tales que b=dq+r y 0\le r<d. Luego trataremos el caso b<0. Al final, reemplazaremos d por |a| para obtener la forma b=qa+r con 0\le r<|a|.

Para b\in\mathbb{Z} con b\ge 0, establecemos la proposición P(b): «existen q,r\in\mathbb{Z} tales que b=dq+r y 0\le r<d». Demostraremos por inducción que P(b) es válida para todo b\ge 0.

Caso base: Para b=0, tomando q=0 y r=0 se obtiene 0=d\cdot 0+0 y 0\le 0<d. Por lo tanto, P(0) es verdadera.

Paso inductivo: Sea k\ge 0 y supongamos que P(k) es verdadera. Entonces existen q,r\in\mathbb{Z} tales que

k=dq+r,\qquad 0\le r<d.

Sumando 1 a ambos lados se obtiene

k+1=dq+(r+1).

Además, de 0\le r<d se sigue que r+1\le d. En consecuencia, solo pueden ocurrir los casos r+1<d o r+1=d.

Caso 1: Si r+1<d, definimos q'=q y r'=r+1. Entonces

k+1=dq'+r',\qquad 0\le r'<d.

Caso 2: Si r+1=d, entonces k+1=dq+d=d(q+1)+0. Definimos q'=q+1 y r'=0, y se cumple

k+1=dq'+r',\qquad 0\le r'<d.

En ambos casos hemos construido enteros q',r' tales que k+1=dq'+r' y 0\le r'<d. Por lo tanto, P(k+1) es verdadera. Concluimos por inducción que P(b) vale para todo b\ge 0.

Ahora consideremos el caso b<0. Entonces -b>0. Aplicando el resultado anterior a -b, existen q,r\in\mathbb{Z} tales que

-b=dq+r,\qquad 0\le r<d.

Multiplicando por -1 se obtiene

b=-dq-r.

Si r=0, basta tomar q_1=-q y r_1=0, con lo cual b=dq_1+r_1 y 0\le r_1<d.

Si r>0, definimos q_1=-q-1 y r_1=d-r. Como 0<r<d, se tiene 0<d-r<d, es decir, 0\le r_1<d. Además,

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

En consecuencia, para todo b\in\mathbb{Z} existen q_1,r_1\in\mathbb{Z} tales que b=dq_1+r_1 y 0\le r_1<d.

Finalmente, recordemos que d=|a|. Si a>0, entonces d=a y la igualdad b=dq_1+r_1 se escribe como b=aq_1+r_1, con 0\le r_1<|a|.

Si a<0, entonces d=-a y b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1. Definiendo q=-q_1 y r=r_1, se obtiene

b=qa+r,\qquad 0\le r<|a|.

Con esto queda probada la existencia de q y r para cualesquiera a,b\in\mathbb{Z} con a\neq 0.

Unicidad

Supóngase que existen q,q',r,r'\in\mathbb{Z} tales que

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

Restando ambas expresiones se obtiene

a(q-q')=r'-r.

Como 0\le r,r'<|a|, se cumple |r'-r|<|a|. En cambio, el miembro izquierdo es múltiplo de a, y por tanto también es múltiplo de |a|. El único múltiplo entero de |a| con valor absoluto estrictamente menor que |a| es 0; en efecto, si |a| m \neq 0 con m\in\mathbb{Z}, entonces \big| |a| m \big| \ge |a| . Por consiguiente, r'-r=0, es decir r=r', y al sustituir en b=qa+r se deduce q=q'. Por esto la descomposición es única.

Interpretación del cociente y el resto

• Qué significa «resto». Si b=qa+r, entonces r=b-qa es lo que «sobra» al quitarle a b el múltiplo qa. En otras palabras, r es el residuo de ajustar b a la rejilla de múltiplos de a.
• Por qué se exige 0\le r<|a|. Sin esta condición, el par (q,r) no sería único. En efecto, si b=qa+r, entonces también b=a(q+1)+(r-a). La condición 0\le r<|a| fuerza al resto a vivir en una ventana fija \{0,1,2,\dots,|a|-1\}, y eso bloquea las infinitas «re-etiquetaciones» del mismo número.
• Qué pasa si a es negativo. El teorema sigue siendo válido sin cambios: el resto se mantiene no negativo y acotado por |a|. Esto es relevante porque algunos lenguajes de programación usan truncamiento hacia cero y pueden producir restos negativos, mientras que en matemáticas se adopta la convención 0\le r<|a| para que el resto sea un representante «estándar».

  Además, cuando a>0, el cociente coincide con el piso:

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

Algoritmo largo de la división

A partir de la división euclidiana es posible implementar el algoritmo largo de la división, aprovechando la representación posicional de los números. Este algoritmo es una técnica de cálculo que permite encontrar rápidamente los valores q y r cuando se desea calcular b\div a con a,b\in\mathbb{Z} y a\neq 0.

Para describirlo, revisemos primero algunos ejemplos que ilustran el proceso y las posibles situaciones durante la ejecución del algoritmo.

1. Supongamos que queremos calcular 57\div 4. Aquí 57 es el dividendo y 4 el divisor. Para lograrlo realizaremos la siguiente secuencia de cálculos:

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{Escribir la operación de división.} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{Separar el primer prefijo (desde la izquierda) del dividendo que}\\ &\text{sea mayor o igual que el divisor, en este caso 5.} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{Pensar en el mayor número que, multiplicado por $4$,}\\ &\text{resulte menor o igual que $5$ y escribirlo a la derecha de la igualdad. Es 1.}\\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{Multiplicar el resultado por el divisor y restarlo del valor seleccionado.} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{Seleccionar y «bajar» el siguiente dígito.} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{Repetir la secuencia con el último número obtenido.} \end{array}

   El algoritmo finaliza cuando se han agotado los dígitos por «bajar», entregando como resultado el cociente q=14 y el resto r=1. En particular, el resto será siempre menor que el divisor.

2. Supongamos que queremos calcular 132\div 5. Para lograrlo realizaremos la siguiente secuencia de cálculos:

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{Separar el primer prefijo del dividendo y buscar algún natural que,}\\ & \text{multiplicado por 5, sea menor o igual que él. Si no se puede,}\\ & \text{incorporar el siguiente dígito hasta que se pueda.} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{Cuando el paso anterior funcione, ejecutar el algoritmo con normalidad.} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. Si el dividendo tiene más dígitos, el procedimiento se ejecuta del mismo modo. Por ejemplo, al calcular 3521\div 12 se obtiene:

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. Si uno de los números es negativo, existen dos formas aceptables de presentar el resultado. No obstante, la forma estándar en teoría de números es aquella en que el resto es positivo y, por tanto, consistente con la división de Euclides. Por ejemplo, si calculamos -598\div 21, se tienen los siguientes desarrollos posibles, ambos correctos como identidades:

   • Con resto negativo: Este se obtiene eliminando el signo al inicio de la operación y restaurándolo al final.

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     A partir de esto se tiene que:

     598 = 21 \times 28 + 10

     Luego, si multiplicamos toda la igualdad por -1, se obtiene:

     -598 = 21 \times (-28) - 10

     De modo que, en esta representación, el resultado de -598\div 21 es cociente q=-28 y resto r=-10.

     Y si multiplicamos nuevamente toda la igualdad por -1, se obtiene:

     598 = (-21)\times(-28) + 10

     De modo que el resultado de 598\div (-21) es cociente q=-28 y resto r=10.

   • Con resto positivo y consistente con la división de Euclides: A partir del desarrollo anterior se tiene que:

     -598 = 21 \times (-28) - 10

     Luego, sumando 0=21-21 en el lado derecho de esta igualdad, se tiene:

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     Por lo tanto, siendo consistentes con la división de Euclides, el resultado de calcular -598\div 21 da un cociente q=-29 y el resto r=11.

   Respecto de lo convencional en la división de Euclides, sólo el resultado con resto positivo corresponde al cociente y resto euclidianos. Sin embargo, ambas expresiones son identidades correctas y pueden ser útiles en contextos distintos. Si bien el algoritmo de división larga puede producir restos negativos, esto resulta práctico para obtener resultados de manera mecánica y realizar manipulaciones algebraicas sin pasos adicionales. Por otro lado, los resultados con resto positivo, consistentes con la división de Euclides, permiten fijar un representante canónico de cada clase residual (por ejemplo, en \{0,1,\dots,n-1\}), lo que facilita el etiquetado de los enteros de forma precisa y libre de ambigüedad. Cabe señalar que también existen otras convenciones de representantes, como los residuos simétricos, igualmente válidas una vez fijada la regla.

Conclusión

El algoritmo de la división garantiza que toda división entera puede expresarse de forma única como b=qa+r con 0\le r<|a|, lo que fija un criterio estándar para interpretar el cociente y el resto incluso cuando intervienen números negativos. El algoritmo largo de la división no es más que una implementación práctica de esta descomposición, apoyada en la representación posicional, y permite calcular q y r de manera mecánica. Finalmente, esta forma euclidiana no solo evita ambigüedades, sino que también conecta naturalmente con la aritmética modular: el resto r actúa como un representante canónico de la clase residual de b módulo a, base de muchas técnicas en teoría de números y en aplicaciones computacionales que podrán ser revisadas en proximas entregas.

Ejercicios propuestos y resueltos

División euclidiana

1. (resuelto) Encuentra q y r tales que

   137 = 9q + r,\qquad 0\le r\lt 9.

   Solución: Busca el número más grande que, multiplicado por 9 no sobrepase a 137. Tenemos que 15\times 9 = 135 y 16\times 9 = 144, por lo tanto, el cociente buscado es q=15. Ahora calcula el resto r=137-9q y verifica que 0\le r\lt 9. Haciendo la verificación se tiene:

   r=137-9\cdot 15=137-135=2.

   Por tanto, 137=9\cdot 15+2 con 0\le 2\lt 9.

2. (resuelto) Encuentra q y r tales que

   2025 = 37q + r,\qquad 0\le r\lt 37.

   Solución: Busca el número más grande que, multiplicado por 37 no sobrepase a 2025. Observa que 37\times 54 = 1998 y 37\times 55 = 2035, por lo tanto, el cociente buscado es q=54. Ahora calcula el resto r=2025-37q y verifica que 0\le r\lt 37. Haciendo la verificación se tiene:

   r=2025-37\cdot 54=2025-1998=27.

   Por tanto, 2025=37\cdot 54+27 con 0\le 27\lt 37.

3. Encuentra q y r tales que

   745 = 23q + r,\qquad 0\le r\lt 23.

4. Encuentra q y r tales que

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. Encuentra q y r tales que

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. Resto fijado y búsqueda de enteros. Sea a=12.

   (a) Describe el conjunto de todos los enteros b cuya división euclidiana por 12 tiene resto r=5.

   (b) Encuentra el menor entero b\gt 1000 que cumpla lo anterior y determina el cociente q correspondiente.

Algoritmo largo de la división

En cada caso, aplica el algoritmo largo de la división para calcular el cociente q y el resto r. Transforma el resultado a división euclidiana cuando el algoritmo proporcione resto negativo.

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.