Ejercicios tema 4: Algoritmo de Euclides e Identidad de Bezout
Instrucciones
Para cada uno de los siguientes ejercicios, calcula el maximo comun divisor (mcd) utilizando el algoritmo de euclides y encuentra los enteros \(s, t \in \mathbb{Z}\) tales que se cumpla la identidad de Bezout:
\(s \cdot a + t \cdot b = \text{mcd}(a, b)\)
Ejemplo Resuelto
Ejercicio 1: Calcula el \(\text{mcd}(720, 168)\) y halla sus coeficientes de Bezout.
Paso 1: Algoritmo de Euclides
Realizamos divisiones sucesivas para encontrar el ultimo resto no nulo:
- \(720 = 4 \cdot 168 + 48 (\text{Resto 1}: 48)\)
- \(168 = 3 \cdot 48 + 24 (\text{Resto 2}: 24)\)
- \(48 = 2 \cdot 24 + 0 (\text{Resto 3}: 0)\)
El ultimo resto no nulo es 24, por lo tanto \(\text{mcd}(720, 168) = 24\).
Paso 2: Identidad de Bezout
Despejamos los restos de las ecuaciones anteriores (empezando por el mcd):
- De la ecuacion 2: \(24 = 168 - 3 \cdot 48\)
- De la ecuacion 1: \(48 = 720 - 4 \cdot 168\)
Ahora sustituimos la expresion del resto 48 en la ecuacion del 24:
\(24 = 168 - 3 \cdot (720 - 4 \cdot 168)\) \(24 = 168 - 3 \cdot 720 + 12 \cdot 168\) \(24 = (-3) \cdot 720 + 13 \cdot 168\)
Resultado: Los coeficientes son \(s = -3\) y \(t = 13\). Comprobacion:
\((-3) \cdot 720 + 13 \cdot 168 = -2160 + 2184 = 24\)
Ejemplo 2
\(\text{mcd}(78, 30)\)
\(78 = 2 \cdot 30 + 18 (\text{ Resto: 18})\) \(18 = 78 - 2 \cdot 30\) \(12 = 30 - 1 \cdot 18\) \(6 = 18 - 1 \cdot 12\)
\(\text{mcd}(78, 30) = 6\)
\(6 = 18 - 1 \cdot (30 - 1 \cdot 18) = 2 \cdot 18 + 1 \cdot 30\) \(6 = 2 \cdot (78 - 2 \cdot 30) + 1 \cdot 30 = 2 \cdot 78 - 4 \cdot 30 + 1 \cdot 30 = 2 \cdot 78 - 5 \cdot 30\)
Ejercicios
Ejercicio 2
\(s \cdot 1024 + t \cdot 360 = \text{mcd}(1024, 360)\)
\(1024 = 2 \cdot 360 + 304\) \(360 = 1 \cdot 304 + 56\) \(304 = 5 \cdot 56 + 24\) \(56 = 2 \cdot 24 + 8\)
\(\text{mcd}(1024, 360) = 8\)
Identidad de Bezout:
\(8 = 56 - 2 \cdot 24\) \(24 = 304 - 5 \cdot 56\) \(56 = 360 - 1 \cdot 304\) \(304 = 1024 - 2 \cdot 360\)
Sustituyendo:
\(8 = 56 - 2 \cdot (304 - 5 \cdot 56) = 11 \cdot 56 - 2 \cdot 304\) \(8 = 11 \cdot (360 - 304) - 2 \cdot 304 = 11 \cdot 360 - 13 \cdot 304\) \(8 = 11 \cdot 360 - 13 \cdot (1024 - 2 \cdot 360) = (-13) \cdot 1024 + 37 \cdot 360\)
\(s = -13, t = 37\)
Ejercicio 3
\(\text{mcd}(525, 231)\)
\(525 = 2 \cdot 231 + 63\) \(231 = 3 \cdot 63 + 42\) \(63 = 1 \cdot 42 + 21\) \(42 = 2 \cdot 21 + 0\)
Identidad de Bezout:
\(63 = 525 - 2 \cdot 231\) \(42 = 231 - 3 \cdot 63\) \(21 = 63 - 1 \cdot 42\)
Sustituyendo:
\(21 = 63 - 1 \cdot 42 = 63 - 1 \cdot (231 - 3 \cdot 63) = 63 - 1 \cdot 23 + 3 \cdot 63 = 6 \cdot 63 - 1 \cdot 23\) \(21 = 4 \cdot (525 - 2 \cdot 231) - 1 \cdot 231 = 4 \cdot 525 - 8 \cdot 231 - 1 \cdot 231 = 4 \cdot 525 - 9 \cdot 231\)
Ejercicio 4
\(\text{mcd}(840, 198)\)
\(840 = 4 \cdot 198 + 48\) \(198 = 4 \cdot 48 + 6\) \(48 = 8 \cdot 6 + 0\)
\(\text{mcd}(840, 198) = 6\)
Identidad de Bezout: \(6 = 198 - 4 \cdot 48\) \(6 = 198 - 4 (840 - 4 \cdot 198)\) \(6 = 198 - 4 \cdot 840 + 16 \cdot 198\) \(6 = (-4)\cdot 840 + 17 \cdot 198\)
\(s = -4, t = 17\)
Ejercicio 5
\(\text{mcd}(324, 144)\)
\(324 = 2 \cdot 144 + 36\) \(144 = 4 \cdot 36 + 0\)
\(36 = 324 - 2 \cdot 144\) \(36 = 1 \cdot 324 + (-2) \cdot 144\)
\(s = 1, t = -2\)
