Hola, me han surgido unas dudas en torno al al Algoritmo de Euclides. Lo escribo primero:
TeoremaEl máximo común divisor del dividendo y del divisor de una división es el mismo que el máximo común divisor del divisor y del resto.
DemostraciónSea \( a=b+qr \) (?). Tenemos que probar que \( \mbox{m.c.d.}(a,b)=\mbox{m.c.d.}(b,r) \). Por la proposición anterior sabemos que los divisores comunes de \( a \) y \( b \) son los mismos que los divisores comunes de \( b \) y \( r \). Por lo tanto tienen el mismo máximo común divisor.
Algoritmo de EuclidesDel Teorema anterior podemos obtener un algoritmo para el cálculo del \( \mbox{m.c.d.} \) de dos números \( a \) y \( b \). Como
\( \mbox{m.c.d.}(a,b)=\mbox{m.c.d.}(|a|,|b|) \),
podemos suponer sin pérdida de generalidad que \( a\geq{b>0} \). Dividimos \( a \) por \( b \)
\( a=bq_1+r_1 \) con \( 0\leq{r_1<b} \)
Si \( r_1=0 \) es obvio que \( b=\mbox{m.c.d.}(a,b) \). Así pues supongamos que \( r_1\neq{0} \);dividiendo \( b \) por \( r_1 \) podemos escribir
\( b=r_1q_2+r_2 \) con \( 0\leq{r_2<r_1} \)
Si \( r_2=0 \) entonces \( \mbox{m.c.d.}(b,r_1)=\mbox{m.c.d.}(a,b)=r_1 \) y hemos terminado. Si \( r_2|0 \) (?) entonces efectuamos la división de \( r_1 \) por \( r_2 \). Vamos obteniendo así un conjunto de números
\( r_1>r_2>...>r_i>..., \)
Puesto que cada uno de los números \( r_1,r_2,...,r_i,... \) es mayor o igual que cero, este conjunto de números no puede ser infinito. En algún momento llegaremos a que un resto es cero. Sea dicho resto \( r_n=0 \) para algún \( n \), entonces
\( r_{n-1}=\mbox{m.c.d.}(r_{n-2},r_{n-1})=\mbox{m.c.d.}(r_{n-3},r_{n-2})=...=\mbox{m.c.d.}(b,r_1)=\mbox{m.c.d.}(a,b) \).
Las dudas son: las dos interrogaciones en el texto y el último razonamiento (En algún momento llegaremos a que un resto es cero. Sea dicho resto \( r_n=0 \) para algún \( n \), entonces
\( r_{n-1}=\mbox{m.c.d.}(r_{n-2},r_{n-1})=\mbox{m.c.d.}(r_{n-3},r_{n-2})=...=\mbox{m.c.d.}(b,r_1)=\mbox{m.c.d.}(a,b) \)). No entiendo esta cantidad de \( r_n,r_{n-1},r_{n-2} \),...
Un saludo!
