 |
ความคิดเห็นที่ 17 |
วิธีทำข้อ 3 ที่ผมทำนะครับ
จากโจทย์จะได้ว่า
x = 1(mod2) ความหมายคือ มีลูกบอล x ลูก หารด้วย 2 แล้วเหลือเศษ 1
x = 2(mod3)
x = 3(mod5)
x = 2(mod7)
x = 5(mod11)
x = 11(mod13)
สังเกตตัวเลขที่อยู่หลังคำว่า mod นั้นจะเป็น coprime (จำนวนเฉพาะสัมพัทธ์)
คือ 2,3,5,7,11,13
จาก Extended Euclidean algorithm (อะไรก็ไม่รู้เจอมาจาก link ใน wiki)
เนื้อหาคร่าวๆก็คือ
ถ้า m กับ n เป็นจำนวนเฉพาะสัมพัทธ์แล้ว m กับ n จะจัดอยู่ในรูป
am + bn = 1 ได้ โดยที่ a,b เป็นจำนวนเต็ม
ดังนั้นผมเลยมาจับคู่ coprime ได้ดังนี้
2 คู่กับ 3*5*7*11*13 =15015
3 คู่กับ 2*5*7*11*13 = 10010
5 คู่กับ 2*3*7*11*13 = 6006
7 คู่กับ 2*3*5*11*13 = 4290
11 คู่กับ 2*3*5*7*11 = 2730
13 คู่กับ 2*3*5*7*11 = 2310
จะได้ coprime (m,n)=(2,15015),(3,10010),(5,6006),(7,4290),(11,2730),(13,2310)
เอามา (m,n) แต่ละอันมาจัดในรูป am + bn = 1 ได้ดังนี้
(7508*2) + (-1*15015) = 1
(3337*3) + (-1 *10010) =1
(-1201*5) + (1*6006) =1
(613*7) + (-1*4290) =1
(1241*11) + (-5*2730) =1
(-533*13) + (3*2310) =1
แล้วให้เราเอาตัวเลขในวงเล็บข้างหลังทั้งหมดไปคูณกับตัวเลขที่อยู่ข้างหน้าคำว่า mod แล้วเอามาบวกกัน
จะได้ว่า
(-1*15015*1)+(-1 *10010*2)+(1*6006*3)+(-1*4290*2)+
(-5*2730*5)+(3*2310*11) = -17617
และเอา 2*3*5*7*11*13 = 30030
จะได้สมการค่า x=30030*k -17617 (โดยที่ k เป็นจำนวนเต็มที่มีค่ามากกว่าหรือเท่ากับ 1)
โจทย์ต้องการค่า x น้อยสุด จึงแทน k=1 ลงไป จะได้ค่า x=30030-17617=12413
ส่วนที่มาว่าทำไมถึงทำแบบนี้ ต้องรอท่านผู้รู้มาอธิบายครับ
ส่วนที่ผมทำได้ก็เพราะอ่านเอาจาก wiki นั่นแหล่ะครับ
ปล. อยากให้มีคนเขียนเกี่ยวกับเรื่อง Chinese remainder theorem ใน wiki ภาคภาษาไทยจัง
(แก้ไขจากเดิมที่มีเลข 9 กลายเป็นไม่มี เนื่องจากพิมพ์มันมือเกินไปเลยพิมพ์เลขคี่ ทั้งๆที่ๆต้องการพิมพ์คือจำนวนเฉพาะ)
แก้ไขเมื่อ 26 ก.ค. 52 20:49:10
| จากคุณ |
:
jesus_god  
|
| เขียนเมื่อ |
:
26 ก.ค. 52 19:22:11
|
|
|
|
|
