Algoritmo de Euclides - ¡Aprende con Serlo!

El algoritmo de Euclides es muy útil para determinar el máximo común divisor (MCD).

Procedimiento

Si tienes dos números, puedes determinar el máximo común divisor MCD de la siguiente manera:

Paso 1: El número mayor lo divides por el menor y tomas nota del residuo.

Paso 2: El número menor lo divides por el residuo que obtuviste en el paso 1.

Paso 3: Ahora divide el residuo que obtuviste en el paso 1 por el residuo que obtuviste en el paso 2.

Paso 4: Divide el residuo del paso 2 por el residuo del paso 3.

Paso 5: Hazlo tantas veces como sea necesario hasta que el residuo sea $0$ .

Paso 6: El divisor en este cálculo es el MCD de los números a y b.

Seguimos una notación matemática general:

Se supone que $a$ es mayor que $b$ :

$a=q_1\cdot b+r_0$		Aquí, $q_{1}$ y $r_{0}$ son números que emergen del cálculo (con el residuo) $a:b=q_1\ \text{residuo} \ r_0$ . $r_{0}$ es, por lo tanto, el residuo de la división de los números de $a$ y $b$ .
$b=q_2\cdot b+r_1$		Aquí, $q_{2}$ y $r_{1}$ son números que emergen del cálculo (con el residuo) $b:r_0=q_2\ \text{residuo} \ r_1$ . $r_{1}$ es, por lo tanto, el residuo de la división de los números de $b$ y $r_{0}$ .
$r_0=q_3\cdot r_1+r_2$		Aquí, $q_{3}$ y $r_{2}$ son números que emergen del cálculo (con el residuo) $r_0:r_1=q_3\ \text{residuo} \ r_2$ . $r_{2}$ es, por lo tanto, el residuo de la división de los números de $r_{0}$ y $r_{1}$ .

Acá puedes reconocer el esquema:

Hazlo tantas veces como sea necesario hasta que el resuduo sea 0:

$r_{n-2}=q_{n+1}\cdot r_{n-1}+0$		$r_{n-1}$ es el $M C D$ de $a$ y $b$

Tenemos dos números, $a = 1071$ y $b = 1029$

$1071=q_1\cdot 1029+r_0$		Los números $q_{1}$ y $r_{0}$ los obtienes aplicando el método escrito para la división con su residuo:
$\Rightarrow1071=1\cdot1029+42$		$\def\arraystretch{1.25} \\ \begin{array}{l}\begin{array}{ccc}1071:&1029&=1\;residuo\;42\\\underline{1029}&&\\\;\;\;42&&\end{array}\end{array}$
		así es $q_{1} = 1$ und $r_{0} = 42$
$1029=q_2\cdot 42+r_1$		Los números $q_{2}$ y $r_{1}$ los obtienes así:
$\Rightarrow1029=24\cdot42+21$		$\def\arraystretch{1.25} \\ \begin{array}{l}\begin{array}{ccc}1029:&42&=24\;residuo\;21\\\underline{84}&&\\\;189\\\underline{168}&&\\\;21&&\end{array}\end{array}$
		así es $q_{2} = 24$ und $r_{1} = 21$
$42=q_3\cdot 21+r_2$		Los números $q_{3}$ y $r_{2}$ los obtienes así:
$\Rightarrow42=2\cdot21+0$		$\def\arraystretch{1.25} \\ \begin{array}{l}\begin{array}{ccc}42:&21&=2\;residuo\;0\\\underline{42}&&\\\;0&&\end{array}\end{array}$
		así es $q_{3} = 2$ und $r_{2} = 0$

Así que $r_{1} = 21$ es el máximo común divisor de $1071$ y $1029$ :

$M C D (1071,1029) = 21$