|
Como la sucesión de residuos va disminuyendo, al final un residuo tiene que ser cero y es en ese momento cuando el algoritmo termina. El máximo común divisor es precisamente <math>r_{n+1}</math> (el último residuo que no es cero).
=== Descripción formaldel algoritmo ===
1.dividir el numero que fue divisor en el paso anterior entre el resto obtenido en el paso anterior
Se puede expresar este algoritmo de manera más formal usando [[pseudocódigo]]. En este caso la expresión "<math>x \; \bmod \; y</math>" significa "el residuo de dividir <math>x</math> entre <math>y</math>" (véase [[Aritmética modular]]).
{{Algoritmo|de Euclides|
'''Entrada:''' Valores <math>a</math> y <math>b</math> pertenecientes a un dominio euclídeo
2.despreciar el cociente
'''Salida:''' Un máximo común divisor de <math>a</math> y <math>b</math>
# <math>r_0\gets a</math>, <math>r_1\gets b</math>
3.si el resto obtenido esta vez es 0, el mcd es el divisor de esta operacion, es decir, el último resto no nulo (recordemos que el divisor de esta operación fué el resto en la anterior.
# <math>i\gets1</math>
# '''Mientras''' <math>r_i\neq 0</math> '''haga lo siguiente:'''
4.Si el resto no es 0, ir al primer paso
## <math>r_{i+1}\gets r_{i-1}\;\bmod\; r_i</math>
## <math>i\gets i+1</math>
# '''El resultado es:''' <math>r_{i-1}</math>
|1}}
Vale la pena notar que este algoritmo no es eficiente ser implementado directamente en una computadora, ya que requeriría memorizar todos los valores de <math>r_i</math>.
== Algoritmo de Euclides extendido ==
| 