viernes, 4 de junio de 2010

Problema del día: 4 de junio

Las sucesiones (a_n) y (b_n) se definen así:

a_{0}=1, b_{0}=4 y

a_{n+1}=a_{n}^{2001}+b_{n}, b_{n+1}=b_{n}^{2001}+a_{n}

Demuestra que 2003 no es divisor de ninguno de los términos de estas sucesiones.

9 comentarios:

DANIELIMO dijo...

(a_{n+1})(b_{n+1}) = (a_{n}^{2001}+b_{n}) (b_{n}^{2001}+a_{n}) congruente con 2 + 1/a_{n}b_{n} + a_{n}b_{n} (mod 2003) (2003 es primo)

(a_{n+1})(b_{n+1}) congruente con
2 + 1/a_{n}b_{n} + a_{n}b_{n} =
(2a_{n}b_{n} + 1 + [a_{n}b_{n}]^2)/
a_{n}b_{n} = [a_{n}b_{n} + 1]^2/
a_{n}b_{n}

suponemos por induccion que a_{n}b_{n} es residuo cuadratico modulo 2003 y que no es divisible entre 2003, es facil checar la base con a_0*b_0 y por lo de arriba es facil ver que (a_{n+1})(b_{n+1}) teniendo en cuenta que como 2003 es congruente con 3 mod 4 entonces -1 no es residuo mod 2003
y acabamos

DANIELIMO dijo...

solución:
no se si sea muy claro lo que acabo de poner, pero por si a caso va en resumen mi idea. usamos inducción, en a_n*b_n suponiendo que es distinto de 0 y es un residuo cuadratico mod 2003 es facil ver que la base cumple. Viendo que 2003 es primo, usando la formula de recursion, el pequeño teorema de fermat y viendo que como a_n*b_n es primo relativo con 2003 podemos pasar dividiendo llegamo a que:
(a_{n+1})(b_{n+1}) es congruente a [a_{n}b_{n} + 1]^[2]/a_{n}b_{n} (mod2003)
y como 2003 congruente con 3 (mod4)
entonces -1 no es residuo cuadratico (facil de ver por fermat) entonces el numerador es distinto de 0 y es un residuo cuadratico, y el denominador es tambien un residuo cuaratico, lo que completa la inducción.

me gusto el problema

Flavio dijo...

Aqui esta mi solucion:
Primero veamos que si 2003 no divide a h entonces h^2002 congruente a 1 modulo 2003, por
teorema de fermat, ya que 2003 es primo, y ademas no existe entero f tal que 2003 | f^2+1
ya que 2003 es un primo de la forma 4r+3
Probare por induccion que:
a) 2003 no divide a a_k*b_k
b) a_k*b_k es residuo cuadratico modulo 2003.
Caso base:
k=0
2003 no divide a 4*1=4
4*1=2^2 es residuo cuadratico modulo 2003.
Hipotesis:
se vale para k=n
Luego
a_n+1*b_n+1 congruente a (a_n^2001+b_n)*(b_n^2001+a_n) mod 2003
congruente a a_n^2002+a_n*b_n+b_n^2001+(a_n*b_n)^2001
pero como 2003 no divide a a_n*b_n (por hipotesis)
entonces 2003 no divide a ninguno de los dos
entonces
a_n^2002 congruente a b_n^2002 congruente a 1
entonces
a_n+1*b_n+1 congruente a 2+a_n*b_n+(a_n*b_n)^2001 mod 2003
pero (a_n*b_n)^2002 congruente a 1 mod 2003, entonces
a_n*b_n congruente a (a_n*b_n)^2003
y 2 congruente a 2*(a_n*b_n)^2002
a_n+1*b_n+1 congruente a 2*(a_n*b_n)^2002+(a_n*b_n)^2003+(a_n*b_n)^2001 mod 2003
congruente a (a_n*b_n)^2001*(2*(a_n*b_n)+(a_n*b_n)^2+1) mod 2003
pero a_n*b_n es residuo cuadratico, y el factor derecho es (a_n*b_n+1)^2 que tambien
es residuo cuadratico, entonces a_n+1*b_n+1 tambien es residuo cuadratico.
luego si 2003 | a_n+1*b_n+1 entonces
2003 | (a_n*b_n)^2001*((a_n*b_n + 1)^2)
pero como 2003 no divide a a_n*b_n entonces son primos relativos y entonces
2003 | (a_n*b_n + 1)^2
entonces com 2003 es primo
2003 | a_n*b_n + 1
pero como a_n*b_n es residuo cuadratico entonces a_n*b_n es congruente a x^2 mod 2003
para algun entero x pero entonces
2003 | x^2+1, pero como 2003 es un primo de la forma 4r+3 entonces no se puede
entonces 2003 no divide a a_n+1*b_n+1, lo que completa la induccion.
Entonces 2003 no divide a a_k*b_k para ninguna k>=0, entonces
2003 no divide a ninguno de a_k y b_k entonces 2003 no divide a ningun termino de la
sucesion, que es lo que queria demostrar.

El niño dijo...

