ตัวหารร่วมมาก - วิกิพีเดีย

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

### จากวิกิพีเดีย สารานุกรมเสรี

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

ตัวหารร่วมมากของ 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·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

ห.ร.ม.เป็นฟังก์ชันการคูณ กล่าวคือ ถ้า a1 และ a2 เป็นจำนวนเฉพาะสัมพัทธ์แล้ว gcd(a1·a2, b) = gcd(a1, b)·gcd(a2, 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·x = a และ d·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) แล้ว อัลกอริทึมของยุคลิดสามารถปรับใช้หา ห.ร.ม. ได้

ต่อไปนี้เป็นตัวอย่างของโดเมนจำนวนเต็มซึ่งสองสมาชิกไม่มี ห.ร.ม.

สมาชิก และ 2 คือ "ตัวหารร่วม maximal" (กล่าวคือ ตัวหารร่วมใด ๆ ที่เป็นจำนวนเท่าของ 2 จะ associate กับ 2 สำหรับ ก็มีคุณสมบัติเช่นเดียวกัน) แต่ค่าทั้งสองนี้ไม่ associate กัน ดังนั้นเราสามารถสรุปได้ว่าไม่มี ห.ร.ม. ของ a และ b

## [แก้] ดูเพิ่ม

- ตัวคูณร่วมน้อย
- ตัวหารร่วมน้อย (Lowest common denominator)
- อัลกอริทึมการคำนวนตัวหารร่วมมากแบบไบนานี (Binary GCD algorithm)

## [แก้] ลิงก์ภายนอก

- Online gcd calculator

ดึงข้อมูลจาก "http://th.wikipedia.org../../../%E0%B8%95/%E0%B8%B1/%E0%B8%A7/%E0%B8%95%E0%B8%B1%E0%B8%A7%E0%B8%AB%E0%B8%B2%E0%B8%A3%E0%B8%A3%E0%B9%88%E0%B8%A7%E0%B8%A1%E0%B8%A1%E0%B8%B2%E0%B8%81.html".

หมวดหมู่: ทฤษฎีจำนวน

##### Views

- บทความ
- อภิปราย
- รุ่นปัจจุบัน

##### ค้นหา

##### ภาษาอื่น

- Deutsch
- English
- Esperanto
- Español
- Français
- Bahasa Indonesia
- 日本語
- Nederlands
- Polski
- Русский
- Slovenščina
- Svenska
- 中文