Ejercicios de El algoritmo de Euclides

Calcula el máximo común divisor entre $252$ y $198$ mediante el algoritmo de Euclides, y escríbelo también como la suma $m c d (252, 198) = s_{n} \cdot 252 + t_{n} \cdot 198$ .

Ver desarrollo y solución

Desarrollo:

En este caso se tiene: $a = 252$ y $b = 198$ .
Se define: $r_{0} = 252, r_{1} = 198$ $s_{0} = 1, s_{1} = 0$ $t_{0} = 0, t_{1} = 1$
Ahora se calcula la división entera entre $r_{0}$ y $r_{1}$ . Se tiene que el resultado es $1$ , y el residuo $45$ . Por lo tanto: $q_{1} = 1, r_{2} = 54$ Por otro lado: $s_{2} = s_{0} - s_{1} \cdot q_{1} = 1 - 0 \cdot 1 = 1$ $t_{2} = t_{0} - t_{1} \cdot q_{1} = 0 - 1 \cdot 1 = - 1$

Como $r_{2} \neq 0$ , se tiene que continuar. Se hace la división entera entre $198$ (es decir $r_{1}$ ) y $54$ (es decir $r_{2}$ ), y se obtiene de resultado $q_{2} = 3$ y residuo $r_{3} = 36$ . Entonces: $s_{3} = s_{1} - s_{2} \cdot q_{2} = 0 - 1 \cdot 3 = - 3$ $t_{3} = t_{1} - t_{2} \cdot q_{2} = 1 - (- 1) \cdot 3 = 4$ Como $r_{3} \neq 0$ , se realiza un paso más. Ahora la división entera entre $54$ (que es $r_{2}$ ) y $36$ ( $r_{3}$ ) y se obtiene: $q_{3} = 1$ y el residuo es $r_{4} = 18$ . Ahora: $s_{4} = s_{2} - s_{3} \cdot q_{3} = 1 - (- 3) \cdot 1 = 4$ $t_{4} = t_{3} - t_{2} \cdot q_{2} = - 1 - 4 \cdot 1 = - 5$ Como $r_{4} \neq 0$ , se vuelve a repetir el proceso. La división entera de $r_{3} = 36$ y $r_{4} = 18$ da como resultado $q_{4} = 2$ , y el residuo es $r_{5} = 0$ . Así pues, ¡ya no se tiene que seguir más!

Entonces se tiene que $m c d (252, 198) = r_{4} = 18$ (porque es el del penúltimo paso). Por otro lado: $m c d (252, 198) = s_{4} \cdot 252 + t_{4} \cdot 198 = 4 \cdot 252 - 5 \cdot 198$

Solución:

$m c d (252, 198) = 18 = 4 \cdot 252 - 5 \cdot 198$

Ocultar desarrollo y solución