== อัลกอริทึมของยูคลิด สำหรับการหา ห.ร.ม. ==
'''เนื้อหา'''
ยูคลิด เป็นนักคณิตศาสตร์สมัย 2 พันกว่าปีที่แล้ว ยูคลิดได้ให้วิธีการหา ห.ร.ม. จึงจัดว่าเป็นวิธีที่มีประสิทธิภาพสูงสุด และยอมรับกันมาจนปัจจุบัน
การหา ห.ร.ม. โดยวิธีการหากำลังของเลขจำนวนเฉพาะ ดังที่กล่างมาแล้วเป็นวิธีที่ยาก ยูคลิดได้ให้หลักการเป็นทฤษฎีง่าย ๆ ว่า "ตัวหารร่วมมากที่สุดของ a และ b ก็จะเป็นตัวหารร่วมมากที่สุดของ a + kb และ b เมื่อ k เป็นเลขจำนวนเต็มใด ๆ"
'''วิธีการหา หรม.ของยูคลิด'''
1.จากตัวเลข 8 12
(8,12)12 = 8 x 1 + 4
(8, 4)8 = 4 x 2
ตอบ 4 คือตัวหารร่วมมากที่สุดของ 8 กับ 12
2.ตัวเลข 330, 140
(330, 140) 330 = 140 x 2 + 50
(140, 50) 140 = 50 x 2 + 40
(50,40) 50 = 40 x 1 + 10
(40,10) 40 = 10 x
ตอบ 10 เป็นตัวหารร่วมมากที่สุดของ 340, 140
อีกตัวอย่างจากโจรย์ข้อ 2 เป็นอีกวิธี ดังนี้ 2.1การหา ห.ร.ม. ของ 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
จากหลักการของยูคลิดสรุปได้ว่า ตัวหารร่วมมากของ 40, 10 ก็จะเป็นตัวหารร่วมมากของ 50, 40 ด้วย และไล่เรียงขึ้นไปถึง 330, 140 นั่นเอง
คำที่เกี่ยวข้อง[]
1.การหา หรม.
เอกสารอ้างอิง
http://blog.spu.ac.th/malee/2007/12/06/entry-2
