ตัวหารร่วมมาก ( GCD ) ของจำนวนเต็มaและbซึ่งอย่างน้อยหนึ่งตัวต้องไม่เป็นศูนย์ คือจำนวนเต็มบวกที่ มากที่สุด dซึ่งdเป็นตัวหารของทั้งaและbกล่าวคือ มีจำนวนเต็มeและfที่a = deและb = dfและdเป็นจำนวนเต็มที่ใหญ่ที่สุดดังกล่าว โดยทั่วไป GCD ของaและbจะใช้สัญลักษณ์gcd ( a , b ) ^{[ 8 ]}

เมื่อค่าใดค่าหนึ่งของaหรือbเป็นศูนย์ ตัวหารร่วมมาก (GCD) คือค่าสัมบูรณ์ของจำนวนเต็มที่ไม่เป็นศูนย์: gcd( a , 0) = gcd(0, a ) = | a |กรณีนี้มีความสำคัญเนื่องจากเป็นขั้นตอนสุดท้ายของ อัลกอริทึม ยุคลิด

นิยามข้างต้นไม่เหมาะสมสำหรับการกำหนดgcd(0, 0)เนื่องจากไม่มีจำนวนเต็มที่มากที่สุดnที่ทำให้0 × n = 0อย่างไรก็ตาม ศูนย์เป็นตัวหารที่มากที่สุดของตัวเอง หากเข้าใจคำว่ามากที่สุด ตามบริบทของความสัมพันธ์การหารลงตัว ดังนั้น gcd(0, 0)จึงมักถูกกำหนดให้เป็น0ซึ่งรักษาเอกลักษณ์ปกติของ GCD ไว้ โดยเฉพาะอย่างยิ่งเอกลักษณ์ของ Bézoutกล่าวคือgcd( a , b ) สร้างอุดมคติเดียวกันกับ{ a , b } [ ^{9 ] [ 10 ] [ 11 ] ระบบ พีชคณิต}คอมพิวเตอร์ หลายระบบ ปฏิบัติตามธรรมเนียมนี้^{[ 12 ]}อย่างไรก็ตาม ผู้เขียนบางคนไม่ได้กำหนดgcd(0, 0) ไว้ ^{[ 13 ]}

ตัวหารร่วมมาก (GCD) ของaและbคือตัวหารร่วมบวกที่มากที่สุด ใน ความสัมพันธ์การหาร แบบเรียง ลำดับก่อนหน้าซึ่งหมายความว่าตัวหารร่วมของaและbคือตัวหารของ GCD ของทั้งสองจำนวนนั้นพอดี โดยทั่วไปแล้วจะพิสูจน์ได้โดยใช้ทฤษฎีบทของยุคลิดทฤษฎีบทพื้นฐานทางเลขคณิตหรืออัลกอริทึมของยุคลิดนี่คือความหมายของคำว่า "มากที่สุด" ที่ใช้ในการขยายความแนวคิดของ GCD

เลข 54 สามารถเขียนให้เป็นผลคูณของจำนวนเต็มสองจำนวนได้หลายวิธี:

${\displaystyle 54\times 1=27\times 2=18\times 3=9\times 6.}$

ดังนั้น ตัวหาร ทั้งหมด ของ 54 คือ 1, 2, 3, 6, 9, 18, 27, 54 ในทำนองเดียวกัน ตัวหารของ 24 คือ 1, 2, 3, 4, 6, 8, 12, 24 ตัวเลขที่ตัวหารร่วมของทั้งสองรายการนี้มีเหมือนกันคือตัวหารร่วมของ 54 และ 24 นั่นคือ

${\displaystyle 1,2,3,6.}$

ในบรรดาตัวเลขเหล่านี้ ตัวที่มากที่สุดคือ 6 ดังนั้น 6 จึงเป็นตัวหารร่วมมากที่สุด :

${\displaystyle \gcd(54,24)=6.}$

