Algoritmo de Euclides

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.