Resolver una congruencia: no puedo entender un paso en la solución [duplicar]

Aug 19 2020

Nuevo en congruencias y teoría de números

A continuación se muestra el texto del libro Joseph H. Silverman: Una introducción amistosa a la teoría de números , cuarta edición, capítulo 8, página 56.


Resolver

$4x\equiv 3 \pmod{19}$

multiplicaremos ambos lados por $5$. Esto da

$20x\equiv 15 \pmod{19}$ - Paso 1

Pero $20\equiv 1\pmod{19}$, entonces $20x\equiv x\pmod{19}$ - Paso 2

Por tanto, la solución es

$x\equiv 15\pmod{19}$


Entiendo que hasta el paso 2, no puedo entender cómo se llega a la solución del paso 2.

Cómo

$20x\equiv x \pmod{19}$
Conducir a
$x\equiv 15 \pmod{19}$

¿Dónde hizo el $20$en el LHS ir? Como lo hizo$x$ en el RHS ser reemplazado por $15$?

Respuestas

5 lulu Aug 19 2020 at 09:01

Creo que el problema aquí se refiere a las propiedades básicas de la congruencia.

De muchas formas importantes, la congruencia se comporta exactamente como la igualdad. Es decir, satisface las tres propiedades críticas:

$1)$ Reflexivo: $a\equiv a \pmod n$.

$2)$ Simétrico: $a\equiv b \pmod n\iff b\equiv a \pmod n$

$3)$ Transitivo: $a\equiv b\pmod n$ y $b\equiv c\pmod n$ implicar $a\equiv c \pmod n$.

Cada uno de estos se deriva fácilmente de la definición básica de congruencia.

Esas tres propiedades, juntas, hacen de la congruencia un https://en.wikipedia.org/wiki/Equivalence_relation. Ésa es una noción importante en sí misma ..., de muchas maneras, puede trabajar con Relaciones de equivalencia de la misma manera que trabaja con Igualdad. Eso es lo que sucede en el cálculo dado.

En este caso tienes $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ así que la combinación de la propiedad simétrica y la propiedad transitiva nos lleva $x\equiv {15}\pmod {19}$.

Sin embargo, como de costumbre, lo importante es el principio general. Esas tres propiedades son la razón por la que las congruencias son tan útiles e importantes ... asegúrese de comprender por qué se mantienen.

1 MartinSleziak Aug 19 2020 at 08:34

Voy a enfatizar que $\gcd(5,19)=1$. Ya que$5$ es coprime al módulo, multiplicado por $5$no cambia las soluciones por lo que estas dos congruencias son equivalentes 1

$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$

Ahora desde $x\equiv20x\pmod{19}$, este último es equivalente a $x\equiv15\pmod{19}$.


Dado que los comentarios aquí (y las otras respuestas) aclararon que este es el problema principal, permítanme deletrear la última equivalencia en detalle. (Usaré libremente tanto la simetría como la transitividad).

  • $x\equiv20x\pmod{19}$ y $20x\equiv15\pmod{19}$ implica $x\equiv15\pmod{19}$
  • $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ implica $20x\equiv15\pmod{19}$
  • Entonces tenemos ambos $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ y $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ que nos da la equivalencia $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.

1 Ver, por ejemplo:


Como nota al margen, mencionaré que existen salas de chat como https://chat.stackexchange.com/transcript/12070 y https://chat.stackexchange.com/transcript/77161. Y también está elhttps://chat.stackexchange.com/transcript/36. Ver también:https://math.meta.stackexchange.com/q/26814#26817. (Menciono esto principalmente porque vi que tuvo varios intercambios en los comentarios. Si hay demasiados comentarios, eso podría ser una señal de que la discusión en el chat podría ser más adecuada).

Wuestenfux Aug 19 2020 at 08:21

Bien, $20\equiv 1 \mod 19$ y entonces $20\cdot x\equiv 1\cdot x\mod 19$.

El resto es como lo explicaste: Multiplicando $4x\equiv 3\mod 19$ por $5$ en ambos lados da $20x\equiv 15\mod 19$, es decir, $x\equiv 15\mod 19$.

user Aug 19 2020 at 08:22

De aquí

$$20x\equiv 15 \mod19$$

tenemos eso

$$20x=19x+x \implies 20x\equiv x \mod19$$

por lo tanto

$$20x\equiv x\equiv 15 \mod19$$

De hecho por definición

$$a\equiv b \mod n \iff a-b=kn$$

por lo tanto $20x\equiv x \mod 19 $ ya que $20x-x=19x$.

sirous Aug 19 2020 at 08:37

Puede dividir los lados de la relación que resultaron en el paso 1 y los lados de la relación que resultaron en el paso 2:

$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$

$1 ≡ \frac {15} x \mod (19)$

$x ≡ 15 \mod (19)$