ห.ร.ม. และ ค.ร.น. คืออะไร?
ตัวหารร่วมมาก (GCD) และตัวคูณร่วมน้อย (LCM) เป็นหนึ่งในแนวคิดที่สำคัญที่สุดในทฤษฎีจำนวนพื้นฐาน มีการใช้งานตั้งแต่การย่อส่วนในการเรียนระดับมัธยมต้นไปจนถึงอัลกอริทึมการเข้ารหัสที่รักษาความปลอดภัยของอินเทอร์เน็ต
อัลกอริทึม Euroclid ที่ถูกอธิบายโดย Euroclid เมื่อประมาณ 300 ปีก่อนคริสตกาล เป็นหนึ่งในอัลกอริทึมที่เก่าแก่และมีประสิทธิภาพสูงสุดในคณิตศาสตร์ สามารถคำนวณ GCD ได้ภายใน O(log(min(a,b))) ขั้นตอน แม้ตัวเลขจะมีค่ามากก็จะหยุดทำงานอย่างรวดเร็ว อัลกอริทึมนี้ใช้สมการ: GCD(a, b) = GCD(b, a mod b) ซ้ำจนกว่าจะได้เศษเป็นศูนย์
เครื่องคิดเลขนี้แสดงขั้นตอนวิธี Euroclid แบบละเอียดสำหรับตัวเลขสองจำนวน และยังคำนวณ GCD และ LCM สำหรับกลุ่มตัวเลขหลายจำนวนโดยใช้: GCD(a, b, c) = GCD(GCD(a, b), c)
เมื่อไหร่ควรใช้เครื่องคำนวณนี้
- ในการลดทศนิยม.
- ในปัญหานัดหมายที่เกิดซ้ำ.
- ในการเข้ารหัสข้อมูล.
- ในการหาตัวคูณร่วมน้อย.
- ในปัญหาเรขาคณิต.
- ในวิทยาการคอมพิวเตอร์.
ขั้นตอน:
- ป้อนจำนวนบวกสองจำนวน a และ b
- ทำการหารแบบจำนวนเต็ม: a = q×b + r
- แทนที่ a ด้วย b และ b ด้วย r ทำซ้ำจนกว่า r = 0
- เศษที่ไม่ใช่ศูนย์ตัวสุดท้ายคือ GCD
- คำนวณ LCM = |a × b| / GCD โดยใช้สมการพื้นฐาน
- ใช้โหมดหลายจำนวนสำหรับตัวเลขสามจำนวนขึ้นไป
สูตร
ขั้นตอนวิธี Euroclid:
GCD(a, b) = GCD(b, a mod b) จนกว่า b = 0
LCM จาก GCD:
LCM(a, b) = |a × b| / GCD(a, b)
สำหรับหลายจำนวน:
GCD(a, b, c) = GCD(GCD(a, b), c)
LCM(a, b, c) = LCM(LCM(a, b), c)
กรณีใช้งาน
- ย่อส่วน: ย่อ a/b ด้วยการหารทั้งสองฝ่ายด้วย GCD(a, b)
- บวกส่วนที่มีตัวหารต่างกัน: หา LCM ของตัวหาร
- การจัดตารางเวลา: หาว่าเหตุการณ์ที่เกิดซ้ำสองเหตุการณ์จะตรงกันเมื่อใด
- การสร้างคีย์ RSA: ตรวจสอบว่าเลขชี้กำลัง e เป็นจำนวนเฉพาะสัมพัทธ์กับ φ(n)
- ปัญหาอัตราทดเฟืองในวิศวกรรมเครื่องกล
- การออกแบบลวดลายกระเบื้อง: หาหน่วยที่เล็กที่สุดที่ซ้ำตัวเอง
ประโยชน์หลัก
- ช่วยลดทศนิยม.
- ใช้ในการเข้ารหัส RSA.
- ช่วยแก้ปัญหานัดหมายที่เกิดซ้ำ.
- ใช้ในการหาตัวคูณร่วมน้อย.
- มีประโยชน์ในวิทยาการคอมพิวเตอร์.
- ช่วยเข้าใจคุณสมบัติของจำนวนเฉพาะ.
เคล็ดลับ
- ใช้อัลกอริทึมยุคลิดสำหรับจำนวนขนาดใหญ่.
- จำว่า GCD(a, b) = GCD(b, a mod b).
- ตรวจสอบด้วย GCD × LCM = a × b.
- GCD(0, a) = a สำหรับทุกจำนวนบวก a.
- หารตัวเลขและตัวหารด้วย GCD.
- สำหรับหลายจำนวน คำนวณ LCM ทีละคู่.
ข้อผิดพลาดที่พบบ่อย
- คิดว่า GCD(0, 0) = 0.
- สับสนระหว่าง GCD และ LCM.
- ลืมว่า GCD ใช้ค่าสัมบูรณ์.
- พยายามคำนวณ GCD โดยไม่มีอัลกอริทึมที่ชัดเจน.
- คิดว่า GCD ใหญ่กว่า LCM เสมอ.
- ลืมตรวจสอบ GCD × LCM = a × b.
คำศัพท์สำคัญ
- GCD: จำนวนเต็มที่มากที่สุดที่หารทั้งสองจำนวนลงตัวโดยไม่เหลือเศษ
- LCM: จำนวนเต็มบวกที่เล็กที่สุดที่ทั้งสองจำนวนหารลงตัว
- จำนวนเฉพาะสัมพัทธ์: สองจำนวนที่มี GCD = 1 ไม่มีปัจจัยร่วม
- ขั้นตอนวิธี Euroclid: อัลกอริทึมโบราณที่คำนวณ GCD โดยการหารซ้ำ
- การดำเนินการ modulo: a mod b คือเศษที่เหลือจากการหาร a ด้วย b
- การหารลงตัว: a หาร b ลงตัวถ้า b/a ไม่เหลือเศษ
แนวคิดที่เกี่ยวข้อง
- อัลกอริทึมยุคลิด: อัลกอริทึมที่มีประสิทธิภาพสำหรับคำนวณ GCD.
- การแยกตัวประกอบเฉพาะ: การแยกจำนวนออกเป็นตัวประกอบเฉพาะ.
- จำนวน FRIENDLY: จำนวนที่มี GCD = 1.
- ตัวหารร่วม: ตัวเลขที่หารทั้งสองลงตัว.
- ตัวคูณร่วม: ตัวเลขในตารางคูณของทั้งสอง.
ตัวอย่าง
หา GCD(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. GCD = 6. LCM = |48×18|/6 = 864/6 = 144. ตรวจสอบ: 144/48 = 3 ✓, 144/18 = 8 ✓.
การตีความผลลัพธ์
GCD คือตัวหารร่วมมาก LCM คือตัวคูณร่วมน้อย ถ้า GCD = 1 จำนวนสองตัวเป็นจำนวน FRIENDLY.