เครื่องคิดเลข GCD/LCM

GCD คือจำนวนเต็มบวกที่มากที่สุดที่หารทุกตัวเลขที่กำหนดได้ลงตัวโดยไม่เหลือเศษ เรียกอีกอย่างว่า HCF (Highest Common Factor) ตัวอย่างเช่น GCD(12, 18) = 6 เพราะ 6 คือตัวเลขที่มากที่สุดที่หารทั้ง 12 และ 18 ได้อย่างแม่นยำ

LCM คือจำนวนเต็มบวกที่น้อยที่สุดที่หารด้วยทุกตัวเลขที่กำหนดได้ลงตัว ตัวอย่างเช่น LCM(4, 6) = 12 เพราะ 12 คือตัวเลขที่น้อยที่สุดที่ทั้ง 4 และ 6 หารได้ลงตัว

อัลกอริทึมยูคลิดหา GCD โดยการใช้ขั้นตอนวิธีการหารซ้ำๆ: หารตัวเลขที่มากกว่าด้วยตัวเลขที่น้อยกว่า แทนที่ตัวเลขที่มากกว่าด้วยตัวเลขที่น้อยกว่าและแทนที่ตัวเลขที่น้อยกว่าด้วยเศษ ทำซ้ำจนกว่าเศษจะเป็นศูนย์ เศษที่ไม่ใช่ศูนย์สุดท้ายคือ GCD ตัวอย่างเช่น เพื่อหา GCD(48, 18): 48÷18=2 เศษ 12 จากนั้น 18÷12=1 เศษ 6 จากนั้น 12÷6=2 เศษ 0 ดังนั้น GCD=6

GCD และ LCM สัมพันธ์กันด้วยสูตร: LCM(a,b) = |a×b| / GCD(a,b) หมายความว่าถ้าคุณรู้ GCD ของสองตัวเลข คุณสามารถคำนวณ LCM ของพวกมันได้ง่าย และในทางกลับกัน ความสัมพันธ์นี้ใช้ได้กับตัวเลขบวกสองจำนวนใดๆ

ได้ คุณสามารถคำนวณ GCD และ LCM สำหรับสามตัวเลขหรือมากกว่า สำหรับ GCD ใช้คุณสมบัติ: GCD(a,b,c) = GCD(GCD(a,b),c) สำหรับ LCM ใช้: LCM(a,b,c) = LCM(LCM(a,b),c) เพียงป้อนตัวเลขหลายตัวคั่นด้วยเครื่องหมายจุลภาค

GCD มีการใช้งานมากมาย: การทำให้เศษส่วนง่ายขึ้น (การหารตัวเศษและตัวส่วนด้วย GCD ของพวกมัน) การแก้สมการ Diophantine การหาอินเวอร์สโมดูลาร์ในการเข้ารหัส การตรวจสอบว่าสองตัวเลขเป็นจำนวนเฉพาะสัมพัทธ์หรือไม่ (GCD=1) และในอัลกอริทึมยูคลิดซึ่งเป็นพื้นฐานในทฤษฎีจำนวน

LCM ถูกใช้ในหลายสถานการณ์ในชีวิตจริง: การหาเวลาที่เหตุการณ์จะตรงกัน (เช่น ตารางรถเมล์) การบวกหรือลบเศษส่วนที่มีตัวส่วนต่างกัน การกำหนดเวลางานที่เกิดขึ้นซ้ำๆ การแก้ปัญหาที่เกี่ยวข้องกับปรากฏการณ์เป็นคาบ และในดนตรีเพื่อหารูปแบบจังหวะ

ถ้า GCD(a,b) = 1 ตัวเลขเหล่านั้นเรียกว่าเป็นจำนวนเฉพาะสัมพัทธ์หรือจำนวนเฉพาะเทียบเท่า หมายความว่าพวกมันไม่มีตัวประกอบร่วมอื่นนอกจาก 1 ตัวอย่างเช่น 8 และ 15 เป็นจำนวนเฉพาะสัมพัทธ์เพราะตัวหารร่วมเดียวของพวกมันคือ 1 จำนวนเฉพาะสัมพัทธ์มีความสำคัญในการเข้ารหัสและทฤษฎีจำนวน

เพื่อหา GCD โดยใช้การแยกตัวประกอบเฉพาะ: (1) หาตัวประกอบเฉพาะของแต่ละตัวเลข (2) ระบุตัวประกอบเฉพาะร่วม (3) สำหรับแต่ละตัวประกอบเฉพาะร่วม ให้ยกกำลังที่ต่ำที่สุด (4) คูณพวกมันเข้าด้วยกัน ตัวอย่างเช่น 36=2²×3² และ 48=2⁴×3¹ ดังนั้น GCD=2²×3¹=12

เพื่อหา LCM โดยใช้การแยกตัวประกอบเฉพาะ: (1) หาตัวประกอบเฉพาะของแต่ละตัวเลข (2) สำหรับแต่ละตัวประกอบเฉพาะที่ปรากฏในตัวเลขใด ๆ ให้ยกกำลังที่สูงที่สุด (3) คูณพวกมันเข้าด้วยกัน ตัวอย่างเช่น 12=2²×3¹ และ 18=2¹×3² ดังนั้น LCM=2²×3²=36

ได้ GCD และ LCM เป็นจำนวนเต็มบวกเสมอโดยไม่คำนึงถึงเครื่องหมายของตัวเลขที่ป้อนเข้า เครื่องคิดเลขใช้ค่าสัมบูรณ์ของตัวเลข ตัวอย่างเช่น GCD(-12, 18) = 6 และ LCM(-4, 6) = 12

อัลกอริทึมยูคลิดมีความซับซ้อนของเวลา O(log(min(a,b))) ทำให้มีประสิทธิภาพสูงแม้กระทั่งกับตัวเลขที่ใหญ่่มาก มันเป็นหนึ่งในอัลกอริทึมที่เก่าแก่และมีประสิทธิภาพมากที่สุดในคณิตศาสตร์ ย้อนกลับไปถึงกรีซโบราณประมาณ 300 ปีก่อนคริสตกาล

เพื่อทำให้เศษส่วนง่ายขึ้น ให้หารทั้งตัวเศษและตัวส่วนด้วย GCD ของพวกมัน ตัวอย่างเช่น เพื่อทำให้ 24/36 ง่ายขึ้น: GCD(24,36)=12 ดังนั้น 24÷12=2 และ 36÷12=3 ให้เศษส่วนที่ง่ายขึ้น 2/3 ซึ่งช่วยให้เศษส่วนอยู่ในรูปแบบที่ต่ำที่สุด

ได้ เครื่องคิดเลขนี้สามารถจัดการกับจำนวนเต็มขนาดใหญ่ได้อย่างมีประสิทธิภาพโดยใช้アルกอริทึมยูคลิด อย่างไรก็ตาม ตัวเลขที่ใหญ่ที่สุด (หลายร้อยหลัก) อาจถูกจำกัดด้วยความแม่นยำของตัวเลข JavaScript สำหรับวัตถุประสงค์ในทางปฏิบัติส่วนใหญ่ มันทำงานได้อย่างสมบูรณ์แบบสำหรับตัวเลขสูงสุด 15-16 หลัก