En aritmética, es un algoritmo que, con el input de dos números enteros positivos $a, b$, produce como output un entero positivo $g$, denominado Máximo Común Divisor de $a$ y $b$ (MCD$(a,b)$). La perspectiva euclideana interpretaba el MCD$(a,b)$ como la la máxima "medida común" de $a$ y $b$. (Claramente el 1 siempre es medida común.)
Las instrucciones son: divide $a$ entre $b$ con el algoritmo de la división; si el residuo $ r $ es cero, $b$ es el MCD$(a,b);$ de otra manera, divide $b$ entre $ r $; si el residuo $r_1$ obtenido es cero, entonces $ r $ es el MCD$(a,b);$ continuar de esta manera hasta obtener un residuo nulo (el penúltimo residuo es el MCD$(a,b)$). Pseudocódigo
PROCEDIMIENTO MCD(a,b): SI a<b, INTERCAMBIAR(a,b) MIENTRAS $b \neq 0$ r = RESIDUO de a÷b a=b b=r end return a end
Ejemplo:
39, 213
213, 39
$213=5\cdot{39}+18$
39, 18
$39=2\cdot{18}+3$
18, 3
$18=6\cdot{6}$
MCD$(39,213)=3$
Para más ejemplos y más detalle consulte el lector la Wikipedia.