ดูต้นฉบับสำหรับ ตัวหารร่วมมาก

{{ต้องการอ้างอิง}}

ใน[[คณิตศาสตร์]] '''ตัวหารร่วมมาก''' หรือ '''ห.ร.ม.''' ({{langx|en|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 เป็นจำนวนเฉพาะสัมพัทธ์

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

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

== การหา ห.ร.ม. ==
การหาตัวหารร่วมมาก ทำได้ด้วย[[การแยกตัวประกอบ]]ของจำนวนสองจำนวน และเปรียบเทียบตัวประกอบ ตัวอย่างเช่น gcd(18,84) เราจะแยกตัวประกอบ 18 = 2·3<sup>2</sup> และ 84 = 2<sup>2</sup>·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''<sub>1</sub> และ ''a''<sub>2</sub> เป็นจำนวนเฉพาะสัมพัทธ์แล้ว gcd(''a''<sub>1</sub>·''a''<sub>2</sub>, ''b'') = gcd(''a''<sub>1</sub>, ''b'') ·gcd(''a''<sub>2</sub>, ''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) แล้ว ขั้นตอนวิธีของยุคลิดสามารถปรับใช้หา ห.ร.ม. ได้

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

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

== แหล่งข้อมูลอื่น ==
* [http://wims.unice.fr/wims/wims.cgi?module=tool/popup.en&search=gcd Online gcd calculator]

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