ถ้าพิจารณาจากนิยามของ ห.ร.ม. จะพบว่าวิธีการหนึ่งที่สามารถใช้ในการหา ห.ร.ม. ได้คือ การนำจำนวนเต็มบวกมาหารจำนวนเต็มสองจำนวน โดยเริ่มตั้งแต่การนำ 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\) |