การแก้ไขความสอดคล้อง - ไม่สามารถเข้าใจขั้นตอนในการแก้ปัญหา [ซ้ำกัน]
ใหม่สำหรับความสอดคล้องและทฤษฎีจำนวน
ด้านล่างนี้เป็นข้อความจากหนังสือ Joseph H.Silverman: A Friendly Introduction to Number Theory , 4th Edition, ตอนที่ 8, หน้า 56
เพื่อแก้ปัญหา
$4x\equiv 3 \pmod{19}$
เราจะคูณทั้งสองข้างด้วย $5$. สิ่งนี้ให้
$20x\equiv 15 \pmod{19}$ - ขั้นตอนที่ 1
แต่ $20\equiv 1\pmod{19}$ดังนั้น $20x\equiv x\pmod{19}$ - ขั้นตอนที่ 2
ดังนั้นวิธีแก้ปัญหาคือ
$x\equiv 15\pmod{19}$
ฉันเข้าใจถึงขั้นตอนที่ 2 แล้วฉันไม่เข้าใจว่ามีวิธีแก้ปัญหาจากขั้นตอนที่ 2 ได้อย่างไร
อย่างไร
$20x\equiv x \pmod{19}$
นำไปสู่
$x\equiv 15 \pmod{19}$
ไฟล์ $20$บน LHS ไป? ทำได้ไง$x$ ใน RHS จะถูกแทนที่ด้วย $15$เหรอ?
คำตอบ
ฉันคิดว่าปัญหานี้เกี่ยวข้องกับคุณสมบัติพื้นฐานของความสอดคล้องกัน
ในหลาย ๆ วิธีที่สำคัญความสอดคล้องจะมีพฤติกรรมเหมือนกับความเท่าเทียมกัน นั่นคือเป็นไปตามคุณสมบัติที่สำคัญสามประการ:
$1)$ สะท้อนกลับ: $a\equiv a \pmod n$.
$2)$ สมมาตร: $a\equiv b \pmod n\iff b\equiv a \pmod n$
$3)$ สกรรมกริยา: $a\equiv b\pmod n$ และ $b\equiv c\pmod n$ บ่งบอก $a\equiv c \pmod n$.
แต่ละสิ่งเหล่านี้ทำตามได้อย่างง่ายดายจากคำจำกัดความหลักของความสอดคล้องกัน
คุณสมบัติทั้งสามนี้รวมกันทำให้เกิดความสอดคล้องกัน https://en.wikipedia.org/wiki/Equivalence_relation. นั่นเป็นแนวคิดที่สำคัญในตัวมันเอง .. ในหลาย ๆ วิธีคุณสามารถทำงานกับ Equivalence Relations ได้แบบเดียวกับที่คุณทำงานกับ Equality นั่นคือสิ่งที่เกิดขึ้นในการคำนวณที่กำหนด
ในกรณีนี้คุณมี $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ ดังนั้นการรวม Symmetric Property และ Transitive Property ทำให้เราได้รับ $x\equiv {15}\pmod {19}$.
ตามปกติสิ่งที่สำคัญคือหลักการทั่วไป คุณสมบัติทั้งสามนี้เป็นสาเหตุที่ความสอดคล้องจึงมีประโยชน์และสำคัญมาก ... ตรวจสอบให้แน่ใจว่าคุณเข้าใจว่าเหตุใดจึงมี
ฉันจะเน้นว่า $\gcd(5,19)=1$. ตั้งแต่$5$ คือ coprime กับโมดูลัสคูณด้วย $5$ไม่เปลี่ยนวิธีแก้ปัญหาเพื่อให้ความสอดคล้องทั้งสองนี้มีค่าเท่ากัน1
$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$
ตั้งแต่ตอนนี้ $x\equiv20x\pmod{19}$หลังเทียบเท่ากับ $x\equiv15\pmod{19}$.
เนื่องจากความคิดเห็นที่นี่ (และสำหรับคำตอบอื่น ๆ ) ชี้แจงว่านี่เป็นปัญหาหลักให้ฉันสะกดรายละเอียดการเทียบเท่าครั้งสุดท้าย (ฉันจะใช้ทั้งสมมาตรและการเคลื่อนย้ายได้อย่างอิสระ)
- $x\equiv20x\pmod{19}$ และ $20x\equiv15\pmod{19}$ หมายถึง $x\equiv15\pmod{19}$
- $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ หมายถึง $20x\equiv15\pmod{19}$
- เราจึงมีทั้งสองอย่าง $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ และ $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ ซึ่งทำให้เรามีความเท่าเทียมกัน $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.
1ดูตัวอย่างเช่น:
ตามบันทึกด้านข้างฉันจะพูดถึงว่ามีห้องสนทนาเช่น https://chat.stackexchange.com/transcript/12070 และ https://chat.stackexchange.com/transcript/77161. และยังมีhttps://chat.stackexchange.com/transcript/36. ดูสิ่งนี้ด้วย:https://math.meta.stackexchange.com/q/26814#26817. (ฉันพูดถึงเรื่องนี้เป็นหลักเนื่องจากฉันเห็นว่าคุณมีการแลกเปลี่ยนความคิดเห็นหลายครั้งหากมีความคิดเห็นมากเกินไปนั่นอาจเป็นสัญญาณว่าการสนทนาในแชทอาจเหมาะสมกว่า)
ดี, $20\equiv 1 \mod 19$ และอื่น ๆ $20\cdot x\equiv 1\cdot x\mod 19$.
ส่วนที่เหลือคือวิธีที่คุณอธิบาย: การคูณ $4x\equiv 3\mod 19$ โดย $5$ ทั้งสองด้านให้ $20x\equiv 15\mod 19$กล่าวคือ $x\equiv 15\mod 19$.
จากที่นี่
$$20x\equiv 15 \mod19$$
เรามีสิ่งนั้น
$$20x=19x+x \implies 20x\equiv x \mod19$$
ดังนั้น
$$20x\equiv x\equiv 15 \mod19$$
แน่นอนโดยคำจำกัดความ
$$a\equiv b \mod n \iff a-b=kn$$
ดังนั้น $20x\equiv x \mod 19 $ ตั้งแต่ $20x-x=19x$.
คุณสามารถแบ่งด้านของความสัมพันธ์ได้ส่งผลให้ขั้นตอนที่ 1 เป็นด้านของความสัมพันธ์ซึ่งส่งผลให้ขั้นตอนที่ 2:
$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$
⇒ $1 ≡ \frac {15} x \mod (19)$
⇒ $x ≡ 15 \mod (19)$