|
สมัครสมาชิก | คู่มือการใช้ | รายชื่อสมาชิก | ปฏิทิน | ข้อความวันนี้ | ค้นหา |
|
เครื่องมือของหัวข้อ | ค้นหาในหัวข้อนี้ |
#1
|
||||
|
||||
อยากทราบวิธีคิดแบบ congruence ของโจทย์ข้อนี้
เมื่อ p หารด้วย 5,8,13 เหลือเศษ 3,5,11 ตามลำดับ จงหาค่า p ที่มากที่สุดโดยที่ p < 1000
ตอนนี้ผมได้3สมการคือ P=3mod5 P=5mod8 P=11mod13 จากคุณMichael Owen 2 เค้าบอกว่าสุดท้ายจะได้ P=520k-67 ขอเชิญผู้รู้ช่วยแนะนำให้ความกระจ่างกับผมหน่อยครับ ผมยังไม่ค่อยเข้าใจนิยามของcongruenceครับ ช่วยอธิบายอย่างละเอียดด้วยครับ ผมเพิ่งขึ้นป.6เองครับ
__________________
กำลังฝึกฝนกำลังภายในอยู่กับเอี้ยก้วยครับ love มังกรหยกกกก |
#2
|
||||
|
||||
อ้างอิง:
__________________
PaTa PatA pAtA Pon! |
#3
|
||||
|
||||
นิยามของคอนกรูเอนซ์ได้มาจากการหารมีเศษ กล่าวคือเมื่อ $a\equiv{b}\pmod{c}$ ก็ต่อเมื่อ $c|(a-b)$ พูดง่ายๆคือ $a$ หารด้วย $c$ แล้วได้เศษ $b$ นั่นเอง ซึ่งจะขอละคุณสมบัติ(ที่หาอ่านเองได้ง่ายๆ)นะครับ
สำหรับโจทย์ที่ถามมาเป็นคำถามคำนวณมาตรฐานเรื่องทฤษฎีบทเศษเหลือจีน (Chinese remainder theorem) ซึ่งอาจทำได้ดังนี้: จากระบบสมการคอนกรูเอนซ์ $$x\equiv3\pmod5,\qquad{}x\equiv5\pmod8,\qquad{}x\equiv11\pmod{13}$$ เราสามารถคูณแต่ละคอนกรูเอนซ์ด้วยจำนวนที่เหมาะสม เพื่อทำให้ตัวหารแต่ละตัวเท่ากัน(=ค.ร.น.ของตัวหาร) นั่นคือ $$104x\equiv312\pmod{520},\quad{}65x\equiv325\pmod{520},\quad{}40x\equiv440\pmod{520}$$ รวมทั้งสามคอนกรูเอนซ์จะได้ $209x\equiv1077\equiv37\pmod{520}$ ดังนั้นเราจะหาจำนวนที่เหมะสมมาคูณเพื่อทำให้สัมประสิทธิ์ของ x เป็น 1 โดย Euclidean Algorithm (ฝากกลับไปค้นรายละเอียดและตัวอย่างเพิ่มเติมในหนังสือเองนะครับ) จะได้ว่า $\begin{eqnarray} 520&=&2\cdot209+102\\ 209&=&2\cdot102+5\\ 102&=&20\cdot5+2\\ 5&=&2\cdot2+1\\ 1&=&5-2\cdot2\\ &=&5-2(102-20\cdot5)=41\cdot5-2\cdot102\\ &=&41\cdot(209-2\cdot102)-2\cdot102=41\cdot209-84\cdot102\\ &=&41\cdot209-2(520-2\cdot209)=209\cdot209-84\cdot520\\ \end{eqnarray}$ (ตรงนี้หมายความว่า หากหารผลคูณ $209\cdot209$ ด้วย 520 จะได้เศษเป็น 1 นั่นคือ เหลือ x ทางซ้ายตัวเดียวตามที่ต้องการ) ดังนั้น $$x\equiv209\cdot37\equiv453\equiv(453-520)\equiv-67\pmod{520}$$ ดังนั้น จำนวนเต็มที่สอดคล้องระบบสมการคอนกรูเอนซ์นี้จะอยู่ในรูป 520k+453 หรือ 520k-67 เมื่อ k เป็นจำนวนเต็ม เราจึงสรุปได้ว่า 520+453=2(520)-67=973 เป็นจำนวนเต็มบวกสามหลักที่มากที่สุดที่สอดคล้องเงื่อนไขโจทย์ หากอ่านวิธีทำหลังจากหนังสือเพิ่มเติมแล้วไม่เข้าใจก็ลองมาถามดูนะครับ แต่เท่าๆที่ทำให้ดูคงพอจะเข้าใจนะครับ ว่าเวลาใครถามอะไรในเวบบอร์ดที่สามารถค้นจากหนังสือได้ไม่ยาก หรือมีการคำนวณพื้นฐานมากๆ จึงไม่ค่อยมีคนตอบแบบละเอียดยิบ (โดยเฉพาะโจทย์แนวนี้)
__________________
คนไทยร่วมใจอย่าใช้ภาษาวิบัติ ฝึกพิมพ์สัญลักษณ์สักนิด ชีวิต(คนตอบและคนถาม)จะง่ายขึ้นเยอะ (จริงๆนะ) Stay Hungry. Stay Foolish. 06 พฤษภาคม 2006 10:51 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ nongtum |
#4
|
||||
|
||||
ขอบคุณมากครับ ผมเข้าใจแล้วครับ แต่ข้องใจตรงวิธี Euclidean Algorithm เราไม่ต้องใช้วิธีนี้ได้ไหมครับ ใช้วิธีคาดคะเนว่า209คูณกับอะไรแล้วหารด้วย520เหลือเศษ1 จากนั้นเราคาดว่าได้209*209แต่209ไม่ต้องคูณกับตัวหาร520หรือครับ
สรุปแล้ววิธีนี้ยากตรงวิธี Euclidean Algorithm ต้องกระจายให้เหลือเศษ1 คือ Xผมยังต้องไปศึกษาวิธี ของcongruenceให้กระจ่างครับ ขอบคุณมากครับสำหรับคำอธิบายครับ
__________________
กำลังฝึกฝนกำลังภายในอยู่กับเอี้ยก้วยครับ love มังกรหยกกกก |
#5
|
||||
|
||||
จะทำงั้นก็ได้ครับหากเลขมันง่ายหรือว่าคิดไหว แต่หากเลขเยอะๆใช้ Euclidean Algorithm จะสะดวกกว่าเยอะครับ
__________________
คนไทยร่วมใจอย่าใช้ภาษาวิบัติ ฝึกพิมพ์สัญลักษณ์สักนิด ชีวิต(คนตอบและคนถาม)จะง่ายขึ้นเยอะ (จริงๆนะ) Stay Hungry. Stay Foolish. |
หัวข้อคล้ายคลึงกัน | ||||
หัวข้อ | ผู้ตั้งหัวข้อ | ห้อง | คำตอบ | ข้อความล่าสุด |
ถามโจทย์congruence | CmKaN | ปัญหาคณิตศาสตร์ ม.ปลาย | 3 | 07 มกราคม 2007 15:42 |
|
|