Algoritmo de Euclides

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} 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} 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} 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:
$\Rightarrow 1071 = 1 \cdot 1029 + 42$		$\begin{array}{l} \begin{array}{l} \begin{array}{ccc} 1071 : & 1029 & = 1 r e s i d u o 42 \\ 1029 \\ 42 \end{array} \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í:
$\Rightarrow 1029 = 24 \cdot 42 + 21$		$\begin{array}{l} \begin{array}{l} \begin{array}{ccc} 1029 : & 42 & = 24 r e s i d u o 21 \\ 84 \\ 189 \\ 168 \\ 21 \end{array} \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í:
$\Rightarrow 42 = 2 \cdot 21 + 0$		$\begin{array}{l} \begin{array}{l} \begin{array}{ccc} 42 : & 21 & = 2 r e s i d u o 0 \\ 42 \\ 0 \end{array} \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$

Este contenido está licenciado bajo
CC BY-SA 4.0 → ¿Qué quiere decir esto? serlo.org