ยูคลิด (Euclid)

ตัวอย่าง อัลกอริทึมการหา ห.ร.ม.

ลักการหา ห.ร.ม.ที่ง่ายที่สุดและรู้จักกันดีจนถึงปัจจุบันคือ ให้นำตัวเลขจำนวนน้อยหารตัวเลขจำนวนมาก เศษที่เหลือมาเทียบกับเลขจำนวนน้อย จับหารกันไปเรื่อย ๆ ทำเช่นนี้จนลงตัว ได้ ห.ร.ม. เป็นเลขที่ลงตัวตัวสุดท้าย

ดังตัวอย่าง การหา ห.ร.ม. ของ 330 กับ 140


a = bq1 + r2 , 0  <  r2  <  b ;  330 = 140 . 2 + 50;
b = r2q2 + r3 , 0  <  r3  <  r2 ;  180 = 50 . 2 + 40;
r2 = r3q3 + r4 , 0  <  r4  <  r3 ;  50 = 40 . 1 + 10;
.......... ..........  40 = 10 . 4
rn-2 = rn-1qn-1 + rn , 0  <  rn  <  rn-1 ;
rn-1 = rnqn
ห.ร.ม. ของ (330, 140) คือ 10


รศ. ยืน ภู่วรวรรณ, สำนักบริการคอมพิวเตอร์ มหาวิทยาลัยเกษตรศาสตร์