การคำนวณหาตัวหารทั้งหมดของจำนวนทั้งสองด้วยวิธีนี้มักจะไม่มีประสิทธิภาพ โดยเฉพาะอย่างยิ่งสำหรับจำนวนมากที่มีตัวหารจำนวนมาก วิธีการที่มีประสิทธิภาพมากกว่านั้นได้อธิบายไว้ในหัวข้อ§  การคำนวณ

จำนวนสองจำนวนเรียกว่าเป็นจำนวนเฉพาะสัมพัทธ์ หรือจำนวนเฉพาะสัมพัทธ์ถ้าตัวหารร่วมมากที่สุดของจำนวนทั้งสองเท่ากับ1 [ ^{14 ] ตัวอย่าง}เช่น 9 และ 28 เป็นจำนวนเฉพาะสัมพัทธ์

ตัวอย่างเช่น พื้นที่สี่เหลี่ยมผืนผ้าขนาด 24 x 60 สามารถแบ่งออกเป็นตารางขนาด 1 x 1, 2 x 2, 3 x 3, 4 x 4, 6 x 6 หรือ 12 x 12 ได้ ดังนั้น 12 จึงเป็นตัวหารร่วมมากที่สุดของ 24 และ 60 พื้นที่สี่เหลี่ยมผืนผ้าขนาด 24 x 60 จึงสามารถแบ่งออกเป็นตารางขนาด 12 x 12 ได้ โดยมีช่องสี่เหลี่ยมสองช่องอยู่ด้านหนึ่ง ( 24/12 = 2 ) และช่องสี่เหลี่ยมห้าช่องอยู่ด้านตรงข้าม ( 60/12 = 5 )

ตัวหารร่วมมากมีประโยชน์สำหรับการลดเศษส่วนให้อยู่ในรูปอย่างง่ายที่สุด^{[ 15 ]}ตัวอย่างเช่นgcd(42, 56) = 14ดังนั้น

${\displaystyle {\frac {42}{56}}={\frac {3\cdot 14}{4\cdot 14}}={\frac {3}{4}}.}$

ตัวคูณร่วมน้อยที่สุดของจำนวนเต็มสองจำนวนที่ไม่ใช่ศูนย์ทั้งคู่ สามารถคำนวณได้จากตัวหารร่วมมากที่สุด โดยใช้ความสัมพันธ์ต่อไปนี้

${\displaystyle \operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}.}$

