ผลเฉลยของสมการคอนกรูเอนซ์กำลังสอง

[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} $
ซึ่งถ้าสามสมการนี้มันจะได้ $x \equiv 0,1 \pmod{2}, x \equiv 0,1 \pmod{3}, x \equiv 0,1 \pmod{5}$
ทีนี้ผมลองเปิดดูในหนังสือ สอวน. จากตัวอย่าง
สมการ $x^2 + x + 7 \equiv 0 \pmod{189} $ ก็แยกสมการ แล้วก็หาคำตอบของสมการ
คำถามข้อต่อไปที่ผมสงสัยคือ สมมติแยกสมการ $x^2 + x + 7 \equiv 0 \pmod{3^3} $ นั่นหมายความว่า เราต้องลองหยิบ x ที่อยู่ใน $\mathbb{Z}_27$ ทุกตัวมาพิจารณาใช่ไหมครับ?
ถ้าไม่ใช่จะมีหลักเกณฑ์อะไรที่พิจารณาบ้างครับ?
จากสมการตัวอย่างอันหลังที่ว่า เขาก็สรุปว่า คำตอบของสมการ $x^2 + x + 7 \equiv 0 \pmod{3^3} $ มีผลเฉลยคือ $x \equiv 4, 13, 22 \pmod{3^3}$ และสมการ $x^2 + x + 7 \equiv 0 \pmod{7} $ มีผลเฉลยคือ $x \equiv 0, 6\pmod{7}$ แล้วสุดท้ายก็สรุปว่า สมการตัวอย่างแรกสุดนี้มี 6 คำตอบ
อยากทราบอีกครับว่า สรุปมาจากไหนว่ามี 6 คำตอบ มาจาก Chinese Remainder Theorem รึเปล่าครับ แล้วถ้ามันมาจริง ๆ มันมาได้อย่างไรครับ งงจากตรงนี้มานานพอสมควรแล้วครับ

แล้วจะหาหนังสือหรือเว็บอะไรจากไหนที่แก้สมการพวก Quadratic Congruence Equation แบบนี้ละเอียด ๆ อะครับ ? (หรือพวกคอนกรูเอนซ์แบบที่ละเอียดๆ เพราะว่าหาจากหนังสือทฤษฎีจำนวนของที่เป็นภาษาไทยนี่ก็ดูแล้วไม่ค่อยชัด ส่วน text ที่ยืมจากห้องสมุด ก็ยังงงๆ อยู่ครับ)


ขอบคุณมากครับ

[Mathophile]

ข้อความเดิมเขียนโดยคุณ 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 คำตอบนั่นเองครับ

[MoDErN_SnC]

เกี่ยวกับสมการคอนกรูเอนซ์อะครับ...

มันมีทฤษฎีบทลากรองจ์บอกไว้ว่า
ถ้า p เป็นจำนวนเฉพาะ สมภาค $f(x)\equiv 0 \left(mod p\,\right) $ ระดับขั้น $k$ มีรากได้อย่างมาก $k$ ราก

ถ้าสมมติว่าเราพิจารณาสมภาค $f(x)\equiv 0 \left(mod p^k\,\right) $ ระดับขั้น $k$ จะยังคงมีรากได้ $k$ รากอยู่หรือไม่ครับ ถ้าไม่ใช่แล้วมีทฤษฎีอะไรที่มาช่วยพิจารณาครับ