อยากทราบวิธีคิดแบบ congruence ของโจทย์ข้อนี้

[Pramote]

เมื่อ 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เองครับ

[M@gpie]

เมื่อ 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เองครับ

พี่ก็ไม่เป็น congruence เหมือนกันนะครับน้อง แต่โจทย์มีปัญหารึเปล่าเท่าที่ลองทำด้วยวิธีอื่นดู อาจจะเป็น เมื่อ p หารด้วย 5,8,13 เหลือเศษ 3,6,11 ตามลำดับ จงหาค่า p ที่มากที่สุดโดยที่ p < 1000 แบบนี้รึเปล่าครับ ?? รบกวนลองเช็คดู ถ้าถูกแล้วขออภัยด้วย

[nongtum]

นิยามของคอนกรูเอนซ์ได้มาจากการหารมีเศษ กล่าวคือเมื่อ $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 เป็นจำนวนเต็มบวกสามหลักที่มากที่สุดที่สอดคล้องเงื่อนไขโจทย์

หากอ่านวิธีทำหลังจากหนังสือเพิ่มเติมแล้วไม่เข้าใจก็ลองมาถามดูนะครับ แต่เท่าๆที่ทำให้ดูคงพอจะเข้าใจนะครับ ว่าเวลาใครถามอะไรในเวบบอร์ดที่สามารถค้นจากหนังสือได้ไม่ยาก หรือมีการคำนวณพื้นฐานมากๆ จึงไม่ค่อยมีคนตอบแบบละเอียดยิบ (โดยเฉพาะโจทย์แนวนี้)

[Pramote]

ขอบคุณมากครับ ผมเข้าใจแล้วครับ แต่ข้องใจตรงวิธี Euclidean Algorithm เราไม่ต้องใช้วิธีนี้ได้ไหมครับ ใช้วิธีคาดคะเนว่า209คูณกับอะไรแล้วหารด้วย520เหลือเศษ1 จากนั้นเราคาดว่าได้209*209แต่209ไม่ต้องคูณกับตัวหาร520หรือครับ
สรุปแล้ววิธีนี้ยากตรงวิธี Euclidean Algorithm ต้องกระจายให้เหลือเศษ1 คือ Xผมยังต้องไปศึกษาวิธี ของcongruenceให้กระจ่างครับ ขอบคุณมากครับสำหรับคำอธิบายครับ

[nongtum]

จะทำงั้นก็ได้ครับหากเลขมันง่ายหรือว่าคิดไหว แต่หากเลขเยอะๆใช้ Euclidean Algorithm จะสะดวกกว่าเยอะครับ