Algoritmo de la División

Teoría

El Algoritmo de la División es un teorema fundamental en la teoría de números que formaliza el proceso intuitivo de dividir con residuos. A pesar de su nombre, no es un algoritmo (un método de cálculo paso a paso), sino más bien un teorema que asegura la existencia y la unicidad de una solución. Dice que para cualquier entero $a$ y cualquier entero positivo $b$, existe un par único de enteros, el cociente $q$ y el residuo $r$, de tal manera que puedes expresar $a$ como un múltiplo de $b$ más el residuo, donde el residuo es estrictamente menor que $b$ y no es negativo.

Este concepto es la piedra angular de la aritmética modular y del Algoritmo de Euclides que usas para encontrar el Máximo Común Divisor (MCD). En las matemáticas de olimpiada, el Algoritmo de la División es esencial para clasificar enteros según sus residuos (por ejemplo, para distinguir entre números pares e impares, o números módulo $n$). Te permite traducir problemas de divisibilidad a ecuaciones algebraicas, lo que facilita el uso de la manipulación algebraica para resolver preguntas de teoría de números.

De forma intuitiva, puedes visualizar el Algoritmo de la División en la recta numérica. Si empiezas en $0$ y das pasos de longitud $b$ hacia $a$, $q$ representa el número de pasos completos que das, y $r$ representa la distancia que te falta para llegar a $a$. Como el