En aritmética, es un algoritmo que, con el input de dos números enteros no negativos $a, b$ (con $b$ no nulo) produce como output o resultado otros dos enteros no negativos $q, r$ (con r<b) tales que $a = b q + r$. Nota: $a$ se llama dividendo, $b$ se llama divisor, $q$ es el cociente y $r$ el residuo.
El contexto primitivo en que se aplica son los problemas de reparto equitativo de objetos entre personas. Responde a la pregunta ¿cuántas veces cabe $b$ en $a$? e, indirectamente, a la cuestión de si $a$ es múltiplo de $b$. (Sí, si $r=0$; no, en otros casos). Las instrucciones son: sigue restando $b$ de $a$ mientras puedas. Ejemplo: reparte 123 objetos entre 12 personas; el output es $q=10$ y $r=3$.
Para un análisis más completo ver: Algoritmo de la División Entera.