เลขคณิตโมดูลาร์ — คณิตนาฬิกา, mod และความสมมูล

เลขคณิตโมดูลาร์คือการทำงานกับเศษที่ได้จากการหารด้วยจำนวนเต็มบวกคงที่ตัวหนึ่ง ซึ่งเรียกว่า มอดุลัส ถ้าจำนวนสองจำนวนให้เศษเท่ากัน ทั้งสองจะทำหน้าที่เหมือนกันในระบบโมดูลาร์นั้น จึงมักถูกเรียกว่า คณิตนาฬิกา

บนหน้าปัดนาฬิกา $12$ ชั่วโมง เวลา $13$ นาฬิกาจะไปตกที่ $1$ นาฬิกา และ $29$ ชั่วโมงก็ไปอยู่ตำแหน่งเดียวกับ $5$ ชั่วโมง วงจรที่วนซ้ำนี้คือภาพจำที่ช่วยให้เข้าใจเลขคณิตโมดูลาร์

mod หมายถึงอะไรในเลขคณิตโมดูลาร์

สำหรับจำนวนเต็ม $a$ และจำนวนเต็มบวก $n$ นิพจน์ $a \bmod n$ หมายถึงเศษเมื่อหาร $a$ ด้วย $n$

ตัวอย่าง:

$$29 \bmod 12 = 5$$

เพราะว่า

$$29 = 12 \cdot 2 + 5$$

มอดุลัสคือ $12$ ดังนั้นการบวกหรือลบ $12$ จะไม่เปลี่ยนตำแหน่งที่ตกในรอบการวนซ้ำ

ความสมมูลโมดูโล $n$ หมายถึงอะไร

ความสมมูลเป็นวิธีเขียนอย่างเป็นทางการว่าจำนวนเต็มสองจำนวนมีพฤติกรรมเหมือนกันภายใต้โมดูโล $n$

$$a \equiv b \pmod n$$

หมายความว่า $a$ และ $b$ ให้เศษเท่ากันเมื่อหารด้วย $n$ อีกวิธีหนึ่งที่ใช้ตรวจสอบได้เทียบเท่ากันคือ

$$n \mid (a-b)$$

ซึ่งหมายถึง "$n$ หาร $a-b$ ลงตัว"

ดังนั้น

$$29 \equiv 5 \pmod{12}$$

เพราะ $29 - 5 = 24$ และ $12$ หาร $24$ ลงตัว

ความแตกต่างนี้สำคัญ:

• $29 \bmod 12 = 5$ เป็นข้อความเกี่ยวกับเศษ
• $29 \equiv 5 \pmod{12}$ เป็นข้อความเกี่ยวกับความสมมูล

ทั้งสองเกี่ยวข้องกัน แต่ใช้แทนกันไม่ได้

ตัวอย่างแบบทำทีละขั้น: หลังจาก $29$ ชั่วโมงนับจาก $8$ นาฬิกา

สมมติว่าตอนนี้เป็นเวลา $8$ นาฬิกา และคุณต้องการรู้ว่าอีก $29$ ชั่วโมงต่อมาจะเป็นเวลาเท่าไรบนหน้าปัด $12$ ชั่วโมง

เริ่มจากลด $29$ ภายใต้โมดูโล $12$ ก่อน:

$$29 \bmod 12 = 5$$

ดังนั้นการบวก $29$ ชั่วโมงให้ผลเหมือนกับการบวก $5$ ชั่วโมง:

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

จากนั้น

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

ดังนั้นนาฬิกาจะแสดงเวลา $1$ นาฬิกา

จุดสำคัญคือขั้นตอนการลดค่า ในโมดูโล $12$ การแทน $29$ ด้วย $5$ ทำให้คำตอบยังเหมือนเดิม แต่คำนวณได้ง่ายขึ้น

ทำไมการลดค่าก่อนจึงทำให้โจทย์ง่ายขึ้น

จำนวนที่มีค่ามากมักจัดการได้ง่ายขึ้น ถ้าคุณแทนมันด้วยจำนวนที่เล็กกว่าแต่สมมูลกัน

ตัวอย่างเช่น ในโมดูโล $7$

$$100 \equiv 2 \pmod 7$$

เพราะ $100 - 2 = 98$ หารด้วย $7$ ลงตัว ถ้าโจทย์สนใจเฉพาะค่าภายใต้โมดูโล $7$ คุณก็สามารถใช้ $2$ แทน $100$ ได้

ข้อผิดพลาดที่พบบ่อย

สับสนระหว่างความเท่ากันกับความสมมูล

$29 \equiv 5 \pmod{12}$ ไม่ได้แปลว่า $29 = 5$ แต่มันหมายความว่าทั้งสองอยู่ในกลุ่มเศษเดียวกันภายใต้โมดูโล $12$

ลืมว่ามอดุลัสมีผลต่อคำตอบ

$17 \equiv 5 \pmod{12}$ เป็นจริง แต่ $17 \equiv 5 \pmod{10}$ เป็นเท็จ ความสมมูลต้องอ้างอิงกับมอดุลัสที่กำหนดเสมอ

มอง mod เหมือนการหารแบบปกติ

$29 \bmod 12$ คือเศษ $5$ ไม่ใช่ผลหาร $2$ และไม่ใช่เศษส่วน $29/12$

คิดว่า % ในซอฟต์แวร์ให้ผลตรงกับนิยามทางคณิตศาสตร์เสมอ

สำหรับจำนวนบวก เครื่องหมาย % ในภาษาโปรแกรมมักตรงกับแนวคิดเรื่องเศษที่นักเรียนเรียนกันก่อน แต่เมื่อเป็นจำนวนลบ ข้อตกลงอาจต่างกันได้ ดังนั้นผลลัพธ์อาจไม่ตรงกับเศษไม่ลบน้อยที่สุดที่ใช้กันในวิชาคณิตศาสตร์หลายหลักสูตร

เลขคณิตโมดูลาร์ถูกใช้ที่ไหน

คุณจะพบเลขคณิตโมดูลาร์ทุกครั้งที่ค่าต่าง ๆ วนซ้ำเป็นรอบ เช่น นาฬิกา วันในสัปดาห์ ระบบเลขตรวจสอบ แฮช และอีกหลายส่วนของทฤษฎีจำนวน

มันยังปรากฏในวิทยาการเข้ารหัสด้วย แต่แนวคิดพื้นฐานยังเหมือนเดิม คือจัดกลุ่มจำนวนตามค่าเศษ และถือว่าจำนวนที่สมมูลกันใช้แทนกันได้ภายในระบบนั้น

ลองทำโจทย์คล้ายกัน

วันอะไรจะเป็นวันที่ $100$ หลังจากวันจันทร์ เนื่องจากวันในสัปดาห์วนซ้ำแบบโมดูโล $7$ ให้เริ่มจากลด $100$ ภายใต้โมดูโล $7$ ก่อนแล้วค่อยตอบ

ถ้าคุณอยากลองอีกกรณีเพื่อเปรียบเทียบ ลองสร้างโจทย์แบบของคุณเองใน GPAI Solver แล้วดูว่าการลดค่าก่อนช่วยให้ทำงานสั้นลงหรือไม่