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).
=== Generalización ===
En realidad el algoritmo de Euclides funciona no sólo para los números naturales, sino para cualesquiera elementos en los que exista una "división con residuo". A este tipo de divisiones se les llama [[División euclidiana|divisiones euclidianas]] y a los conjuntos donde se puede definir dicha división se les llama [[Dominio euclídeo|dominios euclídeos]]. Por ejemplo, el conjunto de los [[Número entero|números enteros]] y el de los [[polinomio]]s con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuo (véase [[División polinomial]]). De esta manera, se puede calcular el máximo común divisor de dos números enteros o de dos polinomios.
Por ejemplo, para calcular el máximo común divisor de los polinomios <math>P(x)=x^5+2x^3+x</math> y <math>Q(x)=x^4-1</math> el algoritmo de Euclides sugiere la siguiente secuencia de operaciones:
{| class="wikitable"
!Paso!!Operación!!Significado
|-
|1||<math>x^5+2x^3+x</math> dividido entre <math>x^4-1</math> es <math>x</math> y sobra <math>2x^3+2x</math>||<math>\mathrm{mcd}(x^5+2x^3+x,x^4-1)=\mathrm{mcd}(x^4-1,2x^3+2x)</math>
|-
|2||<math>x^4-1</math> dividido entre <math>2x^3+2x</math> es <math>\textstyle{\frac12x}</math> y sobra <math>-x^2-1</math>||<math>\mathrm{mcd}(x^4-1,2x^3+2x)=\mathrm{mcd}(2x^3+2x,-x^2-1)</math>
|-
|3||<math>2x^3+2x</math> dividido entre <math>-x^2-1</math> es <math>-2x</math> y sobra 0||<math>\mathrm{mcd}(2x^3+2x,-x^2-1)=\mathrm{mcd}(-x^2-1,0)</math>
|}
De esta manera se concluye que su máximo común divisor es <math>-x^2-1</math>.