ตัวหารร่วมมากสามารถคำนวณได้โดยการหาตัวประกอบเฉพาะของจำนวนทั้งสองและเปรียบเทียบตัวประกอบ ตัวอย่างเช่น ในการคำนวณgcd(48, 180)เราหาตัวประกอบเฉพาะได้ 48 ^{= 2⁴ · 3¹ และ 180 = 2² · 3² · 5¹} ดังนั้น GCD คือ2min ( 4,2 ⁾ · ^3min ( 1,2 ) · ^{5min (} 0,1 ) ⁼ 2² · ^3¹ · ^5⁰ = 12 และ^LCMที่สอดคล้อง^กันคือ^{2max (4,2)} · 3max ^{( 1,2)} · 5max ^{( 0,1} ) = ^2⁴ · 3² · 5¹ = 720                          

ในทางปฏิบัติ วิธีนี้ใช้ได้ผลเฉพาะกับจำนวนน้อยๆ เท่านั้น เพราะการคำนวณการแยกตัวประกอบเฉพาะใช้เวลานานเกินไป

วิธีการที่ยูคลิด นำเสนอ สำหรับการคำนวณตัวหารร่วมมากนั้นอาศัยข้อเท็จจริงที่ว่า เมื่อกำหนดจำนวนเต็มบวกสองจำนวนคือaและbโดยที่a > bตัวหารร่วมของa และ b จะเหมือนกับตัวหารร่วมของa – bและb

ดังนั้น วิธีของยูคลิดในการคำนวณตัวหารร่วมมากที่สุดของจำนวนเต็มบวกสองจำนวน คือ การแทนที่จำนวนที่มากกว่าด้วยผลต่างของจำนวนทั้งสอง และทำซ้ำเช่นนี้ไปเรื่อยๆ จนกว่าจำนวนทั้งสองจะเท่ากัน นั่นคือตัวหารร่วมมากที่สุดของจำนวนทั้งสอง

ตัวอย่างเช่น ในการคำนวณgcd(48,18)จะดำเนินการดังนี้:

${\displaystyle {\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(48-18,18)=\gcd(30,18)\\&\to \quad \gcd(30-18,18)=\gcd(12,18)\\&\to \quad \gcd(12,18-12)=\gcd(12,6)\\&\to \quad \gcd(12-6,6)=\gcd(6,6).\end{aligned}}}$

ดังนั้นgcd(48, 18) = 6

วิธีนี้อาจช้ามากหากตัวเลขหนึ่งมีค่ามากกว่าอีกตัวเลขหนึ่งมาก ดังนั้นโดยทั่วไปจึงนิยมใช้วิธีต่อไปนี้มากกว่า

วิธีที่มีประสิทธิภาพมากกว่าคืออัลกอริทึมแบบยุคลิดซึ่งเป็นรูปแบบหนึ่งที่แทนที่ผลต่างของจำนวนสองจำนวนa และ b ด้วยเศษเหลือจากการหารแบบยุคลิด (เรียกอีกอย่างว่าการหารแบบมีเศษเหลือ ) ของaด้วยb

โดยกำหนดให้เศษเหลือนี้เป็นa mod bอัลกอริทึมจะแทนที่( a , b )ด้วย( b , a mod b )ซ้ำๆ จนกว่าคู่จะเป็น( d , 0)โดยที่dคือตัวหารร่วมมากที่สุด

ตัวอย่างเช่น ในการคำนวณ gcd(48,18) การคำนวณจะเป็นดังนี้:

${\displaystyle {\begin{aligned}\gcd(48,18)\quad &\to \quad \gcd(18,48{\bmod {1}}8)=\gcd(18,12)\\&\to \quad \gcd(12,18{\bmod {1}}2)=\gcd(12,6)\\&\to \quad \gcd(6,12{\bmod {6}})=\gcd(6,0).\end{aligned}}}$

ซึ่งจะได้gcd(48, 18) = 6อีก ครั้ง

อัลกอริทึมหาตัวหารร่วมมาก (GCD) แบบไบนารี เป็นรูปแบบหนึ่งของอัลกอริทึมของยูคลิด ซึ่งได้รับการดัดแปลงเป็นพิเศษให้เข้ากับการแสดงตัวเลขในระบบเลขฐานสอง ซึ่งเป็นระบบที่ใช้ในคอมพิวเตอร์ ส่วน ใหญ่

อัลกอริทึมหาตัวหารร่วมมาก (GCD) ในระบบเลขฐานสองแตกต่างจากอัลกอริทึมของยุคลิดโดยพื้นฐานแล้วคือการหารด้วยสองทุกครั้งที่พบจำนวนคู่ในระหว่างการคำนวณ ประสิทธิภาพของมันเกิดจากข้อเท็จจริงที่ว่า ในการแสดงผลเลขฐานสอง การตรวจสอบความเท่าเทียมกันประกอบด้วยการตรวจสอบตัวเลขหลักขวาสุด และการหารด้วยสองประกอบด้วยการลบตัวเลขหลักขวาสุดออก

วิธีการมีดังนี้ โดยเริ่มจาก aและbซึ่งเป็นจำนวนเต็มบวกสองจำนวนที่เราต้องการหาค่า ห.ร.ม.

1. ถ้าaและbเป็นจำนวนคู่ทั้งคู่ ให้หารทั้งสองด้วยสองไปเรื่อยๆ จนกว่าจะมีอย่างน้อยหนึ่งจำนวนกลายเป็นจำนวนคี่ ให้dเป็นจำนวนครั้งที่ทำการหารแบบจับคู่เช่นนี้
2. ถ้าaเป็นจำนวนคู่ ให้หารด้วยสองไปเรื่อยๆ จนกว่าจะได้จำนวนคี่
3. ถ้าbเป็นจำนวนคู่ ให้หารด้วยสองไปเรื่อยๆ จนกว่าจะได้จำนวนคี่

   ตอนนี้aและbต่างก็เป็นจำนวนคี่ และจะยังคงเป็นจำนวนคี่ไปจนกว่าการคำนวณจะสิ้นสุดลง

4. ในขณะที่a ≠ bทำ
   • ถ้าa > b ให้แทนค่า aด้วยa – bแล้วหารผลลัพธ์ด้วยสองไปเรื่อยๆ จนกว่าaจะเป็นจำนวนคี่ (เนื่องจากaและbเป็นจำนวนคี่ทั้งคู่ จึงมีการหารด้วย 2 อย่างน้อยหนึ่งครั้ง)
   • ถ้าa < bให้แทนbด้วยb – aแล้วหารผลลัพธ์ด้วยสองไปเรื่อยๆ จนกว่าbจะเป็นจำนวนคี่
5. ตอนนี้a = bและตัวหารร่วมมากที่สุดคือ${\displaystyle 2^{d}a.}$

ขั้นตอนที่ 1 กำหนดให้dเป็นกำลังสูงสุดของ2ที่หารaและb ลงตัว และด้วยเหตุนี้จึงเป็นตัวหารร่วมมากที่สุดของทั้งสอง ไม่มีขั้นตอนใดเปลี่ยนแปลงเซตของตัวหารร่วมคี่ของaและbซึ่งแสดงให้เห็นว่าเมื่ออัลกอริทึมหยุดทำงาน ผลลัพธ์จะถูกต้อง อัลกอริทึมจะหยุดทำงานในที่สุด เนื่องจากแต่ละขั้นตอนจะหารตัวถูกดำเนินการอย่างน้อยหนึ่งตัวด้วย2 อย่างน้อยที่สุด ยิ่งไปกว่านั้น จำนวนการหารด้วย2และจำนวนการลบจึงมีค่าสูงสุดเท่ากับจำนวนหลักทั้งหมด

ตัวอย่าง: ( a , b , d ) = (48, 18, 0) → (24, 9, 1) → (12, 9, 1) → (6, 9, 1) → (3, 9, 1) → (3, 3, 1)  ; ตัวหารร่วมมากดั้งเดิมจึงเป็นผลคูณ 6 ของ2 ^d = 2 ¹และa = b = 3

อัลกอริทึมหาตัวหารร่วมมาก (GCD) แบบไบนารีนั้นง่ายต่อการใช้งานเป็นพิเศษและมีประสิทธิภาพมากเป็นพิเศษบนคอมพิวเตอร์ไบนารีความซับซ้อนในการคำนวณ ของมัน คือ

${\displaystyle O((\log a+\log b)^{2}).}$

ความซับซ้อนที่เป็นจำนวนกำลังสองนี้ มาจากข้อเท็จจริงที่ว่า การหารด้วย2และการลบใช้เวลาแปรผันตรงกับจำนวนบิตของข้อมูลป้อนเข้า

ความซับซ้อนในการคำนวณมักจะแสดงในรูปของความยาวnของข้อมูลนำเข้า ในที่นี้ ความยาวคือn = log a + log bและความซับซ้อนจึงเป็นดังนี้

${\displaystyle O(n^{2})}$.

อัลกอริทึมของเลห์เมอร์นั้นอิงจากการสังเกตว่า ผลหารเริ่มต้นที่ได้จากอัลกอริทึมของยูคลิดนั้น สามารถกำหนดได้จากตัวเลขเพียงไม่กี่หลักแรกเท่านั้น ซึ่งมีประโยชน์สำหรับตัวเลขที่มีขนาดใหญ่กว่าคำในคอมพิวเตอร์โดยหลักการแล้ว เราจะดึงตัวเลขหลักแรกออกมา ซึ่งโดยทั่วไปแล้วจะประกอบเป็นคำในคอมพิวเตอร์หนึ่งหรือสองคำ แล้วนำอัลกอริทึมของยูคลิดไปใช้กับตัวเลขที่มีขนาดเล็กกว่าเหล่านี้ ตราบใดที่รับประกันได้ว่าผลหารที่ได้จะเหมือนกับผลหารที่จะได้จากตัวเลขเดิม ผลหารเหล่านั้นจะถูกรวบรวมไว้ในเมทริกซ์การแปลงขนาดเล็ก 2x2 (เมทริกซ์ของจำนวนเต็มคำเดียว) เพื่อลดขนาดตัวเลขเดิม กระบวนการนี้จะทำซ้ำไปเรื่อยๆ จนกว่าตัวเลขจะมีขนาดเล็กพอที่อัลกอริทึมแบบไบนารี (ดูด้านล่าง) จะมีประสิทธิภาพมากกว่า

อัลกอริทึมนี้ช่วยเพิ่มความเร็ว เนื่องจากลดจำนวนการคำนวณกับจำนวนขนาดใหญ่มาก และสามารถใช้การคำนวณทางฮาร์ดแวร์สำหรับการคำนวณส่วนใหญ่ได้ ที่จริงแล้ว ผลหารส่วนใหญ่มีขนาดเล็กมาก ดังนั้นจึงสามารถรวบรวมขั้นตอนจำนวนมากของอัลกอริทึมแบบยุคลิดไว้ในเมทริกซ์ 2x2 ของจำนวนเต็มแบบคำเดียวได้ เมื่ออัลกอริทึมของเลห์เมอร์พบผลหารที่มีขนาดใหญ่เกินไป มันจะต้องย้อนกลับไปใช้การวนซ้ำของอัลกอริทึมแบบยุคลิดหนึ่งรอบ โดยใช้การหาร แบบยุคลิดกับ จำนวนขนาดใหญ่

ถ้าaและbทั้งคู่ไม่ใช่ศูนย์ ตัวหารร่วมมากของaและbสามารถคำนวณได้โดยใช้ตัวคูณร่วมที่น้อยที่สุด (LCM) ของaและb : 

${\displaystyle \gcd(a,b)={\frac {|a\cdot b|}{\operatorname {lcm} (a,b)}}}$,

แต่โดยทั่วไปแล้ว ตัวคูณร่วมที่น้อยที่สุด (LCM) จะคำนวณจากตัวหารร่วมมาก (GCD)

โดยใช้ ฟังก์ชัน fของ Thomae

${\displaystyle \gcd(a,b)=af\left({\frac {b}{a}}\right),}$

ซึ่งสามารถขยายไปสู่จำนวนตรรกยะaและb หรือจำนวนจริงที่เทียบเคียงกันได้

Keith Slavin ได้แสดงให้เห็นว่าสำหรับค่าคี่a ≥ 1 :

${\displaystyle \gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})}$

