El algoritmo de Euclides afirma que podemos aplicar iteradas veces el algoritmo de la divisi\u00f3n hasta encontrar el m\u00e1ximo com\u00fan divisor de dos enteros positivos $a$ y $b$, mediante el siguiente procedimiento:<\/p>\n\n\n\n
Sean $a, b$ cualesquiera enteros positivos, con $a \\neq b$ y $a > b.$
Por el algoritmo de la divisi\u00f3n, sabemos que siempre existen $q, r \\in \\mathbb{Z}$ tales que podemos escribir $$a = bq + r, \\enspace \\text{con} \\quad \\quad 0 \\leq r < b. $$<\/p>\n\n\n\n
Luego, como $b$ y $r$ son enteros, tambi\u00e9n existen $q_1$ y $r_1$ tales que $$b = rq_1 + r_1,\\enspace \\text{con} \\quad \\quad 0 \\leq r_1 < r.$$<\/p>\n\n\n\n
Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2 \\in \\mathbb{Z}^+$ tales que $$r = r_1q_2 + r_2,\\enspace \\text{con} \\quad \\quad 0 \\leq r_1 < r.$$<\/p>\n\n\n\n
Se puede continuar as\u00ed, de tal forma que en un pen\u00faltimo paso tendremos que existen $q_i$ y $r_i$ enteros tales que $$r_{i-2} = r_{i-1}q_i + r_i, \\enspace \\text{con} \\quad \\quad 0 \\leq r_i < r_{i-1}.$$<\/p>\n\n\n\n
Y el algoritmo termina cuando el residuo es cero. Es decir, existir\u00e1n $q_{i+1} \\in \\mathbb{Z}^+$ y $r = 0$ tales que
$$r_{i-1} = r_{i}q_{i+1} + 0, \\enspace \\text{con} \\quad \\quad 0 = r_{i+1} < r_i .$$<\/p>\n\n\n\n
Luego entonces, el \u00faltimo residuo no cero es el m\u00e1ximo com\u00fan divisor de $a$ y $b$.<\/p>\n\n\n\n
Este procedimiento lo podemos aplicar cuando $a$ y $b$ sean n\u00fameros muy grandes, de modo que determinar el m\u00e1ximo com\u00fan divisor no es inmediato. Sin embargo, el algoritmo de Euclides es una receta a\u00fan sencilla, que har\u00e1 f\u00e1cil encontrar el $MCD$ para cualquier pareja de n\u00fameros enteros.<\/p>\n\n\n\n
Ejemplo.<\/strong> Encuentra el m\u00e1ximo com\u00fan divisor de $3456$ y $6524$.<\/p>\n\n\n\n Soluci\u00f3n.<\/em> Observamos que $6524 > 3456$. As\u00ed, $$6524 = 3456\\cdot 1 + 3068, \\quad \\quad 0 \\leq 3068 < 3456. $$ Como el \u00faltimo residuo no cero es $4$, entonces $4$ es el m\u00e1ximo com\u00fan divisor de $6524$ y $3456$.<\/p>\n\n\n\n Observaci\u00f3n.<\/em> Aunque el algoritmo euclidiano requiere que los n\u00fameros $a$ y $b$ sean positivos, cuando ocurriera el caso de que uno de ellos o los dos fueran negativos, no se presentar\u00eda mayor obst\u00e1culo. Bastar\u00eda sacar el valor absoluto de ambos al inicio (ya que los divisores de un n\u00famero negativo son los mismos que los de sus positivos).<\/p>\n\n\n\n Ejemplo.<\/strong> Obt\u00e9n el m\u00e1ximo com\u00fan divisor de $-100$ y $45$.<\/p>\n\n\n\n Soluci\u00f3n.<\/em> Como uno de los n\u00fameros es negativo, antes que nada sacamos valores absolutos: $|-100| = 100$ y $|45| = 45.$ As\u00ed, Por lo tanto, $MCD(-100, 45) = 5.$<\/p>\n\n\n\n La clave por la que el algoritmo de Euclides funciona es el siguiente teorema:<\/p>\n\n\n\n Teorema.<\/strong> Sean $a,b \\in \\mathbb{Z}^+, $ tales que $a = bq + r.$ Entonces $MCD(a,b) = MCD(b,r).$<\/em><\/p>\n\n\n\n Dem.-<\/em> Sean $a,b \\in \\mathbb{Z}^+$ y sea $d$ alg\u00fan divisor com\u00fan de $a$ y $b$ elegido arbitrariamente. Como $d$ es divisor de $a$, entonces $d \\mid a.$ As\u00edmismo, $d$ es divisor de $b$, por lo tanto $d \\mid b.$<\/p>\n\n\n\n Ya que $d \\mid b$, entonces $d \\mid bq$.<\/p>\n\n\n\n Ya que $d \\mid a$ y $d \\mid bq,$ tambi\u00e9n $d \\mid a \\enspace – \\enspace bq.$<\/p>\n\n\n\n Ya que $a = bq + r$ y $d \\mid a \\enspace – \\enspace bq,$ entonces $d \\mid r. \\quad (*)$<\/p>\n\n\n\n Ahora, fij\u00e1ndonos en los divisores comunes de $b$ y $r$, sea $f$ un divisor com\u00fan de $b$ y $r$ tomado arbitrariamente. Se tiene, por lo tanto, que $f \\mid b$ y $f \\mid r$.<\/p>\n\n\n\n Ya que $f \\mid b$, entonces $f \\mid bq$.<\/p>\n\n\n\n Ya que $f \\mid bq$ y $f \\mid r,$ tambi\u00e9n $f \\mid bq + r.$<\/p>\n\n\n\n Ya que $a = bq + r,$ entonces $f \\mid a. \\quad (**)$<\/p>\n\n\n\n En conclusi\u00f3n, de $(*)$, hemos demostrado que cualquier divisor de $a$ y $b$ es tambi\u00e9n divisor de $r.$ Y con $(**)$ mostramos que cualquier divisor de $b$ y $r$ es tambi\u00e9n divisor de $a.$ En otras palabras, “$d$ es divisor de $a$ y $b$ si y s\u00f3lo si $d$ es divisor de $b$ y $r$.”<\/p>\n\n\n\n As\u00ed pues, el conjunto de todos los divisores de $a$ y $b$ es igual al conjunto de todos los divisores de $b$ y $r$; en particular, el m\u00e1ximo com\u00fan divisor de $a$ y $b$ debe ser igual al m\u00e1ximo com\u00fan divisor de $b$ y $r$.<\/p>\n\n\n\n $\\square$ Usando el teorema reci\u00e9n demostrado y regresando al algoritmo de Euclides en el primer paso, si $a = bq + r$, deducimos que $MCD(a,b) = MCD(b, r).$<\/p>\n\n\n\n En el siguiente paso del algoritmo euclidiano, $b = rq_1 + r_1.$ Por lo tanto $MCD(b,r) = MCD(r, r_1).$<\/p>\n\n\n\n En el tercer paso, $r = r_1q_2 + r_2.$ As\u00ed, $MCD(r, r_1) = MCD(r_1, r_2).$<\/p>\n\n\n\n En el pen\u00faltimo paso, $r_{i-2} = r_{i-1}q_{i} + r_i.$ Por lo que $MCD(r_{i+2}, r_{i-1}) = MCD(r_{i-1}, r_i).$<\/p>\n\n\n\n En el \u00faltimo paso, $r_{i+1} = r_iq_{i+1} + 0.$ Por lo que $MCD(r_{i+1}, r_i) = MCD(r_i, 0) = r_i.$<\/p>\n\n\n\n As\u00ed pues, $$MCD(a,b) = MCD(b, r) = MCD(r, r_1) = MCD(r_1, r_2) = \\ldots $$ Esto demuestra que efectivamente, el \u00faltimo residuo no cero en el algoritmo de Euclides, es igual al $MCD(a,b).$<\/p>\n\n\n\n $\\square$<\/p>\n\n\n\n
Aplicando nuevamente el algoritmo de la divisi\u00f3n, obtenemos
$$3456 = 3068 \\cdot 1 + 388, \\quad \\quad 0 \\leq 388 < 3068. $$
Aplicando una vez m\u00e1s el algoritmo de la divisi\u00f3n, se tiene
$$3068 = 388\\cdot 7 + 352, \\quad \\quad 0 \\leq 352 < 388. $$
Luego,
$$388 = 352 \\cdot 1 + 36, \\quad \\quad 0 \\leq 36 < 352. $$
$$352 = 36 \\cdot 9 + 28, \\quad \\quad 0 \\leq 28 < 36. $$
$$36 = 28\\cdot 1 + 8, \\quad \\quad 0 \\leq 8 < 28.$$
$$28 = 8 \\cdot 3 + 4, \\quad \\quad 0 \\leq 4 < 8.$$
$$8 = 4\\cdot 2 + 0.$$<\/p>\n\n\n\n
$$ 100 = 45 \\cdot 2 + 10, \\quad \\quad 0 \\leq 10 < 45. $$
$$ 45 = 10 \\cdot 4 + 5, \\quad \\quad 0 \\leq 5 < 10. $$
$$10 = 5 \\cdot 2 + 0.$$<\/p>\n\n\n\nDemostraci\u00f3n del algoritmo de Euclides<\/h3>\n\n\n\n
<\/p>\n\n\n\n
$$ \\ldots = MCD(r_{i+2}, r_{i-1}) = MCD(r_{i-1}, r_i) = MCD(r_i, 0) = r_i. $$<\/p>\n\n\n\n