¡Muy bien Daniel!

El niño dijo...

¡Muy bien Flavio! y muy bien explicado

José Luis Miranda Olvera dijo...

a0=1, b0=4.
Sea ix tal que ix(x) ≡1(mod 2003), x2001≡ ix para todo (x,2003)=1.

Supongamos que existe x tal que 2003 divide a ax+1 o bx+1, y que n es el numero mas pequeño que cumple. (am,2003)=1 para m<n
an+1≡ ian + bn ≡0(mod 2003) sii (an)ian + (an)bn ≡1+ (an)bn≡0(mod 2003) sii (an)bn ≡-1
sii 1+ (an)bn≡(bn)ibn + (an)bn ≡0(mod 2003) sii bn+1≡ ian + bn ≡0(mod 2003)

b2r≡4 a2r y a2k+1≡4 b2k+1(mod 2003) , para todo k tal que 2k+1≤n+1 y r tal que 2r≤n+1.
Ya que b0=4 a0 .
Si bm= 4am para m<n+1, entonces am+1≡ iam + bm ≡ 4(iam)( i4) + 4am ≡ 4(i4am+ am) ≡4(ibm+ am) ≡4( bm+1), analogamente si am = 4 bm entonces bm+1≡4(am+1).

Si n=2s entonces bn≡4 an(mod 2003) y (an)bn ≡(an)2 i4 ≡-1(mod 2003) entonces
(an)2 ≡-4(mod 2003) lo cual es una contradiccion ya que 2003 es un primo congruente con 3 (mod 4).
Análogamente si n=2s+1 entonces an ≡4 bn (mod 2003) y (bn)2 ≡-4(mod 2003) lo que es una contradicción.

José Luis Miranda Olvera dijo...

No permite subirlo con el formato que tenia, aqui esta la solucion otra vez.
a_0=1, b_0=4.
Sea i_x tal que i_x(x) ≡1(mod 2003), x^2001≡ i_x para todo (x,2003)=1. Por que 2003 es primo.

Supongamos que existe x tal que 2003 divide a a_x+1 o b_x+1, y que n es el numero mas pequeño que cumple. (a_m,2003)=1 para m<n
a_n+1≡ i_an + b_n ≡0(mod 2003) sii (a_n)i_an + (a_n)b_n ≡1+ (a_n)b_n≡0(mod 2003) sii (a_n)b_n ≡-1
sii 1+(a_n)b_n≡(b_n)i_bn + (a_n)b_n ≡0(mod 2003) sii b_n+1≡ i_an + b_n ≡0(mod 2003)

b_2r≡4(a_2r) y a_2k+1≡4 (b_2k+1)(mod 2003) , para todo k tal que 2k+1≤n+1 y r tal que 2r≤n+1.
Ya que b_0=4 a_0 .
Si b_m= 4_am para m<n+1, entonces a_m+1≡ i_am + b_m ≡ 4(i_am)( i_4) + 4_am ≡ 4(i_4am+ a_m) ≡4(i_bm+ a_m) ≡4( b_m+1), analogamente si a_m = 4 (b_m) entonces b_m+1≡4(a_m+1).

Si n=2s entonces b_n≡4(a_n)(mod 2003) y (a_n)b_n ≡(a_n)^2 i_4 ≡-1(mod 2003) entonces
(a_n)^2 ≡-4(mod 2003) lo cual es una contradiccion ya que 2003 es un primo congruente con 3 (mod 4).
Análogamente si n=2s+1 entonces a_n ≡4 b_n (mod 2003) y (b_n)^2 ≡-4(mod 2003) lo que es una contradicción.

Manuel Dosal dijo...
Este comentario ha sido eliminado por el autor.
Georges dijo...

SPG supongamos que a_r es primer número de la sucesión que es divisible entre 2003 entonces a_r congruente con 0. Si y solo si a_r(a_{r-1})=(a_r)(b_r)+1=0 mod 2003
Si y solo si (a_r)(b_r) congruente con -1 mod 2003 si y solo si b_r=0 mod 2003. Ahora si probamos que (a_r)(b_r) es residuo cuadratico mod 2003 siempre, entonces ya acabamos por que como 2003 es congruente con 3 mod 4 entonces -1 no es residuo cuadratico y entonces (a_{r-1})(b_{r-1}) nunca es congruente con -1 y entonces ninguno de (a_r) o (b_r) es divisible entre 2003.

Ahora como (a_0)(b_0)=4=2^2 entonces si es residuo cuadrático y es la base de inducción.

Ahora suponte que (a_i)(b_i) es residuo cuadratico, entonces (a_{i+1})(b_{i+1})= [(a_i)(b_i)]^2001+(a_i)^2002+(b_i)^2002+(a_i)(b_i)= [(a_i)(b_i)]^2001+[(a_i)(b_i)]^2002+[(a_i)(b_i)]^2003= ([(a_i)(b_i)]^2001)[(a_i)(b_i)+1]^2 que es claramente un residuo cuadratico debido a que (a_i)(b_i) lo es por la hipotesis de inducción.

Publicar un comentario