หา ห.ร.ม. ง่ายกว่าที่คิด

ห.ร.ม.?

ตัวหารร่วมมาก (ห.ร.ม.) ของจำนวนเต็มสองจำนวน คือจำนวนเต็มบวกที่มีค่ามากที่สุดที่หารจำนวนเต็มทั้งสองจำนวนนั้นลงตัว

ถ้าพิจารณาจากนิยามของ ห.ร.ม. จะพบว่าวิธีการหนึ่งที่สามารถใช้ในการหา ห.ร.ม. ได้คือ การนำจำนวนเต็มบวกมาหารจำนวนเต็มสองจำนวน โดยเริ่มตั้งแต่การนำ 1,2,3,…ไปเรื่อยๆ มาหารจนถึงจำนวนที่น้อยกว่าในสองจำนวนที่ต้องการหา ห.ร.ม. นั้นและในระหว่างการคำนวณ จะต้องจดจำค่าที่มากที่สุดที่หารจำนวนทั้งสองลงตัว เมื่อดำเนินการเสร็จแล้ว จำนวนมากที่สุดที่จดจำไว้คือ ห.ร.ม. วิธีการนี้จะใช้งานได้สะดวกเมื่อจำนวนเต็มทั้งสองจำนวนมีค่าน้อย เช่น 21 กับ 14 ถ้าจำนวนเต็มทั้งสองมีค่ามาก เช่น 221 กับ 187 วิธีการข้างต้นจะใช้เวลานาน เพาระต้องทำการคำนวณทั้งหมด 187 ครั้ง นักเรียนจึงจะได้คำตอบว่า ห.ร.ม. คือ 17

ขั้นตอนวิธีของยุคลิด

เขียนจำนวนที่ต้องการหา ห.ร.ม. เรียงต่อกัน
ถ้าจำนวนที่น้อยกว่ามีค่าเป็นศูนย์ คำตอบคือจำนวนที่มีค่ามากกว่า และจบการทำงาน
ในบรรทัดถัดไป
- 3.1 เขียนเศษที่ได้จากการหารจำนวนที่มากกว่าด้วยจำนวนที่น้อยกว่า
- 3.2 คัดลอกจำนวนเต็มที่มีค่าน้อยกว่าลงในบรรทัดเดียวกัน
4. กลับไปทำกระบวนการรอบต่อไปในขั้นตอนที่ 2

เมื่อนำขั้นตอนวิธีของยุคลิดมาใช้หา ห.ร.ม. จะมีขั้นตอนในการคำนวณดังตัวอย่างด้านล่าง

ตัวอย่างการหา ห.ร.ม. ของ 187 และ 221

รอบที่	จำนวนทั้งสอง	คำอธิบาย
1	187 221	จำนวนที่น้อยกว่ายังไม่เป็นศูนย์ คำนวณเศษของการหาร 221 ด้วย 187 ได้ 34 ดังนั้น จะเขียนแทน 221 ด้วย 34 ในรอบที่ 2
2	187 34	จำนวนที่น้อยกว่ายังไม่เป็นศูนย์ คำนวณเศษของการหาร 187 ด้วย 34 ได้ 17 ดังนั้น จะเขียนแทน 187 ด้วย 17 ในรอบที่ 3
3	17 34	จำนวนที่น้อยกว่ายังไม่เป็นศูนย์ คำนวณเศษของการหาร 34 ด้วย 17 ได้ 0 ดังนั้น จะเขียนแทน 34 ด้วย 0 ในรอบที่ 4
4	17 0	จำนวนที่น้อยกว่าเป็นศูนย์ ดังนั้น ห.ร.ม. จึงมีค่าเท่ากับ 17

