Teorema de fermat.
2) Deduzca cada una de las siguientes congruencias
a) a^(21) (es congruente con) a(mod15) para todo a.
[Ayuda: Por el teorema de Fermat a^(5) (es congruente con) a(mod15)]
c) a^(13) (es congruente con) a(mod3 · 7 · 13) para todo a.
d) a^(9) (es congruente con) a(mod30) para todo a
a) a^(21) (es congruente con) a(mod15) para todo a.
[Ayuda: Por el teorema de Fermat a^(5) (es congruente con) a(mod15)]
c) a^(13) (es congruente con) a(mod3 · 7 · 13) para todo a.
d) a^(9) (es congruente con) a(mod30) para todo a
1 respuesta
Respuesta de Valero Angel Serrano Mercadal
1
¡Uy, transcribiste mal y me volví medio loco!
La pista decía:
a) a^5 = a (mod 5)
También el teorema de Fermat dice esta otra:
b) a^3 = a (mod 3)
elevando la primera al cubo y la segunda a la quinta
c) a^15 = a^3 (mod 5)
a^15 = a^5 (mod 3)
En esta segunda aplicaremos reiteradamente la congruencia b)
d) a^15 = a^3 · a^2 (mod 3) = a · a^2 (mod 3) = a^3 (mod 3) = a (mod 3)
De c) y d) tenemos
e) a^15 = a^3 + 5k
a^15 = a + 3j
luego
a^3 + 5k = a + 3j
pero de b) tenemos
a^3 = a + 3 m
Luego
a + 3m + 5k = a + 3j
5k = 3(j+m) ==>
Que es múltiplo de 3 porque en el lado izquierdo aprececera el factor primo 3 en la descomposición.
Así que como en e) decia a^15 = a^3 + 5k tenemos
a^15 = a^3 + 15n ==>
a^15 = a^3 (mod 15)
AY, no sé si esto me llevará a la respuesta. Pero tengo que dejar el ordenador por unas cuantas horas y te lo mando ya aunque no está resuelto y a lo mejor hay que deshacer todo. No puntúes ni cierres aun porque no podría continuar respondiendo.
La pista decía:
a) a^5 = a (mod 5)
También el teorema de Fermat dice esta otra:
b) a^3 = a (mod 3)
elevando la primera al cubo y la segunda a la quinta
c) a^15 = a^3 (mod 5)
a^15 = a^5 (mod 3)
En esta segunda aplicaremos reiteradamente la congruencia b)
d) a^15 = a^3 · a^2 (mod 3) = a · a^2 (mod 3) = a^3 (mod 3) = a (mod 3)
De c) y d) tenemos
e) a^15 = a^3 + 5k
a^15 = a + 3j
luego
a^3 + 5k = a + 3j
pero de b) tenemos
a^3 = a + 3 m
Luego
a + 3m + 5k = a + 3j
5k = 3(j+m) ==>
Que es múltiplo de 3 porque en el lado izquierdo aprececera el factor primo 3 en la descomposición.
Así que como en e) decia a^15 = a^3 + 5k tenemos
a^15 = a^3 + 15n ==>
a^15 = a^3 (mod 15)
AY, no sé si esto me llevará a la respuesta. Pero tengo que dejar el ordenador por unas cuantas horas y te lo mando ya aunque no está resuelto y a lo mejor hay que deshacer todo. No puntúes ni cierres aun porque no podría continuar respondiendo.
Hola
Pues me puse a mirar y dice lo siguiente...
a) a^21 = a(mod15) para todo a.
[Ayuda: Por el teorema de Fermat a^5 = a(mod5)]
claro tomando el = como congruencia..... tenias toda la razon
Pues me puse a mirar y dice lo siguiente...
a) a^21 = a(mod15) para todo a.
[Ayuda: Por el teorema de Fermat a^5 = a(mod5)]
claro tomando el = como congruencia..... tenias toda la razon
Si era como decías yo había escrito mal...
Ya me estudié también el tema 4 de las congruencias para entender mejor y creo que tengo la respuesta.
Usaré todas las propiedades citadas en el tema 4. Recuerdo esta que es fundamental para el cálculo: a=b (mod n) ==> ac = bc (mod n)
a) a^21 = a(mod15) para todo a.
Por el teorema de Fermat
a^5 = a (mod 5)
(a^5)^4 = a^4 (mod 5)
a^20 = a^4 (mod 5)
(a^20)·a = (a^4)·a (mod 5)
a^21 = a^5 (mod 5)
Pero como deciamos antes que a^5 = a (mod 5)
a^21 = a (mod 5)
Aplicando el teorema de Fermat al primo 3 tenemos
a^3 = a (mod 3)
(a^3)^7 = a^7 (mod 3)
a^21 = a^7 (mod 3)
Descompongamos a^7 en (a^3)(a^3)a y teniendo en cuenta que a^3 = a (mod 3) y aplicando lo que demostraba arriba tenemos
a^21 = (a^3)(a^3)a (mod 3)
a^21 = a·a·a (mod 3)
a^21 = a^3 (mod 3)
a^21 = a (mod 3)
Resumiendo, tenemos estas dos congruencias:
a^21 = a (mod 5)
a^21 = a (mod 3)
Que vienen a decir:
a^21 = a + 5k
a^21 = a + 3j
Igualando:
a + 5k = a + 3j
5k = 3j
Y esto significa que que es múltiplo de 3 y j es múltiplo de 5, puesto que que tendrá que tener el factor primo 3 que aparece en el otro miembro y viceversa.
Luego
a^21 = a + 5k = a + 5(3i) = a +15i ==>
a21 = a (mod 15)
--------
c) a^(13) (es congruente con) a(mod 3 · 7 · 13) para todo a.
Del teorema de Fermat
a^3 = a (mod 3) ==> Elevando a la cuarta y multiplicando por a
a(a^3)^4 = a·(a^4) (mod 3) ==>
Haciendo operaciones y teniendo en cuenta a^3 = a (mod 3)
a^13 = a·a·a^3 (mod n)
a^13 = aaa (mod n)
a^13 = a (mod 3)
De nuevo por el teorema de Fermat tenemos:
a^7 = a (mod 7) ==> multiplicando por a^6
(a^7)a^6 = a·a^6 (mod 7)
a^13 = a^7 (mod 7)
a^13 = a (mod 7)
Y usando por tercera vez el teorema tenemos y uniedo los resultados anteriiores tenemos este sistema de tres congruencias:
a^13 = a (mod 3)
a^13 = a (mod 7)
a^13 = a (mod 13)
Operando como hicimos en el ejercicio anterior
a13 = a + 3i = a + 7j = a +13 k
3i = 7j = 13 k
i debe ser múltiplo de 7 y múltiplo de 13 Luego i = 7·13·m
a^13 = a + 3i = a + 3(7·13·m)
Luego
a^13 = a mod (3·7·13)
---------------
d) a^(9) (es congruente con) a(mod30) para todo a
Descompongamos 30 en factores primos. 30 = 2·3·5
Apliquemos el teorema de Fermat a estos factores primos:
a^2 = a (mod 2)
Que complicada es la notación de las congruencias para escribir cadenas de cálculo. La siguiente línea tiene iguales auténticos e iguales de congruencias en (mod 2), con := denotaré los de las congruencias. Si me acuerdo usaré := en adelante, pero si se me olvida ten en cuenta que (mod n) detrás también indica que es una congruencia.
a^9 = a(a^2)^4 := a(a)^4 = a·(a^2)^2 := a·a^2 := a·a := a Resumiendo
a^9 := a (mod 2)
Otro
a^3 := a (mod 3)
a^9 = (a^3)^3 := a^3 := a Luego
a^9 := a (mod 3)
Y el final
a^5 := a (mod 5)
a^9 = (a^5)(a^4) := a(a^4) = a^5 := a Luego
a^9 := a (mod 5)
Ya tenemos el sitema de tres congruencias
a^9 := a (mod 2)
a^9 := a ( mod 3)
a^9 := a (mod 5)
Y el final es igual que en de los otros dos ejercicios dando como resultado:
a^9 := a (mod 2·3·5)
a^9 := a (mod 30)
Y eso es todo, espero que te sirva y lo hallas entendido. No es nada difícil creo. No olvides eso.
Usaré todas las propiedades citadas en el tema 4. Recuerdo esta que es fundamental para el cálculo: a=b (mod n) ==> ac = bc (mod n)
a) a^21 = a(mod15) para todo a.
Por el teorema de Fermat
a^5 = a (mod 5)
(a^5)^4 = a^4 (mod 5)
a^20 = a^4 (mod 5)
(a^20)·a = (a^4)·a (mod 5)
a^21 = a^5 (mod 5)
Pero como deciamos antes que a^5 = a (mod 5)
a^21 = a (mod 5)
Aplicando el teorema de Fermat al primo 3 tenemos
a^3 = a (mod 3)
(a^3)^7 = a^7 (mod 3)
a^21 = a^7 (mod 3)
Descompongamos a^7 en (a^3)(a^3)a y teniendo en cuenta que a^3 = a (mod 3) y aplicando lo que demostraba arriba tenemos
a^21 = (a^3)(a^3)a (mod 3)
a^21 = a·a·a (mod 3)
a^21 = a^3 (mod 3)
a^21 = a (mod 3)
Resumiendo, tenemos estas dos congruencias:
a^21 = a (mod 5)
a^21 = a (mod 3)
Que vienen a decir:
a^21 = a + 5k
a^21 = a + 3j
Igualando:
a + 5k = a + 3j
5k = 3j
Y esto significa que que es múltiplo de 3 y j es múltiplo de 5, puesto que que tendrá que tener el factor primo 3 que aparece en el otro miembro y viceversa.
Luego
a^21 = a + 5k = a + 5(3i) = a +15i ==>
a21 = a (mod 15)
--------
c) a^(13) (es congruente con) a(mod 3 · 7 · 13) para todo a.
Del teorema de Fermat
a^3 = a (mod 3) ==> Elevando a la cuarta y multiplicando por a
a(a^3)^4 = a·(a^4) (mod 3) ==>
Haciendo operaciones y teniendo en cuenta a^3 = a (mod 3)
a^13 = a·a·a^3 (mod n)
a^13 = aaa (mod n)
a^13 = a (mod 3)
De nuevo por el teorema de Fermat tenemos:
a^7 = a (mod 7) ==> multiplicando por a^6
(a^7)a^6 = a·a^6 (mod 7)
a^13 = a^7 (mod 7)
a^13 = a (mod 7)
Y usando por tercera vez el teorema tenemos y uniedo los resultados anteriiores tenemos este sistema de tres congruencias:
a^13 = a (mod 3)
a^13 = a (mod 7)
a^13 = a (mod 13)
Operando como hicimos en el ejercicio anterior
a13 = a + 3i = a + 7j = a +13 k
3i = 7j = 13 k
i debe ser múltiplo de 7 y múltiplo de 13 Luego i = 7·13·m
a^13 = a + 3i = a + 3(7·13·m)
Luego
a^13 = a mod (3·7·13)
---------------
d) a^(9) (es congruente con) a(mod30) para todo a
Descompongamos 30 en factores primos. 30 = 2·3·5
Apliquemos el teorema de Fermat a estos factores primos:
a^2 = a (mod 2)
Que complicada es la notación de las congruencias para escribir cadenas de cálculo. La siguiente línea tiene iguales auténticos e iguales de congruencias en (mod 2), con := denotaré los de las congruencias. Si me acuerdo usaré := en adelante, pero si se me olvida ten en cuenta que (mod n) detrás también indica que es una congruencia.
a^9 = a(a^2)^4 := a(a)^4 = a·(a^2)^2 := a·a^2 := a·a := a Resumiendo
a^9 := a (mod 2)
Otro
a^3 := a (mod 3)
a^9 = (a^3)^3 := a^3 := a Luego
a^9 := a (mod 3)
Y el final
a^5 := a (mod 5)
a^9 = (a^5)(a^4) := a(a^4) = a^5 := a Luego
a^9 := a (mod 5)
Ya tenemos el sitema de tres congruencias
a^9 := a (mod 2)
a^9 := a ( mod 3)
a^9 := a (mod 5)
Y el final es igual que en de los otros dos ejercicios dando como resultado:
a^9 := a (mod 2·3·5)
a^9 := a (mod 30)
Y eso es todo, espero que te sirva y lo hallas entendido. No es nada difícil creo. No olvides eso.
