ตัวประกอบร่วมมาก หรือเรียกอีกอย่างว่าตัวหารร่วมมาก และตัวประกอบร่วมมาก หมายถึงตัวหารที่มีค่ามากที่สุดของจำนวนเต็มสองจำนวนขึ้นไป.
ตัวหารร่วมมากของ a, b แสดงเป็น (a, b) ในทำนองเดียวกัน ตัวหารร่วมมากของ a, b, c แสดงเป็น (a, b, c) ตัวหารร่วมมากของจำนวนเต็มหลายจำนวนมีเครื่องหมายเหมือนกัน.
มีหลายวิธีในการหาตัวหารร่วมมาก ตัวประกอบร่วม ได้แก่ การแยกตัวประกอบเฉพาะ การหารสั้น การหารเฟสแบบต่อเนื่อง และการลบเพิ่มเติม.
แนวคิดที่สอดคล้องกับตัวหารร่วมมากคือ ตัวคูณร่วมน้อย และตัวคูณร่วมน้อยของ a, b บันทึกเป็น [a, b].
ถ้าจำนวน a หารด้วยจำนวน b ลงตัว a จะเรียกว่า ตัวคูณของ b และ b จะเรียกว่า ตัวหารของ ก.
ตัวหารและตัวคูณต่างก็แสดงถึงความสัมพันธ์ของจำนวนเต็มหนึ่งกับอีกจำนวนหนึ่ง และไม่สามารถมีอยู่โดยลำพังได้ ตัวอย่างเช่น เราสามารถพูดได้เพียงว่า 16 เป็นผลคูณของจำนวนหนึ่ง และ 2 เป็นตัวหารของจำนวนหนึ่ง แต่เราไม่สามารถพูดโดยแยกได้ว่า 16 เป็นผลคูณและ 2 เป็นตัวหาร.
ตัวหารร่วมมาก (GCD) หรือเรียกอีกอย่างว่า ตัวประกอบร่วมมาก (GCF) ของจำนวนเต็มสองจำนวนขึ้นไป คือ จำนวนบวกที่มากที่สุดที่หารจำนวนทั้งหมดลงตัว (โดยไม่เหลือเศษ)
ตัวอย่างเช่น GCD ของ 18 และ 24 คือ 6 เนื่องจาก 6 เป็นจำนวนสูงสุดที่หารทั้งสองจำนวนลงตัว
GCD มีประโยชน์สำหรับ:
การลดรูปเศษส่วน ให้เป็นพจน์ที่น้อยที่สุด
การแยกตัวประกอบ และการแก้โจทย์คณิตศาสตร์ สมการ
การลดอัตราส่วน ให้เป็นรูปแบบที่ง่ายที่สุด
การแก้ปัญหาทางทฤษฎีจำนวน ที่เกี่ยวข้องกับการหารลงตัวหรือเลขคณิตแบบแยกส่วน
การค้นหารูปแบบทั่วไป ในจำนวนเต็มหรืออัลกอริทึมการเพิ่มประสิทธิภาพที่อาศัยโครงสร้างที่ซ้ำกัน
ช่วยขจัดความซ้ำซ้อนและค้นหาประสิทธิภาพในการใช้งานทางคณิตศาสตร์และในโลกแห่งความเป็นจริง
มีหลายวิธีในการหา GCD ของสองจำนวน:
การระบุปัจจัย: ระบุตัวหารทั้งหมดของแต่ละจำนวนและค้นหาตัวที่ร่วมกันมากที่สุด
การแยกตัวประกอบเฉพาะ: แยกตัวเลขทั้งสองตัวออกเป็นตัวประกอบเฉพาะ แล้วคูณตัวประกอบสามัญ
อัลกอริทึมแบบยุคลิด: ลบตัวเลขที่น้อยกว่าออกจากตัวเลขที่มากกว่าซ้ำๆ หรือใช้การหารด้วยเศษจนกระทั่งเศษเหลือเท่ากับศูนย์ เศษที่เหลือไม่เท่ากับศูนย์คือ GCD
ตัวอย่างของอัลกอริทึมยูคลิดสำหรับ GCD(a, b):
GCD(48, 18):
48 ÷ 18 = เศษ 2 12
18 ÷ 12 = เศษ 1 6
12 ÷ 6 = เศษ 2 0
→ GCD คือ 6
ใช้ GCD เมื่อ:
การลดเศษส่วนหรืออัตราส่วน ให้เป็นรูปแบบที่ง่ายที่สุด
การแก้สมการไดโอแฟนไทน์ (สมการที่มีผลลัพธ์เป็นจำนวนเต็ม)
การเพิ่มประสิทธิภาพอัลกอริทึม ที่เกี่ยวข้องกับวงจร การหมุน หรือการแบ่งส่วน
การกำหนดว่าตัวเลขสองตัวเป็นจำนวนเฉพาะสัมพันธ์กันหรือไม่ (กล่าวคือ GCD ของตัวเลขสองตัวคือ 1)
การแบ่งรายการออกเป็นกลุ่ม โดยให้มีขนาดใหญ่เท่ากันมากที่สุดเท่าที่จะเป็นไปได้ (เช่น การแบ่งสิ่งของออกเท่าๆ กันระหว่างผู้คนหรือภาชนะ)
GCD มีความสำคัญพื้นฐานทั้งในการคำนวณทางคณิตศาสตร์ขั้นพื้นฐานและทฤษฎีจำนวนขั้นสูงหรือการออกแบบอัลกอริทึม
