ความเห็นเพิ่มเติมที่ 46 28 เม.ย. 2550 (19:12) ข้อนี้ใช้ทฤษฎีเศษเหลือของจีนนะครับ
ให้ m1,m2,...,mn เป็นจำนวนเต็็มบวกซึ่ง ห.ร.ม ของ mi,mj = 1 เมื่อ i ไม่เท่ากับ j
และ A1,A2,...,An เป็นจำนวนเต็มและให้ m = m1*m2*...*mn และ Mi = m/mi สำหรับแต่ละ i
ให้ Yi เป็นจำนวนเต็มที่เป็นผลเฉลยของ Mi*y = 1 mod mi
จะได้ว่า ระบบคอนกรูเอนซ์เชิงเส้น
x = A1 mod m1
x = A2 mod m2 จนถึง
x = An mod mn
มีผลเฉลยร่วมกันเพียงตัวเดียวคือ x = M1*A1*Y1 + M2*A2*Y2 + ... + Mn*An*Yn ในมอดุโล M
(อ้างอิงจากหนังสือ สอวน. คณิตศาสตร์พื้นฐานสำหรับคอมพิวเตอร์ หน้า 86)
เพราะฉะนั้น ข้อนี้ทำได้โดย
x = 1 mod 3
x = 1 mod 5
x = 0 mod 7
A1 = 1 , A2 = 1 , A3 = 1 , m1 = 3 , m2 = 5 , m3 = 7
ห.ร.ม ของ 3,5 และ 3,7 และ 5,7 = 1
จะได้ว่าระบบคอนกรูเอนซ์เชิงเส้นมีผลเฉลยเดียวใน m = 3*5*7 = 105
ให้ M1 = m/m1 = 105/3 = 35
และ M2 = m/m2 = 105/5 = 21
และ M3 = m/m3 = 105/7 = 15
ต้องการหา Y1,Y2,Y3 ที่สอดคล้องกับคอนกรูเอนซ์
35*Y1 = 1 mod 3
21*Y2 = 1 mod 5
15*Y3 = 1 mod 7
จะได้ว่า Y1 = 2 , Y2 = 1 , Y3=1
เพราะฉะันั้้น x = M1*A1*Y1 + M2*A2*Y2 + M3*A3*Y3
x = 35*1*2 + 21*1*1 + 15*0*1
x = 70 + 21 = 91
Anonymous (IP:58.9.45.133)