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

                                      

ในคณิตศาสตร์ ตัวหารร่วมมาก หรือ ห.ร.ม. (อังกฤษ: greatest common divisor: gcd) ของจำนวนเต็มสองจำนวนซึ่งไม่เป็นศูนย์พร้อมกัน คือจำนวนเต็มที่มากที่สุดที่หารทั้งสองจำนวนลงตัว
ตัวหารร่วมมากของ a และ b เขียนแทนด้วย gcd (a, b) หรือบางครั้งเขียนว่า (a, b) เช่น gcd (12, 18) = 6, gcd (−4, 14) = 2 และ gcd (5, 0) = 5 จำนวนสองจำนวนจะถูกเรียกว่า จำนวนเฉพาะสัมพัทธ์ ถ้าตัวหารร่วมมากเท่ากับ 1 เช่น 9 และ 28 เป็นจำนวนเฉพาะสัมพัทธ์
ตัวหารร่วมมากมีประโยชน์ในการทำเศษส่วนให้เป็นเศษส่วน

อย่างต่ำ ดังตัวอย่างนี้

= =
ซึ่งเราตัดตัวหารร่วมมากของ 42 และ 56 คือ 14 ออก

การหาตัวหารร่วมมาก ทำได้ด้วยการแยกตัวประกอบของจำนวนสองจำนวน และเปรียบเทียบตัวประกอบ ตัวอย่างเช่น gcd (18,84) เราจะแยกตัวประกอบ 18 = 2 x 32 และ 84 = 22 x 3 x 7 สังเกตว่านิพจน์ที่"ซ้อน"กันคือ 2 x 3 ดังนั้น gcd (18,84) = 6 ในทางปฏิบัติ วิธีนี้จะทำได้สำหรับจำนวนที่น้อยๆเท่านั้น เพราะการแยกตัวประกอบโดยทั่วไปนั้นจะยาวเกินไป

วิธีที่มีประสิทธิภาพกว่าคือ อัลกอริทึมของยุคลิด: หาร 84 ด้วย 18 จะได้ผลหารเท่ากับ 4 และเศษเหลือเท่ากับ 12 จากนั้นหาร 18 ด้วย 12 จะได้ผลหารเท่ากับ 1 และเศษเหลือเท่ากับ 6 จากนั้นหาร 12 ด้วย 6 จะได้เศษเหลือเท่ากับ 0 ซึ่งหมายความว่า 6 เป็น ห.ร.ม.

ตัวเลขจำนวนเต็มใด ๆ ก็ตามที่มีค่ามากกว่า 1 สามารถเขียนในรูปของตัวประกอบที่เป็นจำนวนเฉพาะได้

ถ้าให้ n เป็นเลขจำนวนเต็มที่มีค่ามากกว่า 1

n = ...
เมื่อ p คือเลขจำนวนเฉพาะ
<< ... <
, , , ...      เป็นเลขจำนวนเต็ม > 0
k >= 1
ตัวอย่างเช่น
28 = x x
200 = x x

                    

ที่มา: http://www.krudung.com/webst/2552/501/34/a1.html