Autor Tema: Teorema chino del resto

0 Usuarios y 1 Visitante están viendo este tema.

10 Noviembre, 2010, 03:54 pm
Leído 1117 veces

josepapaiii

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,061
  • Karma: +0/-0
  • Sexo: Masculino
Dados \( r_1,....r_n \)Primos relativos, entonces, el sistema formado por:

\( x\equiv{}a_1 (mod r_1) \)
\( x\equiv{}a_2 (mod r_2) \)
   .                                     
   .                                   
   .                                     
\( x\equiv{}a_n (mod r_n) \)

Tiene solución y es única módulo mcm de \( (r_1,........r_n) \)

Demostración

Lo haremos por inducción:

Lo vemos si es cierto para \( n=1 \);

\( x\equiv{}a_1 (mod r_1) \)

Entonces la solución es:

\( x=a_1+r_1t, \forall{t} \in{Z} \)

Como no lo veo claro, pruebo también con \( n=2 \)

\( x\equiv{}a_1 (mod r_1) \)
\( x\equiv{}a_2 (mod r_2) \)

Donde \( x=a_1+r_1t \)
Substituimos en la segunda ecuación:

\( x=a_1+r_1t\equiv{}a_2 (mod r_2) \)

Operamos:

\( t\equiv{}r_1^{-1}(a_2-a_1) (mod r_2) \)

Cuya solución es: \( t=r_1^{-1}(a_2-a_1)+r_2z, \forall{z}\in{Z} \)

Sustituyendo en \( t \) en \( x \): \( x=a_1+r_1[r_1^{-1}(a_2-a_1)+r_2z], \forall{z}\in{Z} \)

Lo supongo cierto para \( n-1 \)

\( x=a_{n-2}+r_{n-2}[r_1^{-1}*......*r_{n-2}(a_{n-1}-a_{n-2}-......-a_1)+r_{n-1}\alpha], \forall{\alpha }\in{Z} \)

Y probamos para n

\( x=a_{n-1}+r_{n-1}[r_1^{-1}*......*r_{n-1}(a_n-a_{n-1}-......-a_1)+r_n\beta], \forall{\beta }\in{Z} \)

¿Voy encaminado?

10 Noviembre, 2010, 05:58 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

 Puede ir bien encaminada. Pero tienes que tener un poco de cuidado con la notación.

 Cuando en el primer paso escribes \( r_1^{-1} \) te refieres al inverso de \( r_1 \) modulo \( r_2 \). Eso debe de quedar claro. Además para que ese inverso exista estás usando que \( r_1 \) y \( r_2 \) son primos entre si.

 Una vez aclarado esto te basta tener en cuenta a que has llegado a:

 \( x=b_2+r_1r_2z \) con \( z\in Z \) (que \( b \) sea igual a \( a_1+r_1(r_1^{-1}(a_2-a_1))) \) es indiferente).

 Por tanto tu tesis candidata a ser probada por inducción simplemente puede ser que existe una solución de las primeras \( k \) ecuaciones es:

 \( x=b_k+r_1r_2\ldots r_kz \) con \( z\in Z \)

 Finalmente una vez acabado todo esto tienes que probar la unicidad módulo \( m.c.m(r_1,\ldots,r_n) \). Pero eso es fácil teniendo en cuenta que la diferencia de dos posibles soluciones \( x,y \) cumple:

 \( x-y\equiv 0(mod\,r_i) \) para \( i=1,\ldots,n \)

Saludos.

11 Noviembre, 2010, 02:03 pm
Respuesta #2

josepapaiii

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,061
  • Karma: +0/-0
  • Sexo: Masculino
Hola el_manco, justo esa apreciación me ha hecho hoy el profesor, que tenga cuidado con la utilización del inverso de \( r_1 \), ya que como bien me puntualizaste ayer, es el inverso en módulo \( r_2 \). No obstante no estaba bien,entre otras cosas, se me han escapó esa puntualización. A seguir trabajando para mejorar.

Muchísimas gracias.