ซึ่งเป็นฟังก์ชันที่สามารถประเมินค่าสำหรับb ที่ซับซ้อน ได้^{[ 16 ]} Wolfgang Schramm ได้แสดงให้เห็นว่า

${\displaystyle \gcd(a,b)=\sum \limits _{k=1}^{a}\exp(2\pi ikb/a)\cdot \sum \limits _{d\left|a\right.}{\frac {c_{d}(k)}{d}}}$

เป็นฟังก์ชันทั้งหมดในตัวแปรbสำหรับจำนวนเต็มบวกทั้งหมดaโดยที่c ( k ) คือ ผลรวม ของRamanujan ^{[ 17 ]}

ความซับซ้อนในการคำนวณของการหาตัวหารร่วมมากได้รับการศึกษาอย่างกว้างขวาง^{[ 18 ]}หากใช้ขั้นตอนวิธีแบบยุคลิด และขั้นตอนวิธีพื้นฐานสำหรับการคูณและการหาร การ คำนวณตัวหารร่วมมากของจำนวนเต็มสองจำนวนที่มีบิตไม่เกินn บิตจะเป็นO ( n ² )ซึ่งหมายความว่าการคำนวณตัวหารร่วมมากมีความซับซ้อนเท่ากับการคูณ โดยมีค่าคงที่เป็นปัจจัย

