การหาตัวหารร่วมมาก (ห.ร.ม.)

ตัวหารร่วมมาก

ความหมาย

ตัวหารร่วมมาก (ห.ร.ม.) คือเลขจำนวนเต็มบวกที่มีค่ามากที่สุด ซึ่งเมื่อนำมาหารเลขจำนวนเต็มบวก อื่นๆ ที่กำหนดให้ทุกจำนวนแล้วปรากฎว่าหารลงตัวได้ทุกจำนวน

หลักการหาร ห.ร.ม.

สมมุติว่าเรามีตัวเลขจำนวนเต็มบวกสองตัว a และ b เราจะหาตัวหารร่วมได้อย่างไร
ถ้าสมมุติให้ d เป็นตัวหารร่วม d หาร a ได้ลงตัว
d หาร b ได้ลงตัว
ถ้าเขียนจำนวน a และ b ในรูปแบบเลขจำนวนเฉพาะ
a =   ...
b =     ... โดยที่ ai, bi >= 0
เมื่อ d หาร a และ b ลงตัว เขียน d ในรูปแบบจำนวนเฉพาะ
d =    ... เมื่อ di <= ai
di <= bi
di <= min(ai, bi) หรืออาจกล่าวได้ว่า di น้อยกว่าค่าน้อยสุดระหว่าง ai, bi
แต่ถ้าจะให้เป็นตัวหารร่วมที่มากที่สุด (ห.ร.ม.) ค่า di จะต้องเท่ากับค่าน้อยที่สุดระหว่าง ai, bi
di = min(ai, bi)


     การหาตัวหารร่วมมากมี 3 วิธี คือ การหา ห.ร.ม. โดยพิจารณาจากตัวประกอบ การแยก ตัวประกอบ และการหารสั้น

      1. การหา ห.ร.ม. โดยพิจารณาตัวประกอบ

     พิจารณาตัวประกอบของ 12 และ 18
   ตัวประกอบร่วมของ 12 และ 18 ได้แก่ 1,2,3,6
    - ตัวประกอบร่วมที่มากที่สุด ได้แก่ 6
    - เรียกตัวประกอบร่วมที่มากที่สุดว่า ตัวหารร่วมมาก
    - ดังนั้น 6 เป็นตัวหารร่วมมากของ 12 และ 18
    - หรือ 6 เป็น ห.ร.ม. ของ 12 และ 18

    ห.ร.ม. ของ 16 และ 36 พิจารณาได้ดังนี้
    - ตัวประกอบของ 16 ได้แก่ 1 , 2 , 4 , 8 , 16
    - ตัวประกอบของ 36 ได้แก่ 1 , 2 , 3 , 4 , 6 , 9 , 12 , 18 , 36
    - ตัวประกอบร่วมของ 16 และ 36 ได้แก่ 1, 2, 4
    - ตัวประกอบร่วมที่มากที่สุด ได้แก่ 4
    - เรียกตัวประกอบร่วมที่มากที่สุดว่า ตัวหารร่วมมาก
    - ดังนั้น 4 เป็นตัวหารร่วมมากของ 16 และ 36
    - หรือ 4 เป็น ห.ร.ม. ของ 16 และ 36

        ตัวอย่างที่ 1 จงหา ห.ร.ม. ของ 39 และ 65
     วิธีทำ - ตัวประกอบของ 39 ได้แก่ 1 , 3 , 13 , 39
           - ตัวประกอบของ 65 ได้แก่ 1 , 5 , 13 , 65
           - ตัวประกอบร่วมของ 39 และ 65 ได้แก่ 1, 13
            - ตัวประกอบร่วมที่มากที่สุดของ 39 และ 65 ได้แก่ 13
             - ดังนั้น ห.ร.ม. ของ 39 และ 65 คือ 13
        ตัวอย่างที่ 2 จงหา ห.ร.ม. ของ 60, 78 และ 96
     วิธีทำ - ตัวประกอบของ 60 ได้แก่ 1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 15 , 20 , 30 , 60
           - ตัวประกอบของ 78 ได้แก่ 1 , 2 , 3 , 6 , 13 , 26 , 39 , 78
           - ตัวประกอบของ 96 ได้แก่ 1 , 2 , 3 , 4 , 6 , 8 , 12 , 16 , 24 , 32 , 48 , 96
           - ตัวประกอบร่วมของ 60, 78 และ 96 ได้แก่ 1, 2, 3, 6
           - ตัวประกอบร่วมที่มากที่สุดของ 60, 78 และ 96 ได้แก่ 6
           - ดังนั้น ห.ร.ม. ของ 60, 78 และ 96 คือ 6

