ความรู้เบื้องต้นเรื่อง mod

[kongp]

วิชาทฤษฏีจำนวน ไม่ใช่แค่หาเศษนะครับ แต่เป็นการวิเคราะห์ระบบตัวเลข เพื่อให้คำนวนได้แม่นยำและรวดเร็ว ดังนั้น ผลหารก็สำคัญไม่น้อย น่าจะออกเป็นข้อสอบบ้าง แต่ก้นั้นถามหาเศษเหลือก็คงเพราะเป็นปัญหาคณิตศาสตร์มากกว่านั่นเอง จริงไหมครับ

[Gu_ChoewIndY]

ข้อความเดิมเขียนโดยคุณ banker

นั่ง Time Machine ไปยุคประถม

ถ้าถามว่า 5 หารด้วย 2 เหลือเศษเท่าไร เด็กๆก็ตอบได้ว่า เหลือเศษ 1

ถามว่า 289 หารด้วย 13 เหลือเศษเท่าไร

เด็กก็จะตั้งหารยาว ได้ผลลัพธ์เป็น 22 เหลือเศษ 3

เขียนในรูปเศษส่วน จะได้ $\frac{289}{13} = \frac{22(13) +3}{13} = \frac{22(13) }{13} + \frac{3}{13}$

จะเห็นว่า $\frac{22(13) }{13}$ ตัวเศษ มี 13 เป็นพหุคูณ หรือตัวร่วม ทำให้ หารด้วย 13 ลงตัว และมี $\frac{3}{13}$ เศษคือ $3$


แต่โจทย์ไม่ง่ายๆแบบข้างต้น มักเป็นการหารเลขยกกำลัง เช่น

$2^{10}$ หารด้วย $5$ เหลือเศษ เท่าไร

จงหาเศษเหลือจากการหาร $3^{100}$ ด้วย $7$

เศษเหลือจาการหาร $17^{1000}$ ด้วย $13$ เป็นเท่าไร

แบบนี้ถ้าทำแบบตั้งหารยาว คงยุ่งยากและยาวมากๆ

เราจะหาแนวทางในการหาเศษเหลือของตัวเลข $x^n$ ที่หารด้วย $p$

ค่อยๆทำความเข้าใจตัวอย่างต่อไปนี้นะครับ

[banker]

งงเหมือนกัน ว่างงอะไร

[Built]

ยากจังคะ กำลังเริ่มมองหา time machine ใช้อยู่ เพราะลูกชายขึ้นป.4 แล้ว

[เจมี่]

ตัวอย่างที่ 1

เศษเหลือที่ได้จากการหาร 2^100 ด้วย 5 เท่ากับเท่าใด

ไม่ได้ยากอะไรเลย
2^100 ≡ ? (mod 5)

2 ≡ 2 (mod 5)

2^2 ≡ 4 (mod 5)

2^3 ≡ 3 (mod 5)

〖〖(2〗^2)〗^50 ≡ 4^50(mod 5)

4^50 ≡ ? (mod 5)

4 ≡ 4 (mod 5)

4^2 ≡ 1 (mod 5) ( 16 หาร 5 เหลือเศษ 1)

〖〖(4〗^2)〗^25 ≡ 1^25(mod 5)

ตอบ เหลือ เศษ 1