Memecahkan Kesesuaian - tidak dapat memahami langkah dalam solusi [duplikat]

Question

Baru mengenal kongruensi & Teori Bilangan

Di bawah ini adalah teks dari buku Joseph H. Silverman: A Friendly Introduction to Number Theory , 4th Edition, bab 8, halaman 56.

---

Menyelesaikan

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

kami akan mengalikan kedua sisi dengan $5$. Ini memberi

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

Tapi $20\equiv 1\pmod{19}$, jadi $20x\equiv x\pmod{19}$ - Langkah 2

Jadi solusinya adalah

$x\equiv 15\pmod{19}$

---

Saya memahami hingga langkah 2, saya tidak dapat memahami bagaimana seseorang sampai pada solusi dari Langkah 2.

Bagaimana

$20x\equiv x \pmod{19}$
menuju ke
$x\equiv 15 \pmod{19}$

Dimana $20$di LHS pergi? Bagaimana$x$ di kanan diganti dengan $15$?

Answer 1

Saya pikir masalah di sini menyangkut sifat dasar kongruensi.

Dalam banyak hal penting, kesesuaian berperilaku persis seperti kesetaraan. Artinya, ini memenuhi tiga sifat kritis:

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

$2)$ Simetris: $a\equiv b \pmod n\iff b\equiv a \pmod n$

$3)$ Transitif: $a\equiv b\pmod n$ dan $b\equiv c\pmod n$ berarti $a\equiv c \pmod n$.

Masing-masing mengikuti dengan mudah dari definisi inti kongruensi.

Ketiga sifat tersebut, bersama-sama, membuat kesesuaian https://en.wikipedia.org/wiki/Equivalence_relation. Itu adalah gagasan penting tersendiri .., dalam banyak hal, Anda dapat bekerja dengan Hubungan Ekuivalen dengan cara yang sama Anda bekerja dengan Kesetaraan. Itulah yang terjadi dalam perhitungan yang diberikan.

Dalam hal ini Anda punya $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ jadi menggabungkan Properti Simetris dan Properti Transitif mendapatkan kami $x\equiv {15}\pmod {19}$.

Namun seperti biasa, yang terpenting adalah prinsip umum. Ketiga sifat itu adalah mengapa kesesuaian sangat berguna dan penting ... pastikan Anda memahami mengapa kesesuaian itu berlaku.

Answer 2

Saya akan menekankan itu $\gcd(5,19)=1$. Sejak$5$ adalah coprime ke modulus, dikalikan dengan $5$tidak mengubah solusi sehingga kedua kongruensi ini setara ¹

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

Sekarang sejak $x\equiv20x\pmod{19}$, yang terakhir setara dengan $x\equiv15\pmod{19}$.

---

Karena komentar di sini (dan jawaban lain) mengklarifikasi bahwa ini adalah masalah utama, izinkan saya mengeja persamaan terakhir secara mendetail. (Saya akan dengan bebas menggunakan simetri dan transitivitas.)

• $x\equiv20x\pmod{19}$ dan $20x\equiv15\pmod{19}$ menyiratkan $x\equiv15\pmod{19}$
• $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ menyiratkan $20x\equiv15\pmod{19}$
• Jadi kita punya keduanya $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ dan $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ yang memberi kita kesetaraan $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.

---

¹ Lihat, misalnya:

• https://math.stackexchange.com/q/1845718
• https://math.stackexchange.com/q/1752523

---

Sebagai catatan tambahan, saya akan menyebutkan bahwa ada ruang obrolan seperti https://chat.stackexchange.com/transcript/12070 dan https://chat.stackexchange.com/transcript/77161. Dan ada jugahttps://chat.stackexchange.com/transcript/36. Lihat juga:https://math.meta.stackexchange.com/q/26814#26817. (Saya menyebutkan ini terutama karena saya melihat Anda memiliki beberapa pertukaran komentar. Jika ada terlalu banyak komentar, itu mungkin pertanda bahwa diskusi dalam obrolan mungkin lebih cocok.)

Answer 3

Baik, $20\equiv 1 \mod 19$ sehingga $20\cdot x\equiv 1\cdot x\mod 19$.

Selebihnya adalah bagaimana Anda menjelaskannya: Mengalikan $4x\equiv 3\mod 19$ oleh $5$ di kedua sisi memberi $20x\equiv 15\mod 19$, yaitu, $x\equiv 15\mod 19$.

Answer 4

Dari sini

$$20x\equiv 15 \mod19$$

kita punya itu

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

karena itu

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

Memang menurut definisi

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

karena itu $20x\equiv x \mod 19 $ sejak $20x-x=19x$.

Answer 5

Anda dapat membagi sisi-sisi relasi yang dihasilkan pada langkah 1 menjadi sisi-sisi relasi yang dihasilkan pada langkah 2:

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

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

⇒ $x ≡ 15 \mod (19)$