ชุดที่ 3 การหา ห.ร.ม. โดยขั้นตอนวิธีแบบยูคลิด









ยูคลิดแห่งอเล็กซานเดรีย (Euclid of Alexandria) 

ยูคลิดเป็นนักคณิตศาสตร์ที่สำคัญ และเป็นที่รู้จักกันดี ยูคลิดเกิดที่เมืองอเล็กซานเดรีย ประเทศอิยิปต์ เมื่อราว 365 ปี ก่อนคริสตกาล มีชีวิตอยู่จนกระทั่งประมาณปี 300 ก่อนคริสตกาล สิ่งที่มีชื่อเสียงคือผลงานเรื่องThe Elements 

ผลงานของยูคลิดเป็นที่ยอมรับอย่างกว้างขวางมาก และกล่าวกันว่าผลงาน The Elements เป็นผลงานที่ต่อเนื่อง และดำเนินมาก่อนแล้วในเรื่องผลงานของ นักคณิตศาสตร์ยุคก่อน เช่น เธลีส (Thales), ฮิปโปเครตีส (Hippocrates) และปีทาโกรัส (Pythagoras) อย่างไรก็ตาม หลายผลงานที่มีในหนังสือนี้เป็นที่เชื่อกันว่าเป็นบทพิสูจน์และผลงานของยูคลิดเอง ผลงานของยูคลิดได้รับการนำมาจัดทำใหม่ และตีพิมพ์เผยแพร่ครั้งแรกในปี ค.ศ. 1482หลังจากนั้นมีผู้นำมาตีพิมพ์อีกมากมายนับจำนวนครั้งไม่ถ้วนหลัก การหา ห.ร.ม.ที่ง่ายที่สุดและรู้จักกันดีจนถึงปัจจุบันคือ ให้นำตัวเลขจำนวนน้อยหารตัวเลขจำนวนมาก เศษที่เหลือมาเทียบกับเลขจำนวนน้อย จับหารกันไปเรื่อย ๆ ทำเช่นนี้จนลงตัว ได้ ห.ร.ม. คือ ตัวเลขตัวสุดท้ายที่นำไปหารได้ลงตัว 



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



การหา ห.ร.ม. โดยขั้นตอนวิธีแบบยูคลิด 

การหา ห.ร.ม. ของจำนวนนับที่มีค่ามาก ก่อให้เกิดความยุ่งยากในการแยกตัวประกอบ นักคณิตศาสตร์ชาวกรีก Euclid of Alexandria ได้คิดค้นวิธีหา ห.ร.ม. อีกวิธีหนึ่ง ปัจจุบันเรียกวิธีนี้ว่า ขั้นตอนวิธีแบบยูคลิด ทำได้โดยตั้งหารทีละคู่ โดยนำจำนวนน้อยไปหารจำนวนมาก ดังตัวอย่างต่อไปนี้
 ให้นักเรียนพิจารณา การหา ห.ร.ม. ของ 362 และ 684 โดยใช้ขั้นตอนวิธีแบบยูคลิด        
           1
362 ) 684
        362
        322


ขั้นที่ 1  หารจำนวน 684 ด้วย 362

362
684
362
1

322


เขียนเป็นขั้นตอนวิธียูคลิด
 




362 เป็นตัวหารตัวที่หนึ่ง เศษที่ได้ คือ 322

ขั้นที่ 2  หารจำนวน 362 ด้วย 322 ที่เป็นเศษในขั้นที่ 1
           1
322 ) 362
        322
          40


1
362
322
684
362
1

40
322


เขียนเป็นขั้นตอนวิธียูคลิด
 





322 เป็นตัวหารตัวที่สอง เศษที่ได้ คือ 40

            8
  40 ) 322
        320
           2


ขั้นที่ 3  หารจำนวน 322 ด้วย 40 ที่เป็นเศษในขั้นที่ 2
เขียนเป็นขั้นตอนวิธียูคลิด
1
362
322
684
362
1

40
322
320
8


2


 





40 เป็นตัวหารตัวที่สาม เศษที่ได้ คือ 2

         20
   2 ) 40
        40
          0


ขั้นที่ 4  หารจำนวน 40 ด้วย 2 ที่เป็นเศษในขั้นที่ 3
เขียนเป็นขั้นตอนวิธียูคลิด
1
362
322
684
362
1
20
40
40
322
320
8


2


 






          การหารในครั้งนี้ลงตัวจึงเป็นอันสิ้นสุดการหารและจะได้ตัวหารตัวสุดท้ายคือ 2
 เป็น ห.ร.ม. ของ 362 และ 684
8
ในทางปฏิบัติ การ ห.ร.ม. โดยขั้นตอนวิธีแบบยูคลิด รวมทุกขั้นตอนเขียนได้ดังนี้
1
362
322
684
362
1
20
40
40
322
320
8


2


 






ตัวอย่างที่ 1 จงหา ห.ร.ม. ของ 420 และ 865
16
420
400
865
840
2
4
20
20
25
20
1


5


วิธีทำ


               



ดังนั้น  ห.ร.ม. ของ 420 และ 865 คือ 5
ตอบ    5

สำหรับ การหา ห.ร.ม. ของจำนวนนับสามจำนวนสามารถใช้หลักการเดียวกัน คือ
1.      หา ห.ร.ม. ของสองจำนวน ส่วนใหญ่จะหา ห.ร.ม. ของสองจำนวนที่มีค่ามาก
2.      หา ห.ร.ม. อีกครั้งของจำนวนที่เหลือ กับ ห.ร.ม. ที่หาได้ในข้อที่ 1 โดย ห.ร.ม.                  ที่หาได้ในข้อที่ 2 จะเป็น ห.ร.ม. ของทั้งสามจำนวน