อย่างไรก็ตาม หากใช้อัลกอริทึมการคูณ ที่รวดเร็ว เราอาจปรับเปลี่ยนอัลกอริทึมแบบยุคลิดเพื่อปรับปรุงความซับซ้อนได้ แต่การคำนวณตัวหารร่วมมากจะช้ากว่าการคูณ กล่าวคือ หากการคูณจำนวนเต็มสองจำนวนที่มี nบิตใช้เวลาT ( n )อัลกอริทึมที่เร็วที่สุดที่รู้จักสำหรับการหาตัวหารร่วมมากจะมีความซับซ้อนO ( T ( n ) log n ) ซึ่งหมายความว่าอั ลกอริทึมที่เร็วที่สุดที่รู้จักมีความซับซ้อนO ( n (log n ) ^² )

ความซับซ้อนที่กล่าวมาข้างต้นนั้นใช้ได้กับแบบจำลองการคำนวณ ทั่วไป โดยเฉพาะอย่างยิ่งเครื่องจักรทัวริงแบบหลายเทปและเครื่องจักรแบบเข้าถึงแบบสุ่ม

การคำนวณตัวหารร่วมมากจัดอยู่ในกลุ่มปัญหาที่สามารถแก้ไขได้ในเวลากึ่งเชิงเส้น ยิ่งไปกว่านั้นปัญหาการตัดสินใจที่สอดคล้องกันจัดอยู่ในกลุ่มPของปัญหาที่สามารถแก้ไขได้ในเวลาพหุนาม ปัญหา GCD ไม่เป็นที่ทราบกันว่าอยู่ในNCดังนั้นจึงไม่มีวิธีใดที่ทราบกันว่าสามารถทำให้ขนานกันได้อย่างมีประสิทธิภาพ และยังไม่เป็นที่ทราบกันว่าเป็นP-completeซึ่งหมายความว่าไม่น่าจะเป็นไปได้ที่จะทำให้การคำนวณ GCD ขนานกันได้อย่างมีประสิทธิภาพ Shallcross และคณะแสดงให้เห็นว่าปัญหาที่เกี่ยวข้อง (EUGCD การกำหนดลำดับเศษเหลือที่เกิดขึ้นระหว่างอัลกอริทึมยุคลิด) เทียบเท่ากับ NC ของปัญหาการเขียนโปรแกรมเชิงเส้นจำนวนเต็มที่มีสองตัวแปร หากปัญหาใดปัญหาหนึ่งอยู่ในNCหรือเป็นP-completeอีกปัญหาหนึ่งก็จะเป็นเช่นนั้นด้วย^{[ 19 ]}เนื่องจากNCประกอบด้วยNLจึงไม่ทราบว่ามีอัลกอริทึมที่มีประสิทธิภาพด้านพื้นที่สำหรับการคำนวณ GCD หรือไม่ แม้แต่สำหรับเครื่องจักรทัวริงแบบไม่กำหนด

แม้ว่าปัญหาจะไม่เป็นที่ทราบในNCแต่ก็มีอัลกอริทึมแบบขนานที่เร็วกว่าอัลกอริทึมแบบยุคลิดในเชิงอะซิมโทติก อัลกอริทึมแบบกำหนดที่เร็วที่สุดที่ทราบคือของChorและGoldreichซึ่ง (ใน แบบจำลอง CRCW-PRAM ) สามารถแก้ปัญหาได้ใน เวลา O ( n /log n )ด้วยโปรเซสเซอร์n ^{1+ ε [ 20 ]}อัลกอริทึมแบบสุ่มสามารถแก้ปัญหาได้ใน เวลา O ((log n ) ² )บน${\displaystyle O\left(e^{\sqrt {n\log n}}\right)}$โปรเซสเซอร์ (นี่คือซูเปอร์พหุนาม ) ^{[ 21 ]}