Problema de Teoría de Números.
Hola Valero asm:
¿Divide 41 a 7(3)^20 + 6?
El tema que estamos viendo actualmente es "Congruencias Lineales"
Espero tu ayuda
1 Respuesta
Supongo que quieres decir 7 por (3 elevado a la 20)
7·3^20 + 6 :~ 0 (mod 41)
7·3^20 :~ -6 (mod 41)
7·3^20 :~ 35 (mod 41)
3^20 :~ 5 (mod 41)
Hacemos cuentas aparte
3^4=81 :~ 40 (mod 41)
3^8 = 3^4 · 3^4 :~ 40·40 ~ (-1)(-1) :~ 1 (mod 41)
3^16 =3^8 · 3^8 :~ 1·1 :~ 1 (mod 41)
3^20 = 3^16 · 3^4 :~ 1 ·40 :~ 40 (mod 41)
Y comparamos el resultado auténtico con la hipótesis
5 :~ 40 (mod 41)
Lo cual es falso ya que si los los dos están comprendidos entre 0 y 40 deben ser iguales para ser congruentes modulo 41
Luego la hipótesis es falsa y por lo tanto 41 no divide a (7·3^20 + 6)
Bueno, todo esto lo he deducido sobre la marcha intentando que se pudiera demostrás con el menor número de operaciones posible. Pero yo no sé si utilizáis algún teorema más fuerte o alguna técnica mejor. Si me dijeras libro y capítulo miraría a ver si hay algo. Asi he usado propiedades más o menos elementales de las congruencias.
Ya me dirás si te sirve y si necesitas explicaciones pídelas, es que yo no sé hasta qué punto dominas lo que he hecho.
Buen trabajo, justamente esto es lo que andamos asiendo igual
Sólo que tengo varias dudas...
¿por qué en la parte 3^8 = 3^4 · 3^4 :~ 40·40 ~ (-1)(-1) :~ 1 (mod 41), por qué pusiste 40 por 40 y el -1 por el -1?
Luego al final...
¿Los dos están comprendidos entre 0 y 40 deben ser iguales para ser congruentes modulo 41?
Sin duda, necesito que me expliques todo todo todo, desde que pusiste "Hacemos cuantas aparte". La verdad si se lo que estás asiendo pero no sé porque pusiste varios números en esa parte.
Espero que me respondas. muchas gracias
La parte esa que decía de las cuentas aparte es para calcular el verdadero residuo de 3^20 modulo 41.
Se basa en unas algunas propiedades de las congruencias.
Si
a :~ b (mod m)
c :~ d (mod m)
entonces
ac :~ bd (mod m)
Y esta otra
a :~ a+km (mod m) para todo k € Z
Entonces
3^20 = 3^4 · 3^16 =
y queremos hallar números congruentes con 3^4 y 3^16 que faciliten las cuentas
3^4 = 81 :~ 40 (mod 41)
eso creo que no tiene dificultad
El segundo paso es calcular la congruencia de 3^8
3^8 = 3^4 · 3^4 :~ 40 ·40
podríamos haber tomado 1600 y hacer cuentas
1600 / 41 = 39.02...
1600 - 39·41 = 1600 - 1599 = 1
Pero es mucho más elegante sustituir los 40 por números congruentes aplicando la segunda propiedad
40 :~ 40 - 41 :~ -1 (mod 41)
asi tenemos
3^8 = 3^4 · 3^4 :~ 40 ·40 :~ (-1)(-1) :~ 1 (mod 41)
Como ves hemos llegado al mismo resultado pero sin cálculos apenas
Y el siguiente paso es calcular la congruencia de 3^16 aunque ahora que lo pienso no es necesario y no lo voy a hacer aparte
Tenemos
3^20 = 3^4 · 3^8 ·3^8 :~ 40 · 1 · 1 :~ 40 mod(41)
Esa es la congruencia verdadera de 3^20 que si se quiere se puede comprobar
3^20 = 348678441
3486784401 / 41 = 85043521.98
3486784401 - 41 · 85043521 = 3486784401 - 3486784361 =40
Pero si admitíamos que era divisible teníamos
3^20 :~5 (mod 41)
Y 5 y 40 no son congruentes módulo 41 porque si lo fueran se diferenciarían en un múltiplo de 41 y su diferencia es 35. Por eso decía que si dos números están entre 0 y 40 es imposible que sean congruentes módulo 41.
Luego absurdo y la hipótesis de que es divisible por 41 es falsa.