ดัง ตัวอย่างที่ 2 และ ตัวอย่างที่ 3

9
 














ตัวอย่างที่ 2 จงหา ห.ร.ม. ของ 129, 602 และ 774
วิธีทำ   เราเลือก 602 และ 774 มาหา ห.ร.ม. ก่อน เพราะเป็นจำนวนที่มีค่ามาก                  ใช้ขั้นตอนวิธีแบบยูคลิด         ในหารหา ห.ร.ม. ดังนี้
3
602
516
744
602
1
86
172
2


172


 





จะได้ ห.ร.ม. ของ 602 และ 774 คือ 86
หา ห.ร.ม. ของ 86 และ 129 เนื่องจากจำนวนทั้งสองมีค่าไม่มากนัก การหา ห.ร.ม. อาจใช้วิธีแยกตัวประกอบมาช่วย ดังนี้
          86    = 2 x 43
           129  = 3 x 43

           ดังนั้น ห.ร.ม. ของ 86 และ 129 คือ 43
           นั้นคือ ห.ร.ม. ของ 129, 602 และ 774  คือ 43
           ตอบ  43

ตัวอย่างที่ 3 จงหา ห.ร.ม. ของ 786, 917 และ 1,048
วิธีทำ  หา ห.ร.ม. ของ 917 และ 1,048 โดยใช้ขั้นตอนวิธีแบบยูคลิด ดังนี้
7
917
917
1,048
917
1


131


 




ดังนั้น ห.ร.ม. ของ 917 และ 1,048  คือ 131
           หา ห.ร.ม. ของ 131 และ 786 โดยใช้ขั้นตอนวิธีแบบยูคลิด ดังนี้

131
786
6


786


 


         
          ดังนั้น ห.ร.ม. ของ 131 และ 786 คือ 131
           นั้นคือ ห.ร.ม. ของ 786, 917 และ 1,048 คือ  131
           ตอบ 131
10
นักเรียนเคยเรียนการหา ค.ร.น. ของจำนวนนับสองจำนวนแล้ว โดยใช้วิธีแยกตัวประกอบหรือตั้งหาร


ทบทวน
การหา ค.ร.น. โดยใช้วิธีแยกตัวประกอบ
จงหา ค.ร.น. ของ 5, 15, และ 40
วิธีทำ             5      =    5
                     15    =    5 x 3
                     40    =    5 x 2 x 2 x 2
ดังนั้น ค.ร.น. ของ 5, 15, และ 40 คือ 5 x 3 x 2 x 2 x 2 = 120
ตอบ  ค.ร.น. ของ 5, 15, และ 40 คือ 120

การหา ค.ร.น. โดยใช้วิธีตั้งหาร
จงหา ค.ร.น. ของ 5, 15, และ 40
5
10   15   40
2
  2     3     8

   1     3    4



วิธีทำ                   



ดังนั้น ค.ร.น. ของ 5, 15, และ 40 คือ 5 x 2 x 1 x 3 x 4 = 120
ตอบ  ค.ร.น. ของ 5, 15, และ 40 คือ 120


นอกจากนี้เรายังสามารถหา ค.ร.น. ของจำนวนนับสองจำนวนจากการนำ ห.ร.ม. มาใช้ในการหา ค.ร.น. โดยใช้สูตรดังนี้
ค.ร.น. ของสองจำนวนที่กำหนด
 


หรือ



11
ตัวอย่างที่ 4 จงหา ค.ร.น. ของ 244 และ 427
วิธีทำ  หา ห.ร.ม. ของ 244 และ 427 โดยใช้ขั้นตอนแบบยูคลิด
1
244
183
427
244
1
61
183
3


183


 





           ดังนั้น ห.ร.ม. ของ 244 และ 427 คือ 61
นั้นคือ ค.ร.น.ของ 244 และ 427 คือ  
ตอบ  1,708

ในกรณีการหา ค.ร.น. ของจำนวนนับสามจำนวน อาจใช้วิธีเดียวกันกับการหา ห.ร.ม. ของจำนวนนับสามจำนวน คือ
1.      หา ค.ร.น. ของสองจำนวนก่อน
2.      หา ค.ร.น. ของจำนวนที่เหลือกับ ค.ร.น.ที่หาได้ในข้อที่ 1 โดย ค.ร.น. ที่หาได้ในข้อที่ 2 เป็น ค.ร.น. ของทั้งสามจำนวน


ตัวอย่างที่ 5 จงหา ค.ร.น. ของ 168, 420 และ 588
วิธีทำ  ขั้นที่1 หา ห.ร.ม. ของ 168 และ 420 โดยใช้ขั้นตอนแบบยูคลิด
2
168
168
420
336
2


84


 




           ดังนั้น ห.ร.ม. ของ 168 และ 420 คือ 84
นั้นคือ ค.ร.น. ของ 168 และ 420 คือ  









12
           ขั้นที่ 2 หา ห.ร.ม. ของ 840 และ 588 โดยใช้ขั้นตอนวิธีแบบยูคลิด  ดังนี้
2
588
504
840
588
1
84
252
3


252


 





           ดังนั้น ห.ร.ม. ของ 588 และ 840 คือ 84
นั้นคือ ค.ร.น. ของ 588 และ 840 คือ  
ตอบ  5,880

1 ความคิดเห็น: