การหา ห.ร.ม. แบบยุคลิด

ที่มาภาพ : https://us-fbcloud.net/cal/data/gcd/title.jpg

ตัวหารร่วมมาก (ห.ร.ม.) ของจำนวนเต็มสองจำนวน คือจำนวนเต็มบวกที่มีค่ามากที่สุดที่หารจำนวนเต็มทั้งสองจำนวนนั้นลงตัว

ถ้าพิจารณาจากนิยามของ ห.ร.ม. จะพบว่าวิธีการหนึ่งที่สามารถใช้ในการหา ห.ร.ม. ได้ คือ การนำจำนวนเต็มบวกมาหารจำนวนเต็มสองจำนวน โดยเริ่มตั้งแต่การนำ 1, 2, 3.... ไปเรื่อย ๆ มาหาร จนถึงจำนวนที่น้อยกว่าในสองจำนวนที่ต้องการหา ห.ร.ม. นั้น และในระหว่างการคำนวณ จะต้องจดจำค่าที่มากที่สุดที่หารจำนวนทั้งสองลงตัว เมื่อดำเนินการเสร็จแล้ว จำนวนมากที่สุดที่จดจำไว้คือ ห.ร.ม. วิธีการนี้จะใช้งานได้สะดวกเมื่อจำนวนเต็มทั้งสองจำนวนมีค่าน้อย เช่น 21 กับ 14 ถ้าจำนวนเต็มทั้งสองมีค่ามาก เช่น 221 กับ 187  วิธีการข้างต้นจะใช้เวลานาน เพราะต้องทำการคำนวณทั้งหมด 187 ครั้ง นักเรียนจึงจะได้คำตอบว่า ห.ร.ม. คือ 17

ถ้านักเรียนใช้วิธีการเดียวกันนี้กับจำนวนเต็ม 61,950,337 และ 62,377,963  นักเรียนอาจต้องทำการหารจำนวนเต็มทั้งสองประมาณ 62 ล้านครั้ง แต่ถ้าใช้ขั้นตอนวิธีของยุคลิด (Buclidean algorithm) ในการหาคำตอบของปัญหานี้สามารถทำได้อย่างมีประสิทธิภาพ

การหา ห.ร.ม. แบบขั้นตอนวิธีของยุคลิด
1. เขียนจำนวนที่ต้องการหา ห.ร.ม. เรียงต่อกัน
2. ถ้าจำนวนที่น้อยกว่ามีค่าเป็นศูนย์ คำตอบคือจำนวนที่มีค่ามากกว่า และจบการทำงาน
3. ในบรรทัดถัดมา
     3.1 เขียนเศษที่ได้จากการหารจำนวนที่มากกว่าด้วยจำนวนที่น้อยกว่า
     3.2 คัดลอกจำนวนเต็มที่มีค่าน้อยกว่าลงในบรรทัดเดียวกัน
4. กลับไปทำกระบวนการรอบต่อไปในขั้นตอนที่ 2

ที่มาภาพ : https://i0.wp.com/www.bloggang.com/data/k/kruaun/picture/1245601119.jpg 

ยุคลิด (อังกฤษ: Euclid /ˈjuːklɪd/; กรีกโบราณ: Εὐκλείδης – Eukleídēs; fl. 300 BC) บางครั้งถูกเรียกว่า ยุคลิดแห่งอะเล็กซานเดรีย (อังกฤษ: Euclid of Alexandria, เพื่อแยกเขาออกจากยุคลิดแห่งเมการา) เป็นนักคณิตศาสตร์ชาวกรีกโบราณที่มีชีวิตอยู่ในช่วง 300 ปีก่อนคริสต์ศักราช ผลงานที่มีชื่อเสียงที่สุดของยุคลิดคือหนังสือเอเลเมนส์ (The Elements) ซึ่งเป็นหนังสือรวบรวมทฤษฎีบทในคณิตศาสตร์ (โดยเฉพาะอย่างยิ่งทางเรขาคณิต) และการพิสูจน์โดยวิธีแบบสัจพจน์ ซึ่งได้รับความนิยมอย่างยิ่งจนเป็นตำราเรียนคณิตศาสตร์เล่มสำคัญในอดีตจนถึงศตวรรษที่ 19 ในหนังสือดังกล่าวยุคลิดพิสูจน์ทฤษฎีบทเกี่ยวกับเรขาคณิตที่ในปัจจุบันเรียกว่า เรขาคณิตแบบยุคลิด จากสัจพจน์พื้นฐานเท่านั้น

ให้นักเรียนศึกษาเพิ่มเติม (หนังสือเรียน หน้า 10-12)