การหา ห.ร.ม. ด้วยวิธีดังกล่าวใช้การหารเพียง 3 ครั้ง ก็สามารถหาคำตอบที่ต้องการได้ เมื่อเทียบกับวิธีแรกที่ดำเนินการตามนิยามจะเห็นว่าวิธีการหา ห.ร.ม. ของยุคลิดนั้นทำให้ได้ผลลัพธ์เร็วกว่ามาก

แบบฝึกหัด: จงหา ห.ร.ม. ของ $301{,}981$ และ $449{,}573$

รอบที่	จำนวนทั้งสอง	คำอธิบาย
1	$301{,}981$ $449{,}573$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $449{,}573$ ด้วย $301{,}981$ คือ $147{,}592$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $449{,}573$ ด้วย $147{,}592$
2	$\Box$ $\Box$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\Box$ ด้วย $\Box$ คือ $\Box$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\Box$ ด้วย $\Box$
3	$\Box$ $\Box$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\Box$ ด้วย $\Box$ คือ $\Box$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\Box$ ด้วย $\Box$
4	$\Box$ $\Box$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\Box$ ด้วย $\Box$ คือ $\Box$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\Box$ ด้วย $\Box$
5	$\Box$ $\Box$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\Box$ ด้วย $\Box$ คือ $\Box$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\Box$ ด้วย $\Box$
6	$1{,}942$ $971$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\Box$ ด้วย $\Box$ คือ $\Box$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\Box$ ด้วย $\Box$
7	$0$ $971$	จำนวนที่น้อยกว่าเป็นศูนย์ ดังนั้น ห.ร.ม. จึงมีค่าเท่ากับ $971$

ดูเฉลยคำตอบ

รอบที่	จำนวนทั้งสอง	คำอธิบาย
1	$301{,}981$ $449{,}573$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $449{,}573$ ด้วย $301{,}981$ คือ $147{,}592$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $449{,}573$ ด้วย $147{,}592$
2	$\color{red}{301{,}981}$ $\color{red}{147{,}592}$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\color{red}{301{,}981}$ ด้วย $\color{red}{147{,}592}$ คือ $\color{red}{6{,}797}$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\color{red}{301{,}981}$ ด้วย $\color{red}{6{,}797}$
3	$\color{red}{6{,}797}$ $\color{red}{147{,}592}$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\color{red}{147{,}592}$ ด้วย $\color{red}{6{,}797}$ คือ $\color{red}{4{,}855}$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\color{red}{147{,}592}$ ด้วย $\color{red}{4{,}855}$
4	$\color{red}{6{,}797}$ $\color{red}{4{,}855}$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\color{red}{6{,}797}$ ด้วย $\color{red}{4{,}855}$ คือ $\color{red}{1{,}942}$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\color{red}{6{,}797}$ ด้วย $\color{red}{1{,}942}$
5	$\color{red}{1{,}942}$ $\color{red}{4{,}855}$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\color{red}{4{,}855}$ ด้วย $\color{red}{1{,}942}$ คือ $\color{red}{971}$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\color{red}{4{,}855}$ ด้วย $\color{red}{971}$
6	$1{,}942$ $971$	จำนวนที่น้อยกว่าไม่เป็นศูนย์ เศษจากการหาร $\color{red}{1{,}972}$ ด้วย $\color{red}{971}$ คือ $\color{red}{0}$ ดังนั้น ในขั้นถัดไปจะเขียนแทน $\color{red}{1{,}972}$ ด้วย $\color{red}{0}$
7	$0$ $971$	จำนวนที่น้อยกว่าเป็นศูนย์ ดังนั้น ห.ร.ม. จึงมีค่าเท่ากับ $971$

ขั้นตอนวิธีของยุคลิด

ตัวอย่างการหา ห.ร.ม. ของ 187 และ 221

แบบฝึกหัด: จงหา ห.ร.ม. ของ 301,981301{,}981 และ 449,573449{,}573

Related Posts

Leave a Reply

แบบฝึกหัด: จงหา ห.ร.ม. ของ $301{,}981$ และ $449{,}573$