Como resuelvo este ejercicio de divisibilidad?
Me podrían ayudar con un ejercicio que he estado intentando hacer.
Mostrar que 725 y 441 son coprimos y encontrar enteros m, n tales que m*725 + n*441 = 1
·
·
¡Hola Patito!
Yo podría responder ahora mismo. Pero antes tendrás de valorarme Excelente en esta pregunta, se puede cambiar la votación.
Duda sobre problemas de Divisibilidad
Una vez lo hayas hecho avísame para que conteste.
Saludos.
:
:
Para mostrar que son coprimos calcularemos los factores primos y no tendrán que tener niguno en común. Espero que no desalien las columnas
725 | 5 145 | 5 29 | 29 1 · 441 | 3 147 | 3 49 | 7 7 | 7 1
Y como puedes ver no tienen ningun factor primo común, luego son coprimos.
725m + 441n = 1
Si te piden esto imagino que estás estudiando teoría de números y el algoritmo extendido de Euclides. Iremos calculando los divisores y restos
725 = 441 + 284
441 = 284 + 157
284 = 157 + 127
157 = 127 + 30
127 = 4 · 30 + 7
30 = 4 · 7 + 2
7 = 3·2 + 1
Y ahora se calcula de abajo arriba
1 = 7 - 3 · 2 =
7 - 3(30 - 4 · 7) = -3 · 30 + 13 · 7 =
-3 · 30 + 13(127 - 4 · 30) = 13 · 127 - 55 · 30=
13 · 127 - 55(157 - 127) = - 55 · 157 + 68 · 127 =
-55 · 157 + 68(284 - 157) = 68 · 284 - 123 · 157 =
68 · 284 - 123(441-284) = -123 · 441 + 191 · 284 =
-123 · 441 + 191(725-441) = 191 · 725 - 314 · 441
Luego m=191 y n=314
Hay formas de hacerlo mecánicamente que se tiene que escribir y calcular menos, pero aparte de lo complicado que es explicarlo aquí, se olvidan esos métodos. Yo el único que recuerdo es este, de hacer sustituciones de abajo hacia arriba hasta que quedan los números originales multiplicados por algo.
Y eso es todo, saludos.
:
:
