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

ในคณิตศาสตร์ **ตัวหารร่วมมาก** หรือ **ห.ร.ม.** (: gcd) ของจำนวนเต็มสองจำนวนซึ่งไม่เป็นศูนย์พร้อมกัน คือจำนวนเต็มที่มากที่สุดที่หารทั้งสองจำนวนลงตัว

ตัวหารร่วมมากของ *a* และ *b* เขียนแทนด้วย gcd(*a*, *b*) หรือบางครั้งเขียนว่า (*a*, *b*) เช่น gcd(12, 18)  = 6, gcd(−4, 14)  = 2 และ gcd(5, 0)  = 5 จำนวนสองจำนวนจะถูกเรียกว่า *[[จำนวนเฉพาะสัมพัทธ์]]* ถ้าตัวหารร่วมมากเท่ากับ 1 เช่น 9 และ 28 เป็นจำนวนเฉพาะสัมพัทธ์

ตัวหารร่วมมากมีประโยชน์ในการทำเศษส่วนให้เป็นเศษส่วนอย่างต่ำ ดังตัวอย่างนี้
:{42\over56}={3\cdot14\over4\cdot14}={3\over4}

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

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

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

## คุณสมบัติ

ตัวหารร่วมของ *a* และ *b* จะเป็นตัวหารของ gcd(*a*, *b*)

gcd(*a*, *b*) เมื่อ *a* และ *b* ไม่เป็นศูนย์พร้อมกัน จะเป็นจำนวนเต็มบวก *d* ที่น้อยที่สุดที่สามารถเขียนในรูป *d* = *a*·*p* + *b*·*q* เมื่อ *p* และ *q* เป็นจำนวนเต็ม จำนวน *p* และ *q* สามารถคำนวณได้จากขั้นตอนวิธีของยุคลิดเพิ่มเติม

ถ้า *a* หาร *b*·*c* ลงตัว และ gcd(*a*, *b*)  = *d* แล้ว *a*/*d* หาร *c* ลงตัว

ถ้า *m* เป็นจำนวนเต็มใด ๆ แล้ว gcd(*m*·*a*, *m*·*b*)  = *m*·gcd(*a*, *b*) และ gcd(*a* + *m*·*b*, *b*)  = gcd(*a*, *b*) ถ้า *m* เป็นตัวหารร่วมของ *a* และ *b* แล้ว gcd(*a*/*m*, *b*/*m*)  = gcd(*a*, *b*)/*m*

ห.ร.ม. เป็นฟังก์ชันเชิงการคูณ กล่าวคือ ถ้า *a*1 และ *a*2 เป็นจำนวนเฉพาะสัมพัทธ์แล้ว gcd(*a*1·*a*2, *b*) = gcd(*a*1, *b*)·gcd(*a*2, *b*)

ห.ร.ม. ของจำนวนสามจำนวน หาได้จาก gcd(*a*, *b*, *c*) = gcd(gcd(*a*, *b*) , *c*) = gcd(*a*, gcd(*b*, *c*)) นั่นคือ ห.ร.ม.มีสมบัติการเปลี่ยนหมู่

gcd (*a*, *b*) นั้นมีความเกี่ยวข้องกับตัวคูณร่วมน้อย lcm(*a*, *b*) : จะได้ว่า
:gcd(*a*, *b*)·lcm(*a*, *b*)  = *a*·*b*
สูตรนี้มักถูกใช้เพื่อคำนวณค่าคูณร่วมน้อย โดยเริ่มด้วยการหา ห.ร.ม. โดยใช้ขั้นตอนวิธีของยุคลิด จากนั้นหารผลคูณของตัวเลขทั้งสองด้วย ห.ร.ม. สมบัติการแจกแจงด้านล่างนี้เป็นจริง:
:gcd(*a*, lcm(*b*, *c*))  = lcm(gcd(*a*, *b*), gcd(*a*, *c*))
:lcm(*a*, gcd(*b*, *c*))  = gcd(lcm(*a*, *b*), lcm(*a*, *c*))

การนิยามให้ gcd(0, 0) = 0 และ lcm(0, 0)  = 0 นั้นมีประโยชน์เนื่องจากจะทำให้เซตของจำนวนธรรมชาติเป็นแลตทิซแบบกระจายที่บริบูรณ์ โดยที่ ห.ร.ม. เป็นการดำเนินการ meet และ ค.ร.น. เป็นการดำเนินการ join การขยายนิยามนี้สอดคล้องกับนัยทั่วไปของนิยามสำหรับริงสลับที่ด้านล่าง

ในระบบพิกัดคาร์ทีเซียน gcd(*a*, *b*) สามารถตีความว่าเป็นจำนวนของจุดที่มีพิกัดเป็นจำนวนเต็มบนเส้นตรงที่เชื่อมจุด (0, 0) และจุด (*a*, *b*) โดยที่ไม่นับจุด (0, 0)

## ห.ร.ม. ในริงสลับที่
ห.ร.ม. สามารถนิยามให้กว้างขึ้นสำหรับสมาชิกของริงสลับที่

ถ้า *R* เป็นริงสลับที่ และให้ *a* และ *b* อยู่ใน *R* จะเรียกสมาชิก *d* ที่อยู่ใน *R* ว่า *ตัวหารร่วม*ของ *a* และ *b* ถ้ามันหาร *a* และ *b* ลงตัว (กล่าวคือ ถ้ามีสมาชิก *x* และ *y* ใน *R* ที่ทำให้ *d*&#183;*x* = *a* และ *d*&#183;*y* = *b*) ถ้า *d* เป็นตัวหารร่วมของ *a* และ *b* และตัวหารร่วมทุกตัวของ *a* และ *b* หาร *d* ลงตัว จะเรียก *d* ว่าเป็น *ตัวหารร่วมมาก*ของ *a* และ *b*

สังเกตว่าจากนิยามนี้ สมาชิก *a* และ *b* อาจมี ห.ร.ม. หลายค่า หรือไม่มี ห.ร.ม. เลย แต่ถ้า *R* เป็นโดเมนจำนวนเต็ม (integral domain) แล้ว ห.ร.ม. สองตัวใด ๆ ของ *a* และ *b* ต้องเป็นสมาชิก associate ถ้า *R* เป็นโดเมน unique factorization แล้ว สมาชิกใด ๆ สองสมาชิกจะมี ห.ร.ม. เสมอ และถ้า *R* เป็นโดเมนยุคลิเดียน (Euclidean domain) แล้ว ขั้นตอนวิธีของยุคลิดสามารถปรับใช้หา ห.ร.ม. ได้

ต่อไปนี้เป็นตัวอย่างของโดเมนจำนวนเต็มซึ่งสองสมาชิกไม่มี ห.ร.ม.
:R = \mathbb{Z}[\sqrt{-3}],\quad a = 4 = 2\cdot 2 = (1+\sqrt{-3}) (1-\sqrt{-3}) ,\quad b = (1+\sqrt{-3}) \cdot 2
สมาชิก 1+\sqrt{-3} และ 2 คือ "ตัวหารร่วม maximal" (กล่าวคือ ตัวหารร่วมใด ๆ ที่เป็นจำนวนเท่าของ 2 จะ associate กับ 2 สำหรับ 1+\sqrt{-3} ก็มีคุณสมบัติเช่นเดียวกัน) แต่ค่าทั้งสองนี้ไม่ associate กัน ดังนั้นเราสามารถสรุปได้ว่าไม่มี ห.ร.ม. ของ *a* และ *b*

## ดูเพิ่ม
* ตัวคูณร่วมน้อย
* ตัวส่วนร่วมน้อย (Lowest common denominator)
* ขั้นตอนวิธีการคำนวณตัวหารร่วมมากแบบไบนารี (Binary GCD algorithm)

## แหล่งข้อมูลอื่น
* Online gcd calculator

หมวดหมู่:เลขคณิตมูลฐาน
หมวดหมู่:ฟังก์ชันเชิงการคูณ