Autor Tema: Coprimizar ecuación en Teorema Chino del Resto

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

12 Junio, 2017, 04:25 am
Leído 3013 veces

mathspirit

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 88
  • Karma: +0/-0
  • Sexo: Masculino
1) Hola! Tengo que resolver este sistema de ecuaciones de congruencia:

\( a \equiv{1} (mod 12) \)
\( a \equiv{7} (mod 10) \)
\( a \equiv{4} (mod 9) \)

En principio no parece un sistema incompatible ya que ningún número divide a otro. Sin embargo, no son coprimos dos a dos como pide le teorema chino del resto. En particular, 12 no es coprimo con 10 ni con 9.

¿Cómo se coprimiza antes de resolver el ejercicio?

12 Junio, 2017, 04:44 am
Respuesta #1

mathspirit

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 88
  • Karma: +0/-0
  • Sexo: Masculino
2) Y otra pregunta, ya que estoy... relacionada al TCR. Este sistema:

\( 3a\equiv{4} (mod5) \)
\( 5a\equiv{4} (mod6) \)
\( 6a\equiv{2} (mod7) \)

No puede usarse el TCR porque tiene números multiplicando a la variable a. Lo que calculo que se hace es primero resolver una por una las ecuaciones de congruencia, por ejemplo, la primera:

\( 3a\equiv{4} (mod5) \)

Es equivalente (si hice bien las cuentas) a:

\( a\equiv{3} (mod5) \)

Lo hice resolviendo la ecuación diofántica:

\( 3 X + 5 Y = 4 \)

12 Junio, 2017, 09:30 am
Respuesta #2

feriva

  • $$\Large \color{#a53f54}\pi\,\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 12,032
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola.

\( \dfrac{3a-4}{5}+\dfrac{5a-4}{6}+\dfrac{6a-2}{7}=b
  \) donde “b” es un entero

\( \dfrac{(3a-4)42+(51a-4)35+(6a-2)30}{210}=b
  \)

\( (3a-4)42+(51a-4)35+(6a-2)30=210b\Rightarrow
  \)

De ahí, despejando “a”, te sale una sola ecuación diofántica con “a” y “b”; pero ésta no es la forma habitual del teorema chino, se va haciendo hallando los inversos modulares para cada caso.

En cuanto a la primera pregunta, que no la había visto; ten en cuenta que 10 se descompones sólo en el producto de dos primos 2*5 y que el 2 es común con doce, así que lo puedes simplificar.
Ah, y el 3 del 12 también lo puedes quitar, porque es factor común con 9.Es decir, te quedan módulos: en vez de 12, cuatro, en vez de 10, cinco; y el nueve se queda igual.

Para que ya sea claro del todo; es decir, a partir de las congruencias tienes que

\( a-1
  \) dividido entre 12 es un entero; por la definición de congruencia.

\( a-7
  \) dividido entre 10 es un entero

\( a-4
  \) dividido entre 9 es un entero

Luega esta suma será un entero

\( \dfrac{a-1}{12}+\dfrac{a-7}{10}+\dfrac{a-4}{9}
  \)

El mínimo común múltiplo ¿qué factores tiene?, pues dos al cuadrado, tres al cuadrado y cinco, ésos son los módulos coprimos.

 


Spoiler
La forma en que lo he explicado creo que puede ser confusa, sabía lo quería decirte pero no sabía bien del todo cómo decirlo; viendo la respuesta de el_manco ya sí sé:

Una congruencia módulo “k” implica que existan implicitamente las congruencias módulo los divisores propios de “k”.

La idea es que al simplificar para llegar a los coprimos se tienen que conservar las congruencias según los múltiplos comunes. Si, por ejemplo, hubiera tomado 12/2= 6 quitando el 2 de la primera congruencia, hubiera eliminado la congruencia módulo 4; que es un divisor de 12 y que no existe en las otras dos; y al hacer eso nos hubiéramos cargado la relación de equivalencia. En cambio, al hacer 10/2=5, la congruencia módulo 2 sigue existiendo, porque tenemos en la otra módulo 4.

[cerrar]

Saludos.

12 Junio, 2017, 12:00 pm
Respuesta #3

Luis Fuentes

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

1) Hola! Tengo que resolver este sistema de ecuaciones de congruencia:

\( a \equiv{1} (mod 12) \)
\( a \equiv{7} (mod 10) \)
\( a \equiv{4} (mod 9) \)

En principio no parece un sistema incompatible ya que ningún número divide a otro. Sin embargo, no son coprimos dos a dos como pide le teorema chino del resto. En particular, 12 no es coprimo con 10 ni con 9.

¿Cómo se coprimiza antes de resolver el ejercicio?

La condición \( a \equiv{1} (mod 12) \) equivale a \( a \equiv{1} (mod 3) \) y \( a \equiv{1} (mod 4) \).
La condición \( a \equiv{7} (mod 10) \) equivale a \( a \equiv{7}\equiv 1 (mod 2) \) y \( a \equiv{7}\equiv 2 (mod 5) \).

La condición \( a \equiv{1} (mod 4) \) implica \( a \equiv{1} (mod 2) \) y \( a \equiv{4} (mod 9) \) implica  \( a \equiv{1} (mod 3) \).

Por tanto tu sistema equivale a:

 \( a \equiv{1} (mod 4) \)
 \( a \equiv{2} (mod 5) \)
 \( a \equiv{4} (mod 9) \)

Saludos.

18 Junio, 2017, 12:01 am
Respuesta #4

mathspirit

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 88
  • Karma: +0/-0
  • Sexo: Masculino
Hola, muchas gracias! Creo que pude resolver ambos ejercicios.

El primero me da:

\( a \equiv{157} (mod 180) \)

Y el segundo:

\( a\equiv{68} (mod 210) \)