Autor Tema: Sistema de congruencias

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

20 Enero, 2007, 02:02 am
Leído 2682 veces

flematico

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 65
  • Karma: +0/-0
Saludos, tengo lo siguiente:

\( \begin{displaymath}
  \left\{ \begin{array}{ll}
            2x \equiv a \pmod{7}\\
            3x \equiv b \pmod{8}\\
            4x \equiv c \pmod{9}
          \end{array} \right.
\end{displaymath} \)

Me piden:
-Halla la solución general del sistema.
– Halla la menor solución positiva que tiene cuatro cifras y comprueba que
esta solución cumple las tres congruencias del sistema.


Yo de lo que he hecho es simplificar el sistema y aplicar la fórmula general de resolución de sistemas de congruencias:

\( \begin{displaymath}
  \left\{ \begin{array}{ll}
            x \equiv 4a \pmod{7}\\
            x \equiv 3b \pmod{8}\\
            x \equiv 7c \pmod{9}
          \end{array} \right.
\end{displaymath}

\begin{displaymath}
  x=2a \cdot 72\cdot 4a+3b \cdot 63 \cdot 3b+ 4c \cdot 56 \cdot 7c+ 7 \cdot 8 \cdot 9 \lambda =
  576a+567b+1568c+504 \lambda
\end{displaymath} \)

Esto último supongo que sería la solución general, ahora lo que no sé es cómo calcular los valores de las variables \( a,b,c \) para obtener la solución del último apartado.

¿alguna pista?

22 Enero, 2007, 09:03 am
Respuesta #1

Luis Fuentes

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

 
Citar
– Halla la menor solución positiva que tiene cuatro cifras y comprueba que
esta solución cumple las tres congruencias del sistema.

 Si no FIJAS previamente valores concretos de a,b y c, no se si esto tiene mucho sentido esta pregunta.

Me refiero a que para cualquier x, obviamente, siempre existen valores de a,b,c para los cuales se cumplen las tres ecuaciones. Entonces la menor solución positiva de cuatro fijas es x=1000 y hallas a tal que \( 2x\equiv{} a \), y lo mismo para b y c.

Saludos.

24 Enero, 2007, 03:55 am
Respuesta #2

flematico

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 65
  • Karma: +0/-0
Tienes razón, la verdad es que es una parte de un ejercicio más largo. Faltaba una primera parte que al realizarla te daba los datos que te faltaban en la segunda. Ahora tengo todos los datos pero sigue sin salirme:

\( \begin{displaymath}
  \left\{ \begin{array}{ll}
            2x \equiv 38 \pmod{7}\\
            3x \equiv 61 \pmod{8}\\
            4x \equiv 25 \pmod{9}
          \end{array} \right.
\end{displaymath} \)

\( \begin{displaymath}
  \left\{ \begin{array}{ll}
            x \equiv 4 \cdot 38 \pmod{7}\\
            x \equiv 3 \cdot 61 \pmod{8}\\
            x \equiv 7 \cdot 25 \pmod{9}
          \end{array} \right.
\end{displaymath} \)

\( \begin{displaymath}
  \left\{ \begin{array}{ll}
            x \equiv 5 \pmod{7}\\
            x \equiv 7 \pmod{8}\\
            x \equiv 4 \pmod{9}
          \end{array} \right.
\end{displaymath} \)

\( \begin{displaymath}
  x=3 \cdot 72 \cdot 5 +7 \cdot 63 \cdot 7+7 \cdot 56 \cdot 4+7 \cdot 8 \cdot 9 \lambda=191 +504 \lambda
\end{displaymath} \)

Pero al ir a comprobar el resultado:
\( x=191 -5= 186  \)   -->no es múltiplo de 7

No me sale correcto y a pesar de que lo he revisado varias veces y lo he rehecho de nuevo sigue sin salirme. Seguramente me estoy saltando algun detalle (calcular inversas o qué sé yo...).

A ver si alguien puede echarme una mano.

24 Enero, 2007, 08:38 am
Respuesta #3

Luis Fuentes

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

 Los que están mal son los coeficientes:

\(   x=\widehat{3} \cdot 72 \cdot 5 +\widehat{7} \cdot 63 \cdot 7+\widehat{7} \cdot 56 \cdot 4+7 \cdot 8 \cdot 9 \lambda= \)

que he marcado con el "sombrero".

El primero debería de ser la inversa de 9*8 módulo 7 ; el segundo (este lo tienes bien) la inversa de 7*9 módulo 8 ; el tercero la inversa de módulo 9 de 8*7.

Fíjate que \( 9*8\equiv{}_7=2 \) y 3 no es la inversa de 2 módulo 7.

Saludos.

P.D. Puedes leer sobre el tema aquí: http://www.famaf.unc.edu.ar/~cripto06/cursoPacetti.pdf (pág 6,7)

25 Enero, 2007, 01:46 am
Respuesta #4

flematico

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 65
  • Karma: +0/-0
Como bien dices calculaba mal las inversas.

Pongo la respuesta correcta, por si a alguien le interesa:

\(  \begin{displaymath}
        \left\{ \begin{array}{ll}
                  2x \equiv 38 \pmod{7}\\
                  3x \equiv 61 \pmod{8}\\
                  4x \equiv 25 \pmod{9}
                \end{array} \right.
      \end{displaymath}

      \begin{displaymath}
        \left\{ \begin{array}{ll}
                  x \equiv 4 \cdot 38 \pmod{7}\\
                  x \equiv 3 \cdot 61 \pmod{8}\\
                  x \equiv 7 \cdot 25 \pmod{9}
                \end{array} \right.
      \end{displaymath}


      \begin{displaymath}
        \left\{ \begin{array}{ll}
                  x \equiv 5 \pmod{7}\\
                  x \equiv 7 \pmod{8}\\
                  x \equiv 4 \pmod{9}
                \end{array} \right.
      \end{displaymath}
      Podemos aplicar la formula general, por tanto nos queda:
      \begin{displaymath}
        x=4 \cdot 72 \cdot 5 +7 \cdot 63 \cdot 7+6 \cdot 56 \cdot 4+7 \cdot 8 \cdot 9 \lambda=5647 +504 \lambda=103+504 \lambda
      \end{displaymath}
      Realizamos la comprobacion:\\\\
      $\begin{array}{c} 103-5\div 7\Rightarrow multiplo \quad de \quad 7\\
                        103-7\div 8\Rightarrow multiplo \quad de \quad 8\\
                        103-4\div 9\Rightarrow multiplo \quad de \quad 9\\
          \end{array}
      $ \)

14 Febrero, 2007, 03:43 am
Respuesta #5

Omega-3

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 10
  • Karma: +0/-0
Como bien dices calculaba mal las inversas.

Pongo la respuesta correcta, por si a alguien le interesa:

\(  \begin{displaymath}
        \left\{ \begin{array}{ll}
                  2x \equiv 38 \pmod{7}\\
                  3x \equiv 61 \pmod{8}\\
                  4x \equiv 25 \pmod{9}
                \end{array} \right.
      \end{displaymath}

      \begin{displaymath}
        \left\{ \begin{array}{ll}
                  x \equiv 4 \cdot 38 \pmod{7}\\
                  x \equiv 3 \cdot 61 \pmod{8}\\
                  x \equiv 7 \cdot 25 \pmod{9}
                \end{array} \right.
      \end{displaymath}


      \begin{displaymath}
        \left\{ \begin{array}{ll}
                  x \equiv 5 \pmod{7}\\
                  x \equiv 7 \pmod{8}\\
                  x \equiv 4 \pmod{9}
                \end{array} \right.
      \end{displaymath}
      Podemos aplicar la formula general, por tanto nos queda:
      \begin{displaymath}
        x=4 \cdot 72 \cdot 5 +7 \cdot 63 \cdot 7+6 \cdot 56 \cdot 4+7 \cdot 8 \cdot 9 \lambda=5647 +504 \lambda=103+504 \lambda
      \end{displaymath}
      Realizamos la comprobacion:\\\\
      $\begin{array}{c} 103-5\div 7\Rightarrow multiplo \quad de \quad 7\\
                        103-7\div 8\Rightarrow multiplo \quad de \quad 8\\
                        103-4\div 9\Rightarrow multiplo \quad de \quad 9\\
          \end{array}
      $ \)


Se ve interesante. Podrias decirme de que "Formula General" se trata para obtener a "x"?