Ejercicio de congruencia y MCD

Buenas gente, tengo este ejercicio que no me sale... Quizás puedan ayudarme.

Sea a Є Z tal que a Ξ 3 (4)

Hallar ( 13 a ^(n + 1) + 7 a : 8 a ^n + 4 ) para cada n Є N

Por favor, disculpen los simbolos! 🙁

Saludos

creo que lo tengo....

estamos buscando d/ d=( 13 a ^(n + 1) + 7 a : 8 a ^n + 4 ) entonces sabemos que

d|13.a^n.a+7a --> d|a(13a^n+7) --->d|a ó d|13a^n+7
y
d|8a^n+4 --> d|4(2a^n+1) ------> d|4 ó d|2a^n+1

vemos caso por caso (vamos a tener 4)
d|a y d|4 ----> d=1 por que aΞ 3 (4)

d|a y d|2^n+1 -----> d| (2a^n+1)-(2.a^(n-1).a) ---->d|1, d=1

d|13a^n+7 y d|2a^n+1 ---> d|(2.13.a^n+2.7)-(13.2.a^n+13.1)----> d|1

hasta ahora nada, sobre todo por que el resultado no depende de n pero en el ultimo caso

d|13a^n+7 y d|4-----lo que sabemos es que si d|4 entonces d=1,2,4

entonces me fijo a que es congruente 13a^n+7 modulo 4.... (no hago esa cuenta aca por que no se como escribirlo y que quede claro, hagan una tabla o algo asi) y las opcionoes son para los nΞ0 (4) y nΞ2(4) ---> 13a^n+7 Ξ 2 (4) ---->d=2
y
para los nΞ1 (4) y nΞ3(4) -----> 13a^n+7Ξ 0 (4) , osea, 4|13a^n+7

todo esto quiero decir que si n= 4k+1 o n=4k+3 el dcm=4
si n= 4k o n= 4k+2 el dcm =2

no se si esto esta bien, y espero que se entienda, ahora busco a alguien para que le pegue una leida y confirme todo lo dicho, si alguna parte no se entiende pueden pedirme que reescriba eso... pero no pretendan que use tex por que me vuelvo tonta en el intento

iscutiendo el problema me dicen que tengo un error y es que si d|a.b no siempre vale que d|a o d|b...asi que mañana sigo intentandolo por otro lado y lo corrijo, si encuntro una mejor solucion.

Kari escribió:

d|13.a^n.a+7a --> d|a(13a^n+7) ---> [ESTO NO ES CIERTO!!!] d|a ó d|13a^n+7
y
d|8a^n+4 --> d|4(2a^n+1) ------> [IDEM!!!] d|4 ó d|2a^n+1

Porejemplo, tenés que \(6\mid 2 \cdot 3\), pero \(6 \nmid 2\) y \(6 \nmid 3\)

Gracias a Santi que lo pensamos juntos

Tenemos que \(d \mid 13a^{n+1} +7a\) y \(d \mid 8a^n + 4\). Entonces, \(d \mid 8(13a^{n+1} +7a) - 13a(8a^n + 4) = 8 \cdot 13 a^{n+1} + 56a - 13 \cdot 8a^{n+1} - 52a = 4a\). Luego \(d \mid 4a\).

Afirmo que d y a son coprimos. Para eso, veamos lo siguiente:

Si \(p \mid a\), entonces \(p \mid 8a^n\). Si además \(p \mid d \mid 8a^n +4\), tenemos que \(p \mid 4\), luego \(p = 2\). Pero \(2 \nmid a\), porque a es impar. Luego d y a son coprimos, y por lo tanto, como \(d \mid 4a\), tenemos que \(d\mid 4\). Notar que \(4 \mid 8a^n + 4\).

Ahora, \(2 \mid 13 a^{n+1} + 7a\), porque a, 13 y 7 son impares. Así que \(2 \mid d\). Nos falta ver si \(d\) es 2 o 4. Eso se resuelve así. Para que sea 4, debe ocurrir que \(4 \mid 13 a^{n+1} + 7a\), es decir, \(13a^{n+1} + 7a \equiv 0 \ (4)\). Pero uno sabe que \(a \equiv 3 \equiv -1 \ (4)\), y por lo tanto \(a^{n+1} \equiv (-1)^{n+1} \ (4)\). Entonces, \(13 a^{n+1} + 7a \equiv (-1)^{n+1} + 3 \cdot 3 \equiv (-1)^{n+1} + 1 \ (4)\). ESto es congruente a 0 si y solo si n+1 es impar, es decir, si n es par.

Entonces concluimos que si n es par, el MCD es 4. Si es impar, el MCD es 2.

Perdón si faltan algunos detalles o un poco más de prolijidad, la idea es esa. Cualquier cosa, avisen.

\(\aleph_1\) amor...

Yo sabiendo que pueden ser 2 ó 4 use otra forma, que no sé si es válida:
\(a^1 \equiv 3 \ (4)\)

Entonces
si \(n\) es par: \(a^n \equiv 1 \ (4)\)
si \(n\) es impar: \(a^n \equiv 3 \ (4)\)

Sabiendo que \(8a^n+4\) es divisible por 2 y por 4, nos queda saber para qué casos 2 divide a \(13a^{n+1}+7a\)

si \(n\) es par, \(n+1\) es impar. entonces: \(13a^{n+1}+7a \equiv 13 3 + 7 3 \equiv 39 + 21 \equiv 60 \equiv 0 \ (4)\)
Entonces si \(n\) es par, \(4 | 13a^{n+1}+7a\) , entonces 4 es el MCD

si \(n\) es impar, \(n+1\) es par. entonces: \(13a^{n+1}+7a \equiv 13 1 + 7 3 \equiv 13 + 21 \equiv 41 \equiv 1 \ (4)\)
Entonces si \(n\) es par \(4 \nmid 13a^{n+1}+7a\) , entonces 4 no es el MCD, entonces 2 es el MCD.