El teorema de fermat
1. A) Si gcd(a, 35) = 1, muestre que a^(12) (es congruente con) 1(mod35).
[Ayuda: Del teorema de Fermat a^6 (es congruente con)1(mod7) y a^(4) (es congruente con) 1(mod5)].
b) Si gcd(a, 42) = 1, muestre que 168 = 3 · 7 · 8 divide a a^(6) - 1
[Ayuda: Del teorema de Fermat a^6 (es congruente con)1(mod7) y a^(4) (es congruente con) 1(mod5)].
b) Si gcd(a, 42) = 1, muestre que 168 = 3 · 7 · 8 divide a a^(6) - 1
1 Respuesta
Respuesta de Valero Angel Serrano Mercadal
1
Ni estudié esta asignatura ni se inglés, así que mal vamos. Pero algo se hará.
Cuando escribamos a = b (mod n) el = se debe interpretar como es congruente.
Usaremos la ayuda del teorema de Fermat.
Si mcd(a, 35)=1 significa que a no tiene factores primos 5 ó 7, porque en ese caso el mcd sería 5, 7 o 35. Luego dado p primo que no divide a a tenemos:
a^(p-1) = 1 (mod p)
Aplicado al 5 y 7 tenemos:
a^6 = 1 (mod 7) ==> (a^6)^2 = 1^2 (mod 7) ==> a^12 = 1 (mod 7)
a^4 = 1 (mod 5) ==> (a^4)^3 = 1^3 (mod 5) ==> a^12 = 1 (mod 5)
Luego:
a^12 = 1 + 7k = 1 + 5j con k,j € Z
7k = 5j ==> k es múltiplo de 5 y j lo es de 7 porque en la descomposición en factores primos de 7k debe aparecer un 5. Al igual que en la de 5j debe aparecer un 7.
Luego
a12 = 1 + 35 m ==>
a12 = 1 (mod 35)
Y con eso queda demostrado el ejercicio a)
--------------------
Igual que antes, a no puede ser divisible por 2, 3 y 7 porque entonces el mcd(a, 42) tendría un factor de esos o varios. Luego podemos usar el teorema de Fermat para los primos 2,3 y 7
Y por el teorema de Fermat
a = 1 (mod 2) ==> a^6 = 1 (mod 2)
a^2 = 1 (mod 3) ==> a^6 = 1 (mod 3)
a^6 = 1 (mod 7)
Pero esta vez pasa que necesitaríamos una congruencia mod 8 que no nos proporciona el teorema de Fermat. La obtendremos por nosotros mismos.
A no es par por lo que deciamos antes, luego
a = 1, 3, 5 ò 7 (mod 8), o
Entonces a ^2 = 1, 9, 25 , 49 (mod 8)
Pero casualmente eso es lo mismo que
a^2 = 1 (mod 8)
y por tanto
a^6 = 1 (mod 8)
de las tres congruencias calculadas de a^6 tenemos
a^6 = 1 + 8 k = 1 + 3j = 1 + 7m
8k = 3j = 7m
8k = 3j ==> k múltiplo de 3 y j múltiplo de 8
8k = 7m ==> k múltiplo de 7 y m múltiplo de 8
3j = 7m ==> j múltiplo de 7 y m múltiplo de 3
que es múltiplo de 3 y 7 luego múltiplo de 21
j es múltiplo de 8 y 7 luego múltiplo de 14
m es múltiplo de de 8 y 3 luego múltiplo de 6
a^6 = 1 + 8k = 1 + 8·3·7n = 1 + 168n
Luego a^6 - 1 = 168n
Luego 168 divide a a^6 - 1
Y eso es todo, espero que te sirva y lo hallas entendido. Si tienes alguna duda cosúltamela.
Cuando escribamos a = b (mod n) el = se debe interpretar como es congruente.
Usaremos la ayuda del teorema de Fermat.
Si mcd(a, 35)=1 significa que a no tiene factores primos 5 ó 7, porque en ese caso el mcd sería 5, 7 o 35. Luego dado p primo que no divide a a tenemos:
a^(p-1) = 1 (mod p)
Aplicado al 5 y 7 tenemos:
a^6 = 1 (mod 7) ==> (a^6)^2 = 1^2 (mod 7) ==> a^12 = 1 (mod 7)
a^4 = 1 (mod 5) ==> (a^4)^3 = 1^3 (mod 5) ==> a^12 = 1 (mod 5)
Luego:
a^12 = 1 + 7k = 1 + 5j con k,j € Z
7k = 5j ==> k es múltiplo de 5 y j lo es de 7 porque en la descomposición en factores primos de 7k debe aparecer un 5. Al igual que en la de 5j debe aparecer un 7.
Luego
a12 = 1 + 35 m ==>
a12 = 1 (mod 35)
Y con eso queda demostrado el ejercicio a)
--------------------
Igual que antes, a no puede ser divisible por 2, 3 y 7 porque entonces el mcd(a, 42) tendría un factor de esos o varios. Luego podemos usar el teorema de Fermat para los primos 2,3 y 7
Y por el teorema de Fermat
a = 1 (mod 2) ==> a^6 = 1 (mod 2)
a^2 = 1 (mod 3) ==> a^6 = 1 (mod 3)
a^6 = 1 (mod 7)
Pero esta vez pasa que necesitaríamos una congruencia mod 8 que no nos proporciona el teorema de Fermat. La obtendremos por nosotros mismos.
A no es par por lo que deciamos antes, luego
a = 1, 3, 5 ò 7 (mod 8), o
Entonces a ^2 = 1, 9, 25 , 49 (mod 8)
Pero casualmente eso es lo mismo que
a^2 = 1 (mod 8)
y por tanto
a^6 = 1 (mod 8)
de las tres congruencias calculadas de a^6 tenemos
a^6 = 1 + 8 k = 1 + 3j = 1 + 7m
8k = 3j = 7m
8k = 3j ==> k múltiplo de 3 y j múltiplo de 8
8k = 7m ==> k múltiplo de 7 y m múltiplo de 8
3j = 7m ==> j múltiplo de 7 y m múltiplo de 3
que es múltiplo de 3 y 7 luego múltiplo de 21
j es múltiplo de 8 y 7 luego múltiplo de 14
m es múltiplo de de 8 y 3 luego múltiplo de 6
a^6 = 1 + 8k = 1 + 8·3·7n = 1 + 168n
Luego a^6 - 1 = 168n
Luego 168 divide a a^6 - 1
Y eso es todo, espero que te sirva y lo hallas entendido. Si tienes alguna duda cosúltamela.
