เครื่องคำนวณ ค.ร.น. และ ห.ร.ม.

เกี่ยวกับเครื่องคำนวณนี้

ตัวหารร่วมมาก (GCD) ของจำนวนเต็มสองจำนวนคือจำนวนที่มากที่สุดที่หารทั้งสองลงตัว โดยทั่วไปหาได้ด้วยขั้นตอนวิธีของยูคลิด (การหารซ้ำพร้อมเศษ ซึ่งเป็นหนึ่งในขั้นตอนวิธีที่เก่าแก่ที่สุดในคณิตศาสตร์ มีที่มาจาก Elements ของยูคลิด) ส่วนตัวคูณร่วมน้อย (LCM) คือจำนวนที่น้อยที่สุดที่จำนวนเต็มทั้งสองหารลงตัว คำนวณจาก GCD ด้วย LCM(a,b) = (a×b) / GCD(a,b)

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