.
    2. โดยการแยกตัวประกอบ มีวิธีการดังนี้

          (1) แยกตัวประกอบของจำนวนทุกจำนวนที่ต้องการหาร ห.ร.ม.
          (2) เลือกตัวประกอบที่ซ้ำกันของทุกจำนวนมาคูณกัน
          (3) ห.ร.ม. คือ ผลคูณที่ได้

       ตัวอย่าง     จงหา ห.ร.ม. ของ 56 84 และ 140
       วิธีทำ   56 =
                   84 =
                  104 =
     เลือกตัวที่ซ้ำกัน ที่อยู่ทั้ง 56 84และ 104 ตัวทีซ้ำกันเอามาซ้ำละ 1 ตัว
     คือ มีเลข 2 เลข 2 และ เลข 7
     ดังนั้น ห.ร.ม. =

    3. การหารสั้น มีวิธีการดังนี้

        1) นำจำนวนทั้งหมดที่ต้องการหา ห.ร.ม. มาเขียนเรียงกัน
        2) หาจำนวนเฉพาะที่สามารถหารจำนวนทั้งหมดได้ลงตัวมาหารไปเรื่อยๆ จนกว่าไม่สามารถหาได้
        3) นำตัวหารทุกตัวที่ใช้มาคูณกัน เป็นค่าของ ห.ร.ม.

        ตัวอย่าง จงหา ห.ร.ม. ของ 56 84 และ 140
       วิธีทำ  
                       2) 56 84 104                       2) 28 42 70
                       7) 14 21 35                            2 3 5

           ห.ร.ม. คือ 2 x 2 x 7 = 28

     4. การนำ ห.ร.ม. ไปใช้แก้โจทย์ปัญหา

         ตัวอย่าง      มีเชือกอยู่สามเส้น ยาวเส้นละ 48, 60 และ 108 เมตร ถ้าตัดแบ่งให้ยาวเส้นละเท่าๆกัน ให้ยาวที่สุดเท่าที่จะยาวได้ จะได้เชือกยาวเส้นละกี่เมตร และได้เชือกทั้งหมดกี่เส้น
วิธีทำ               48  =   2   x   2   x   2   x  2   x   3
                     60  =   2   x   2   x   3   x  5
                    108  =   2   x   2   x   3   x  3   x   3ห.ร.ม. คือ 2 x 2 x 3 หรือ 12ดังนั้น จะแบ่งเชือกได้ยาวที่สุดเส้นละ 12 เมตร เชือกเส้นแรกแบ่งได้        48 / 12  =  4  เส้น
เชือกเส้นที่สองแบ่งได้      60 / 12  =  5  เส้น
เชือกเส้นที่สามแบ่งได้    108 / 12  =  9  เส้น
ดังนั้นจะได้เชือกทั้งหมด 4 + 5 + 9  =  18  เส้น
ตอบ  จะได้เชือกยาวเส้นละ 12 เมตร  และได้เชือกทั้งหมด 18 เส้น

            ตัวอย่าง    แม่ค้าต้องการจัดมะม่วง 4 ผล ชมพู่ 8 ผล พุทรา 12 ผล ใส่ถาดโดยให้แต่ละถาดมีผลไม้แต่ละชนิดมากที่สุดและไม่ปนกัน จะได้ผลไม้ถาดละกี่ผลและแบ่งได้กี่ถาด
วิธีทำ               มีมะม่วง 4 ผล ชมพู่ 8 ผล พุทรา 12 ผล ห.ร.ม. คือ 4, 8 และ12 คือ     4ดังนั้น แบ่งผลไม้ได้ถาดละ    4 ผล
จะแบ่งมะม่วงได้     4   /    4    =   1   ถาด
จะแบ่งชมพู่ได้        8   /    4    =   2   ถาด
จะแบ่งพุทราได้       12 /   4    =   3   ถาด
ดังนั้น แบ่งผลไม้ได้ทั้งหมด   1+2+3 =  6  ถาด
ตอบ  ได้ผลไม้ถาดละ   4    ผลและแบ่งได้  6  ถาด


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

         ยูคลิด เป็นนักคณิตศาสตร์สมัย 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 นั่นเอง

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

ที่มา : ศิริกานต์ ชูก้าน.  ตัวหารร่วมมาก.  ค้นข้อมูล 6 ธันวาคม 54 จาก http://www.krudung.com/webst/2552/501/34/a4.html

ตัวหารร่วมมาก.  ค้นข้อมูล  6 ธันวาคม 54 จาก

          http://www.youtube.com/watch?v=yWgj8RuTf0k