โปรแกรมคำนวณ mod (Modulo) หาผลหารและเศษเหลือ
a mod b คือเศษ r ที่เหลือจากการหาร a ด้วย b โดย a = b × q + r และ 0 ≤ r < |b| (เมื่อ b เป็นบวก) เช่น 17 mod 5 = 2 เพราะ 17 = 5 × 3 + 2 ส่วนจำนวนลบ ภาษา C/JavaScript ให้ −17 % 5 = −2 แต่คณิตศาสตร์และ Python ให้ −17 mod 5 = 3
ประวัติการคำนวณ (เก็บในเครื่องนี้)
วิธีใช้คำนวณ mod (หารเอาเศษ)
- เลือกโหมด: หาเศษ a mod b, ยกกำลังแบบมอดุโล aᵇ mod m หรือหาตัวผกผัน a⁻¹ mod m
- กรอกจำนวนเต็ม (ยาวกี่หลักก็ได้) หรือพิมพ์เป็นสูตร เช่น 2^64 ใส่เครื่องหมายลบได้
- ดูผลหาร เศษ ตารางเปรียบเทียบแบบ C/JavaScript กับ Python และวิธีทำทีละขั้น
นิยามของ mod และการหารแบบมีเศษ
a = b × q + r → a mod b = r
q คือผลหาร (quotient) และ r คือเศษ (remainder) ความต่างของแต่ละภาษาโปรแกรมอยู่ที่วิธีปัดผลหาร q เมื่อมีจำนวนลบ
| แบบ | ผลหาร q | เครื่องหมายของเศษ | ใช้ใน |
|---|---|---|---|
| ตัดทศนิยม (truncated) | ปัดเข้าหาศูนย์ | ตามตัวตั้ง a | C, C++, Java, JavaScript (%), Go, Rust |
| ปัดลง (floored) | ปัดลง ⌊a ÷ b⌋ | ตามตัวหาร b | Python (%), Excel MOD(), Ruby, คณิตศาสตร์ |
| ยุคลิด (Euclidean) | ให้ 0 ≤ r < |b| | ไม่ติดลบเสมอ | ทฤษฎีจำนวน |
เมื่อ a และ b เป็นบวกทั้งคู่ ทั้งสามแบบให้ผลเท่ากัน
ตัวอย่างการคำนวณ
โจทย์: −17 mod 5
- −17 ÷ 5 = −3.4
- แบบตัดทศนิยม: q = −3 → r = −17 − 5 × (−3) = −2 (ผลของ -17 % 5 ใน JavaScript)
- แบบปัดลง: q = ⌊−3.4⌋ = −4 → r = −17 − 5 × (−4) = 3 (ผลของ -17 % 5 ใน Python)
โจทย์ยกกำลัง: 4¹³ mod 497 เขียน 13 = 1101₂ แล้วยกกำลังสองซ้ำ: 4¹ ≡ 4, 4² ≡ 16, 4⁴ ≡ 256, 4⁸ ≡ 429 (mod 497) จากนั้นคูณเฉพาะบิตที่เป็น 1: 4 × 256 × 429 ≡ 445 (mod 497)
mod ใช้ทำอะไรในชีวิตจริง
- นาฬิกาและปฏิทิน อีก 100 ชั่วโมงจาก 9 โมง คือ (9 + 100) mod 24 = 13 นาฬิกา และอีก 45 วันจากวันจันทร์ คือ 45 mod 7 = 3 วันถัดไป = วันพฤหัสบดี
- เลขคู่/เลขคี่ n mod 2 = 0 แปลว่าเป็นเลขคู่
- ตรวจเลขบัตรและบาร์โค้ด หลักตรวจสอบ (check digit) ของเลขประจำตัวประชาชน 13 หลักและบาร์โค้ด EAN-13 คำนวณด้วย mod 11 และ mod 10
- การเข้ารหัส RSA และลายเซ็นดิจิทัลใช้ aᵇ mod m กับตัวผกผันมอดุโลเป็นแกนหลัก
ยกกำลังมอดุโลด้วยวิธียกกำลังสองแล้วคูณ
การคำนวณ aᵇ ตรง ๆ แล้วค่อยหาเศษจะได้ตัวเลขยาวมหาศาล วิธี square-and-multiply เขียนเลขชี้กำลัง b เป็นเลขฐานสอง ยกกำลังสองฐานซ้ำ ๆ และหาเศษทุกครั้ง แล้วคูณเฉพาะตำแหน่งที่บิตเป็น 1 จึงใช้การคูณเพียงประมาณ 2 × (จำนวนบิตของ b) ครั้ง เช่น b ขนาด 2048 บิตใช้การคูณไม่ถึง 4,100 ครั้ง
ถ้า m เป็นจำนวนเฉพาะและ a หารด้วย m ไม่ลงตัว ทฤษฎีบทเล็กของแฟร์มาต์ บอกว่า am−1 ≡ 1 (mod m) จึงลดเลขชี้กำลังเหลือ b mod (m − 1) ได้
คำถามที่พบบ่อย
mod คืออะไร
mod (modulo) คือการหาเศษที่เหลือจากการหาร เช่น 17 mod 5 = 2 เพราะ 17 หารด้วย 5 ได้ 3 เหลือเศษ 2
ทำไม −7 mod 3 ใน Excel กับ JavaScript ได้ไม่เท่ากัน
Excel ฟังก์ชัน MOD และ Python ปัดผลหารลง เศษจึงมีเครื่องหมายตามตัวหาร ได้ 2 ส่วน JavaScript, C และ Java ตัดทศนิยมของผลหารทิ้ง เศษจึงมีเครื่องหมายตามตัวตั้ง ได้ −1 ทั้งสองแบบถูกตามนิยามของตัวเอง
a mod 0 ได้เท่าไร
หาค่าไม่ได้ เพราะการหารด้วยศูนย์ไม่นิยาม โปรแกรมจะแจ้งเตือน
ตัวผกผันมอดุโลคืออะไร
คือจำนวน x ที่ทำให้ a × x ≡ 1 (mod m) เช่น 3 × 4 = 12 ≡ 1 (mod 11) จึงได้ 3⁻¹ ≡ 4 (mod 11) มีคำตอบเมื่อ ห.ร.ม.(a, m) = 1 เท่านั้น และหาได้ด้วยขั้นตอนวิธีของยุคลิดแบบขยาย
คำนวณเลขใหญ่มาก ๆ ได้ไหม
ได้ โปรแกรมใช้ BigInt ของเบราว์เซอร์ จึงคำนวณจำนวนเต็มหลายร้อยหลักได้แม่นยำทุกหลัก และพิมพ์เป็นสูตร เช่น 2^521-1 ได้