Autor Tema: Congruencia

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

21 Agosto, 2010, 02:03 am
Leído 1222 veces

Elvira psv

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 37
  • Karma: +0/-0
  • Sexo: Femenino
Hola, este ejercicio me lo pusieron en un examen de teoría de códigos y criptografía en febrero, no es un ejercicio muy propio de este tema, pero hace falta para saber resolver otras cosas, así  que si podéis ayudarme os lo agradecería.

a) Encontrar todas las soluciones de la congruencia:
\( x^2\equiv{210}\pmod {9991} \)
b) Sean p y q dos primos distintos impares ¿Cuántas soluciones tiene la congruencia
\( x^2\equiv{1}\pmod (pq) \)?

26 Agosto, 2010, 04:32 pm
Respuesta #1

Héctor Manuel

  • Lathi
  • Mensajes: 3,701
  • País: mx
  • Karma: +0/-0
  • Sexo: Masculino
Bien.  La idea es usar el siguiente teorema que es muy fuerte, pero sencillo, de congruencias:

Si \( p,q \) son primos relativos, entonces \( a\equiv{b}(modpq)\Longleftrightarrow{a\equiv{b}(mod p)\mbox{ y }a\equiv{b}(mod q)} \)

Spoiler
Demostración:

Si \( a\equiv{b}(modpq) \) entonces \( pq|a-b \) y como \( p|pq \) entonces \( p|a-b \).  Es decir, \( a\equiv{b}(modp) \).  Análogamente \( a\equiv{b}(modq) \)

Si \( a\equiv{b}(modp) \) y \( a\equiv{b}(modq) \) entonces \( p|a-b \) y \( q|a-b \).  Luego \( a-b=sp \) para algún entero \( s \) y \( a-b=tq \) para algún entero \( t \).  De ahí que \( sp=tq \).  Por tanto \( q|sp \) y como \( q,p \) son primos relativos, entonces \( q|s \).  De esta manera se deduce que \( s=uq \) y de ahí \( a-b=sp=uqp \).  Por tanto \( pq|a-b \).  Es decir \( a\equiv{b}(modpq) \)

[cerrar]

El resultado anterior se cumple en particular para \( p,q \) primos diferentes.

Ahora bien. 
Para (a):
Notar que \( 9991=97*103 \).
Por el teorema anterior, se tiene \( x^2\equiv{210}(mod9991)\Longleftrightarrow{x^2\equiv{210}(mod97)}\mbox{ y }x^2\equiv{210}(mod103) \).

Pero lo anterior es equivalente a que \( x^2\equiv{16(mod97)} \) y \( x^2\equiv{4}(mod103) \).
Es decir, si y sólo si \( 97|(x-4)(x+4) \) y \( 103|(x-2)(x+2) \). 

Como 97 y 103 son primos, lo anterior equivale a que (\( 97|x-4 \) ó \( 97|x+4 \)) y (\( 103|x-2 \) ó \( 103|x+2 \))

Esto es, en resumen, \( x^2\equiv{210}(mod9991) \) si y sólo si \( x\equiv{\pm{4}(mod97)} \) y \( x\equiv{\pm{2}(mod103)} \)

Veamos por casos:  Supongamos que \( x\equiv{2}(mod103) \).  Es decir \( x=103k+2 \).  Como \( x\equiv{\pm{4}(mod97)} \), entonces sustituyendo se tiene: \( 103k+2\equiv{\pm{4}(mod97)} \) y como \( 103\equiv{6}(mod97) \) entonces \( 6k+2\equiv{\pm{4}(mod97)} \).

Como \( mcd(2,97)=1 \) podemos dividir la congruencia anterior entre 2 y obtener \( 3k+1\equiv{\pm{2}(mod97)} \).
Luego \( 3k\equiv{1} \) ó \( 3k\equiv{-3} \), ambas en módulo 97.
Multiplicando ambas congruencias por 32: \( 96k\equiv{32} \) ó \( 96k\equiv{-96} \) y como \( 96\equiv{-1} \), entonces \( -k\equiv{32}(mod97) \) ó \( -k\equiv{-96}(mod97) \), lo cual equivale a \( k\equiv{-32}\equiv{65} \) ó \( k\equiv{96} \), ambas en módulo 97.  De esta forma tenemos que \( k=97s+65 \) ó \( k=97s+96 \)

Y como \( x=103k+2 \), se tiene \( x=103(97s+65)+2=9991s+6697 \) ó bien \( x=103k+2=103(97s+96)+2=9991s+9890 \).
En resumen, \( x\equiv{2}(mod103) \) y \( x\equiv{\pm{4}(mod97)} \) si y sólo si \( x\equiv{6697}(mod9991) \) ó \( x\equiv{9890}(mod9991) \).

Analiza el caso \( x\equiv{-2}(mod103) \).  Deberás obtener al final que \( x\equiv{101}(mod9991) \) ó \( x\equiv{3294}(mod9991) \).

Se concluye que las solucinones a \( x^2\equiv{210(mod9991)} \) son
\( x\equiv{6697}(mod9991) \)
\( x\equiv{9890}(mod9991) \)
\( x\equiv{101}(mod9991) \)
\( x\equiv{3294}(mod9991) \).

Ahora usa la misma idea para (b).

Saludos