Risoluzione di una congruenza - impossibile comprendere un passaggio nella soluzione [duplicato]
Nuovo in congruenze e teoria dei numeri
Di seguito è riportato il testo del libro Joseph H. Silverman: A Friendly Introduction to Number Theory , 4a edizione, capitolo 8, pagina 56.
Risolvere
$4x\equiv 3 \pmod{19}$
moltiplicheremo entrambi i lati per $5$. Questo da
$20x\equiv 15 \pmod{19}$ - Passo 1
Ma $20\equiv 1\pmod{19}$, così $20x\equiv x\pmod{19}$ - Passo 2
Quindi la soluzione è
$x\equiv 15\pmod{19}$
Capisco fino al passaggio 2, non riesco a capire come si arrivi alla soluzione dal passaggio 2.
Come fa
$20x\equiv x \pmod{19}$
portare a
$x\equiv 15 \pmod{19}$
Dov'è finito il file $20$su LHS vai? Come ha fatto$x$ sulla destra vengono sostituiti da $15$?
Risposte
Penso che il problema qui riguardi le proprietà di base della congruenza.
In molti modi importanti, la congruenza si comporta esattamente come l'uguaglianza. Cioè, soddisfa le tre proprietà critiche:
$1)$ Riflessivo: $a\equiv a \pmod n$.
$2)$ Simmetrico: $a\equiv b \pmod n\iff b\equiv a \pmod n$
$3)$ Transitivo: $a\equiv b\pmod n$ e $b\equiv c\pmod n$ implicare $a\equiv c \pmod n$.
Ciascuno di questi discende facilmente dalla definizione centrale di congruenza.
Queste tre proprietà, insieme, rendono la congruenza un https://en.wikipedia.org/wiki/Equivalence_relation. Questa è una nozione importante di per sé .., in molti modi, puoi lavorare con le relazioni di equivalenza nello stesso modo in cui lavori con l'uguaglianza. Questo è ciò che sta succedendo nel calcolo dato.
In questo caso hai $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ quindi combinando la proprietà simmetrica e la proprietà transitiva ci ottiene $x\equiv {15}\pmod {19}$.
Come al solito, però, l'importante è il principio generale. Queste tre proprietà sono il motivo per cui le congruenze sono così utili e importanti ... assicurati di capire perché valgono.
Lo sottolineerò $\gcd(5,19)=1$. Da$5$ è coprimo al modulo, moltiplicato per $5$non cambia le soluzioni quindi queste due congruenze sono equivalenti 1
$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$
Da allora $x\equiv20x\pmod{19}$, quest'ultimo è equivalente a $x\equiv15\pmod{19}$.
Poiché i commenti qui (e alle altre risposte) hanno chiarito che questo è il problema principale, permettetemi di precisare l'ultima equivalenza in dettaglio. (Userò liberamente sia la simmetria che la transitività.)
- $x\equiv20x\pmod{19}$ e $20x\equiv15\pmod{19}$ implica $x\equiv15\pmod{19}$
- $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ implica $20x\equiv15\pmod{19}$
- Quindi abbiamo entrambi $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ e $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ che ci dà l'equivalenza $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.
1 Vedi, ad esempio:
Come nota a margine, menzionerò che esistono chatroom come https://chat.stackexchange.com/transcript/12070 e https://chat.stackexchange.com/transcript/77161. E c'è anche ilhttps://chat.stackexchange.com/transcript/36. Guarda anche:https://math.meta.stackexchange.com/q/26814#26817. (Lo sto menzionando principalmente perché ho visto che hai avuto diversi scambi di commenti. Se ci sono troppi commenti, potrebbe essere un segno che la discussione in chat potrebbe essere più adatta.)
Bene, $20\equiv 1 \mod 19$ e così $20\cdot x\equiv 1\cdot x\mod 19$.
Il resto è come l'hai spiegato: moltiplicare $4x\equiv 3\mod 19$ di $5$ su entrambi i lati dà $20x\equiv 15\mod 19$, cioè $x\equiv 15\mod 19$.
Da qui
$$20x\equiv 15 \mod19$$
ce l'abbiamo
$$20x=19x+x \implies 20x\equiv x \mod19$$
perciò
$$20x\equiv x\equiv 15 \mod19$$
Anzi per definizione
$$a\equiv b \mod n \iff a-b=kn$$
perciò $20x\equiv x \mod 19 $ da $20x-x=19x$.
Puoi dividere i lati della relazione risultante nel passaggio 1 essere i lati della relazione risultante nel passaggio 2:
$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$
⇒ $1 ≡ \frac {15} x \mod (19)$
⇒ $x ≡ 15 \mod (19)$