Autor Tema: Sistema de congruencias

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

09 Enero, 2011, 10:22 pm
Leído 1600 veces

tntboom

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 43
  • Karma: +0/-0
  • Sexo: Masculino
Tengo que resolver el siguiente problema pero no tengo muy claro por donde empezar,

Encontrar el menor número positivo que dividido por 18,30,42 se obtenga siempre el mismo resto: 19.

Creo que hay que resolver un sistema de congruencias, pero no se como plantearlas.

Muchas gracias.

12 Enero, 2011, 09:55 pm
Respuesta #1

tntboom

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 43
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Creo que es sistema a resolver es

\( x\equiv{19 (mod 18)} \)
\( x\equiv{19 (mod 30)} \)
\( x\equiv{19 (mod 42)} \)

¿Voy o el planteamiento no es correcto?

Muchas gracias.

13 Enero, 2011, 04:44 pm
Respuesta #2

tntboom

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 43
  • Karma: +0/-0
  • Sexo: Masculino
Bueno creo que el sistema no tiene solución, ya que aunque

\( m.c.d(1,18)=1 \)
\( m.c.d(1,30)=1 \)
\( m.c.d(1,42)=1 \)

Aplicando el Teorema Chino del Resto, los modulos de las ecuaciones deberían ser primos entre sí 2 a 2, y esto no se cumple con el 18 y el 30
ya que \( m.c.d(18,30)=6\neq{1} \) por lo que no son primos entre sí 2 a 2  y por lo que el sistema no tiene solución y en consecuencia no existe un número entero que dividido por 18, 30 y 42 tenga como resto siempre 19.

Por favor, necesito saber si la argumentación es válida o me equivoco en algo.

Muchas gracias.


13 Enero, 2011, 05:37 pm
Respuesta #3

Héctor Manuel

  • Lathi
  • Mensajes: 3,701
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
mmm falso.  Por lo mismo de que (18,30), (30,42),(18,42)\( \neq1 \), no puedes aplicar el teorema chino del residuo.

Por otra parte, veamos la siguiente proposición:

\( at\equiv bt(mod m) \) si y sólo si \( a\equiv b\left(mod\displaystyle\frac{m}{(m,t)}\right) \).  Es decir, para dividir en una congruencia hay que dividir el módulo apropiadamente.

Spoiler
Demostración:
Sea \( d=(m,t) \). Por tanto \( m=m'd \) y \( t=t'd \) donde \( (m',t')=1 \). Luego:
\( at\equiv bt(modm) \) si y sólo si \( m|t(a-b) \), si y sólo si \( t(a-b)=mk \) para alguna \( k \), si y sólo si \( t'(a-b)=m'k \), si y sólo si \( m'|t'(a-b) \), y como \( (m',t')=1 \), la anterior relación de divisibilidad es cierta si sólo si \( m'|a-b \), o equivalentemente, \( a\equiv b(mod m') \), donde \( m'=\displaystyle\frac{m}{(t,m)} \). 
[cerrar]

En tu ejercicio:

De la primera congruencia, tenemos que \( x\equiv{1}(mod 18) \), y por tanto es de la forma \( x=18t+1 \).  Sustituyendo en la segunda congruencia, obtenemos \( 18t+1\equiv 19(mod30) \), que equivale a \( 18t\equiv18(mod30) \).  Como \( (18,30)=6 \), entonces por la proposición que te dí podemos dividir todo entre 6, quedando \( 3t\equiv3(mod 5) \).

Esto significa que \( 5|3(t-1) \), y como \( (5,3)=1 \), entonces \( 5|t-1 \).  Es decir, \( t \) es de la forma \( t=5m+1 \).

Como \( x=18t+1 \), entonces \( x=18(5m+1)+1=90m+19 \).  Sustituyendo en la tercera congruencia:
\( 90m+19\equiv19(mod42) \), y al ser \( 90\equiv6(mod42) \), tenemos \( 6m\equiv0(mod42) \).  Nuevamente, por la proposición dada al inicio, al ser \( (6,42)=6 \) tenemos \( m\equiv0(mod7) \).  Por tanto \( m \) es de la forma \( m=7r \).

Pero como \( x=90m+19 \), entonces \( x=90(7r)+19=630r+19 \).   Luego, \( 630|x-19 \), y por tanto, de existir solución al sistema origina, ésta debe ser \( x\equiv 19(mod630) \). 

Verifica que realemente estas \( x \) cumplen lo pedido.

Saludos.

13 Enero, 2011, 11:41 pm
Respuesta #4

tntboom

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 43
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Muchas gracias, he entendido perfectamente el procedimiento para la resolución, y que no puedo aplicar el teorema chino del resto, pero hay un paso que no termino de tener claro y es

Citar
\( 90m+19\equiv19(mod42) \), y al ser \( 90\equiv6(mod42) \), tenemos \( 6m\equiv0(mod42) \)

No entiendo por que  \( 90\equiv6(mod42) \), ¿No sería  \( 90\equiv0(mod42) \)?

13 Enero, 2011, 11:57 pm
Respuesta #5

Héctor Manuel

  • Lathi
  • Mensajes: 3,701
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
No... recuerda que \( a\equiv b(mod m) \) si y sólo si \( m|a-b \).  Es claro que \( 42\not|90 \), pero \( 42|90-6 \), ya que \( 90-6=84=42*2 \).

Saludos.