อ้างอิง:
ข้อความเดิมเขียนโดยคุณ MoDErN_SnC
สมมติว่าผมมีสมการคอนกรูเอนซ์
$x^2 - x \equiv 0 \pmod{30} $
ทีนี้ถ้าผมจะหาผลเฉลย ผมจะต้องมาพิจารณาสามสมการนี้ใช่ไหมครับ?
$x^2 - x \equiv 0 \pmod{2} $
$x^2 - x \equiv 0 \pmod{3} $
$x^2 - x \equiv 0 \pmod{5} $
|
ไม่แน่ใจว่าเป็นคำถามหรือเปล่า แต่ก็ขอตอบว่าถูกต้องแล้วครับ
อ้างอิง:
ข้อความเดิมเขียนโดยคุณ MoDErN_SnC
คำถามข้อต่อไปที่ผมสงสัยคือ สมมติแยกสมการ $x^2 + x + 7 \equiv 0 \pmod{3^3} $ นั่นหมายความว่า เราต้องลองหยิบ x ที่อยู่ใน $\mathbb{Z}_{27}$ ทุกตัวมาพิจารณาใช่ไหมครับ?
ถ้าไม่ใช่จะมีหลักเกณฑ์อะไรที่พิจารณาบ้างครับ?
|
อันนี้ไม่รู้แฮะ
สำหรับผม ขอตอบว่าใช่ครับ หรือถ้าให้ง่ายขึ้นอีกนิดนึงอาจพิจารณา ${0,\pm 1,\pm 2,...,\pm 13}$ แทน ${0,1,2,...,27}$ ก็ได้ครับ ซึ่งเป็นส่วนตกค้างบริบูรณ์ mod 27 เหมือนกัน
อีกวิธีที่ทำให้ง่ายขึ้นก็คือพยายามเปลี่ยนพหุนามด้านซ้ายให้สามารถแยกตัวประกอบได้ครับ
เช่นจากสมการด้านบน $0\equiv x^2 + x + 7 \equiv x^2 + x -20 \equiv (x+5)(x-4) \pmod{3^3}$
ถ้า modulo เป็นจำนวนเฉพาะ เราสามารถสรุปได้เลยครับว่า $x\equiv -5,4 \pmod{...}$
แต่ตรงนี้ 27 ไม่ใช่จำนวนเฉพาะ ฉะนั้นเรายังไม่สามารถบอกได้ว่า $x\equiv -5,4 \pmod{3^3}$ เท่านั้น อาจมีอันอื่นอีก แต่ก็คงทำให้การพิจารณาง่ายขึ้นครับ
อ้างอิง:
ข้อความเดิมเขียนโดยคุณ MoDErN_SnC
อยากทราบอีกครับว่า สรุปมาจากไหนว่ามี 6 คำตอบ มาจาก Chinese Remainder Theorem รึเปล่าครับ แล้วถ้ามันมาจริง ๆ มันมาได้อย่างไรครับ
|
ใช่แล้วครับ มาจาก Chinese Remainder Theorem (CRT) ส่วน "6 คำตอบ" มีที่มาดังนี้ครับ...
จาก CRT ที่ว่าระบบสมการ (เมื่อ $gcd(m_i,m_j)=1$ ทุก i,j)
$x\equiv a_1 \pmod {m_1}$
$x\equiv a_2 \pmod {m_2}$
...
$x\equiv a_k \pmod {m_k}$
มีคำตอบเดียวใน $\pmod{m_1m_2}$ คือ $x=\sum_{n = 1}^{k}A_iM_ia_i$
เมื่อ $M_i=\frac{m_1m_2...m_k}{m_i}$ และ $A_i$ เป็นอินเวอร์สของ $M_i\pmod {m_i}$
สำหรับกรณีที่มีแค่ 2 สมการ ก็เขียน x ในรูปง่ายๆก็คือ $x=A_1M_1a_1+A_2M_2a_2$
จะเห็นว่า $A_1,M_1,A_2,M_2$ มีค่าเดียว ฉะนั้นไม่มีผลกับจำนวนคำตอบ
แต่ตามตัวอย่างที่ให้มาจะพบว่า $a_1$ เป็นได้ 3 ค่า (4,13 และ 22) และ $a_2$ เป็นได้ 2 ค่า (0 และ 6)
ฉะนั้น โดย combinatorics จึงได้จำนวนคำตอบทั้งหมดคือ 3x2=6 คำตอบนั่นเองครับ