16105-202-19 อัลกอริทึมของยูคลิด สำหรับการหา ห.ร.ม.

อัลกอริทึมของยูคลิด สำหรับการหา ห.ร.ม.

ยูคลิด เป็นนักคณิตศาสตร์สมัย 2 พันกว่าปีที่แล้ว ยูคลิดได้ให้วิธีการหา ห.ร.ม. จึงจัดว่าเป็นวิธีที่มีประสิทธิภาพสูงสุด และยอมรับกันมาจนปัจจุบัน การหา ห.ร.ม. โดยวิธีการหากำลังของเลขจำนวนเฉพาะ ดังที่กล่างมาแล้วเป็นวิธีที่ยาก ยูคลิดได้ให้หลักการเป็นทฤษฎีง่าย ๆ ว่า

       "ตัวหารร่วมมากที่สุดของ a และ b ก็จะเป็นตัวหารร่วมมากที่สุดของ a + kb และ b
   เมื่อ k เป็นเลขจำนวนเต็มใด ๆ"
          ดังนั้นหากคิดในทางกลับกัน ตัวหารร่วมมากสุดของ kb + a และ b ก็จะเป็นตัวหารร่วมมากของ a และ b ด้วย

    

            ตัวอย่าง
               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   

จากหลักการของยูคลิดสรุปได้ว่า .....ตัวหารร่วมมากของ 40, 10 ก็จะเป็นตัวหารร่วมมากของ 50, 40 ด้วย และไล่เรียงขึ้นไปถึง 330, 140 นั่นเอง