บทความนี้เรามาดูวิธีการหา ห.ร.ม. แบบธรรมดา กับ การหา ห.ร.ม. ด้วยอัลกอริทึมของยุคลิดกันครับ
ห.ร.ม. ย่อมาจาก หารร่วมมาก นั่นก็คือ ตัวหารร่วมที่มากทีสุด 

ห.ร.ม. หมายถึง ตัวหารร่วมตั้งแต่สองจำนวนขึ้นไป ที่มีค่ามากที่สุด
การหา ห.ร.ม.
การหา ห.ร.ม. โดยการแยกตัวประกอบ
ตัวประกอบ หมายถึง  จำนวนนับที่สามารถหารจำนวนนับได้ลงตัว  เช่น ตัวประกอบของ 3 คือ  1 และ 3 , ตัวประกอบของ 20 คือ 1, 2, 4, 5, 10, 20


วิธีการหา ห.ร.ม. โดยวิธีการแยกตัวประกอบ เริ่มด้วยการ แยกตัวประกอบของตัวที่ต้องการหาทุกตัว จากนั้น เอาตัวประกอบที่ซ้ำกันของทุกตัวมา คูณกัน ก็จะได้ ห.ร.ม. ออกมา


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

จงหา ห.ร.ม. ของ  56   84  และ 140

วิธีทำ

56 แยกตัวประกอบจะได้ 2 x 2 x 2 x 7

84 แยกตัวประกอบจะได้ 2 x 2 x 3 x 7

140 แยกตัวประกอบจะได้ 2 x 2 x 5 x 7

เลือกตัวประกอบที่ซ้ำกันของ 56, 84, 140 ซึ่งก็คือตัวสีเขียว ๆ นั่นเอง เอามาคูณกัน จะได้ 2 x 2 x 7 จะได้ ห.ร.ม. เท่ากับ 28
การหา ห.ร.ม. โดยการหารสั้น
วิธีการหา ห.ร.ม. โดยการหารสั้น เริ่มด้วยการ นำตัวที่ต้องหารหา ห.ร.ม. มาเขียนเรียงกัน จากนั้น หาจำนวนที่หารทั้งหมดลงตัวมาหารเรื่อย ๆ จนกว่าจะไม่สามารถหาได้แล้ว เสร็จแล้วก็เอาจำนวนที่เป็นตัวหารทั้งหมดมาคูณกัน ก็จะได้ ห.ร.ม. ออกมา


ตัวอย่างการหา ห.ร.ม. โดยการหารสั้น

จงหา ห.ร.ม. ของ  56   84  และ 140

วิธีทำ

2 ) 56    841    40
2 ) 28     42    70
7 ) 14     21    35
       2      3      5

เอาตัวหารทั้งหมดมาคูณกัน จะได้ 2 x 2 x 7 จะได้ ห.ร.ม. เท่ากับ 28
อัลกอริทึมของยุคลิด
ยูคลิด (Euclid) เป็นนักคณิตศาสตร์ชาวกรีกที่สำคัญ และเป็นที่รู้จักกันดี เขาได้กล่าวถึงการหา ห.ร.ม. หรือ ตัวหารร่วมมาก ของจำนวนนับ 2 จำนวนที่มีค่ามากอย่างรวดเร็ว ซึ่งในปัจจุบันเรียกว่า ขั้นตอนวิธีแบบยุคลิด


ขั้นตอนวิธีแบบยูคลิด (Euclidean Algorithm) เป็นขั้นตอนวิธีที่ใช้ในการหาค่า (a,b) และจำนวนเต็ม x, y ที่ทำให้ (a,b)=ax+by โดยการใช้ขั้นตอนวิธีการหาร แต่เนื่องจาก 
(a,b)=(|a|,|b|) ดังนั้นเราจึงพิจารณากรณีที่ a,b เป็นจำนวนเต็มบวกเท่านั้น กล่าวคือ



ตัวอย่าง การหา ห.ร.ม. โดยวิธีแบบยุคลิด
จงหา ห.ร.ม. ของ 231, 525

วิธีทำ

525 = 231*2 + 63

231 = 63*3 + 42

63 = 42*1 + 21

42 = 21*2 + 0

ห.ร.ม. ก็คือ 21


จงหา ห.ร.ม. ของ 68, 38

วิธีทำ

68 = 38*1 + 30

38 = 30*1 + 8

30 = 8*3 + 6

8 = 6*1 + 2

6 = 2*3 + 0

ห.ร.ม. ก็คือ 2


จงหา ห.ร.ม. ของ 56, 84, 140

gcd(56, 84, 140) = gcd(gcd(56, 84), 140) = gcd(56, gcd(84, 140))

วิธีทำ หา ห.ร.ม. ของ 56 กับ 84 ก่อน

84 = 56*1 + 28

56 = 28*2 + 0

ห.ร.ม. ของ 84 กับ 56 ก็คือ 28

ต่อไปหา ห.ร.ม. ของ 28 กับ 140

140 = 28*5 + 0

ห.ร.ม. ของ 140 กับ 28 ก็คือ 28

ดังนั้น ห.ร.ม. ก็คือ 28