ขั้นตอนวิธีแบบยุคลิด

บทความนี้อ้างอิงคริสต์ศักราช/คริสต์ทศวรรษ/คริสต์ศตวรรษ ซึ่งเป็นสาระสำคัญของเนื้อหา

ตัวหารร่วมมากของจำนวนเต็มสองจำนวนคือจำนวนเต็มมากที่สุดที่หารทั้งสองจำนวนนั้นได้โดยไม่เหลือเศษ

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

หลักการสำคัญคือ หรม. ไม่เปลี่ยนค่าถ้านำจำนวนที่น้อยกว่าลบจำนวนที่มากกว่า เช่น หรม. ของ 252 และ 105 เท่ากับ หรม. ของ 147 (= 252 − 105) และ 105 จำนวนที่มากกว่าถูกลดลดค่าลงเสมอ ทำให้การทำวิธีนี้ซ้ำได้จำนวนที่เล็กลง การซ้ำนี้จึงจบอย่างแน่นอนเมื่อทั้งสองจำนวนมีค่าเท่ากัน (ถ้าทำอีกหนึ่งครั้ง จำนวนใดจำนวนหนึ่งจะเป็น 0)

หลักฐานเกี่ยวกับขั้นตอนวิธีแบบยุคลิดพบในหนังสือ Elements ของยุคลิด (ในช่วงศตวรรษที่ 3 ก่อนคริสตกาล) ทำให้เป็นขั้นตอนวิธีเก่าแก่ที่สุดเกี่ยวกับจำนวนที่ยังใช้โดยทั่วไป ขั้นตอนวิธีฉบับดังเดิมใช้สำหรับจำนวนธรรมชาติและความยาวเชิงเรขาคณิต (จำนวนจริง) แต่นักคณิตศาสตร์ได้ขยายการใช้งานไปยังจำนวนชนิดอื่น เช่น จำนวนเต็มเกาส์เซียนและพหุนามหนึ่งตัวแปร อันนำไปสู่แนวคิดเชิงพีชคณิตนามธรรมสมัยใหม่ เช่นโดเมนแบบยุคลิด ซึ่งเป็นริงที่สามารถทำขั้นตอนวิธีของยุคลิดได้

ขั้นตอนวิธีของยุคลิดมีการประยุกต์ใช้ในทางทฤษฎีและปฏิบัติ อาจใช้ก่อกำเนิดจังหวะดนตรีที่สำคัญหลายรูปแบบที่พบในวัฒนธรรมต่างๆ ทั่วโลก ขั้นตอนวิธีนี้เป็นส่วนประกอบสำคัญของการเข้ารหัสอาร์เอสเอ (การเข้ารหัสลับแบบกุญแจอสมมาตรที่ใช้ทั่วไปในการพาณิชย์อิเล็กทรอนิกส์) ขั้นตอนวิธีแบบยุคลิดใช้แก้สมการไดโอแฟนไทน์แบบรูปแบบ เช่นการหาจำนวนที่สอดคล้องกับสมภาคหลายชุด (ทฤษฎีบทเศษเหลือของจีน) หรือตัวผกผันการคูณในฟิลด์จำกัด, ใช้สร้างเศษส่วนต่อเนื่อง, ใช้หาจำนวนรากจริงของพหุนามโดยวิธีโซ่ของสเติร์ม และในขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มสมัยใหม่ และที่สำคัญ ขั้นตอนวิธีของยุคลิดเป็นเครื่องมือสำหรับพิสูจน์ทฤษฎีบทในทฤษฎีจำนวน เช่น ทฤษฎีบทผลรวมกำลังสองของลากรองจ์และทฤษฎีบทมูลฐานของเลขคณิต

ถ้าปรับปรุงขั้นตอนวิธีให้ใช้เศษหารจากวิธีหารแบบยุคลิดแทนที่จะเป็นการลบ ขั้นตอนวิธีของยุคลิดคำนวณค่าตัวหารร่วมมากของจำนวนขนาดใหญ่อย่างมีประสิทธิภาพ โดยใช้ขั้นตอนวิธีการหารเป็นจำนวนครั้งไม่เกินห้าเท่าของจำนวนหลักของจำนวนขนาดเล็กกว่า (ในฐานสิบ) ขั้นตอนวิธีแบบปรับปรุงนี้พิสูจน์ได้โดย Gabriel Lamé [en] เมื่อปี ค.ศ. 1844 นับเป็นจุดริเริ่มการศึกษาทฤษฎีความซับซ้อนในการคำนวณ และในคริสต์ศตวรรษที่ 20 มีการพัฒนาวิธีเพิ่มประสิทธิภาพในรูปแบบอื่นเพิ่มขึ้นมา

เมื่อย้อนขั้นตอนวิธีแบบยุคลิด ตัวหารร่วมมากสามารถเขียนในรูปผลรวมเชิงเส้นของสองจำนวนที่นำมาดำเนินการ โดยที่แต่ละจำนวนคูณกับจำนวนเต็ม เช่น ตัวหารร่วมมากของ 252 และ 105 คือ 21 และ 21 = [5 × 105] + [(−2) × 252] สมบัตินี้เรียกว่าเอกลักษณ์ของเบซู

ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของจำนวนธรรมชาติสองจำนวน a และ b ค่าตัวหารร่วมมาก g เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง a และ b ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ ตัวประกอบร่วมค่ามากสุด (อังกฤษ: greatest common factor, GCF), ตัวประกอบร่วมค่ามากสุด (อังกฤษ: highest common factor, HCF) และ greatest common measure (GCM) ตัวหารร่วมมากมักเขียนแทนด้วย gcd(a, b) หรือ (a, b), แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ

ถ้า gcd(a, b) = 1 แล้ว a กับ b เป็นจำนวนเฉพาะสัมพัทธ์ ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า a หรือ b เป็นจำนวนเฉพาะเองแต่อย่างใด เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6 = 2 × 3 and 35 = 5 × 7 อย่างไรก็ตาม 6 และ 35 เป็นจำนวนเฉพาะสัมพัทธ์ ไม่มีจำนวนธรรมชาตินอกเหนือจาก 1 หารทั้ง 6 และ 35 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน

 

ให้ g = gcd(a, b) จากการที่ a และ b เป็นพหุคูณของ g สามารถเขียนในรูป a = mg และ b = ng และไม่มีจำนวนเต็ม G ที่มากกว่า g ที่ทำให้ข้อความดังกล่าวเป็นจริง m และ n ต้องเป็นจำนวนเฉพาะสัมพัทธ์ เพราะหากมีตัวประกอบร่วมของ m และ n จะทำให้ g มีค่ามากขึ้น ดังนั้นจำนวนเต็ม c ใด ๆ ที่หาร a และ b ลงตัว จะต้องหาร g ลงตัวด้วย ตัวหารร่วมมาก g ของ a และ b คือตัวหารร่วมบวกเพียงหนึ่งตัวของ a และ b ที่หารด้วยตัวหารร่วมอื่น c ลงตัว

ตัวหารร่วมมากสามารถอธิบายได้ด้วยการสมมติสี่เหลี่ยมผืนผ้ากว้าง a ยาว b และตัวหารร่วม c ที่หาร a และ b ลงตัว ด้านของสี่เหลี่ยมสามารถแบ่งเป็นส่วนย่อยยาว c ซึ่งแบ่งสี่เหลี่ยมผืนผ้าเป็นตารางสี่เหลี่ยมจัตุรัสย่อยยาวด้านละ c โดยตัวหารร่วมมาก g คือค่าที่มากที่สุดที่เป็นไปได้ของ c ตัวอย่างดังภาพคือสี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 สามารถแบ่งได้เป็นตารางของสี่เหลี่ยมจัตุรัส 1 ${\displaystyle \times }$  1, สี่เหลี่ยมจัตุรัส 2 ${\displaystyle \times }$  2, สี่เหลี่ยมจัตุรัส 3 ${\displaystyle \times }$  3, สี่เหลี่ยมจัตุรัส 4 ${\displaystyle \times }$  4, สี่เหลี่ยมจัตุรัส 6${\displaystyle \times }$ 6 หรือสี่เหลี่ยมจัตุรัส 12 ${\displaystyle \times }$  12 ดังนั้น 12 คือตัวหารร่วมมากของ 24 และ 60 โดยสี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 สามารถแบ่งเป็นตารางของสี่เหลี่ยมจัตุรัสยาวด้านละ 12 ที่มีสี่เหลี่ยมจัตุรัส 2 รูปติดด้านกว้าง (24/12 = 2) และสี่เหลี่ยมจัตุรัส 5 รูปติดด้านยาว (60/12 = 5)

ตัวหารร่วมมากของสองจำนวน a และ b คือผลคูณของตัวประกอบเฉพาะที่สองจำนวนนี้มีร่วมกัน โดยตัวประกอบเฉพาะหนึ่งค่าสามารถนำมาคูณได้หลายรอบ ตราบที่ผลคูณของตัวประกอบเหล่านี้หาร a และ b ลงตัว ตัวอย่างเช่น 1386 แยกตัวประกอบได้เป็น 2 ${\displaystyle \times }$  3 ${\displaystyle \times }$  3 ${\displaystyle \times }$  7 ${\displaystyle \times }$  11 และ 3213 แยกตัวประกอบได้เป็น 3 ${\displaystyle \times }$  3 ${\displaystyle \times }$  3 ${\displaystyle \times }$  7 ${\displaystyle \times }$  17 ตัวหารร่วมมากของ 1386 และ 3213 จึงเท่ากับ 63 = 3 ${\displaystyle \times }$  3 ${\displaystyle \times }$  7 ซึ่งก็คือผลคูณของตัวประกอบเฉพาะร่วม ถ้าสองจำนวนไม่มีตัวประกอบเฉพาะร่วมกัน ตัวหารร่วมมากคือ 1 (เท่ากับค่าผลคูณว่าง) หรือก็คือทั้งสองจำนวนนั้นเป็นจำนวนเฉพาะสัมพัทธ์ ข้อได้เปรียบของขั้นตอนวิธีแบบยุคลิดคือสามารถหาค่าตัวหารร่วมมากโดยไม่ต้องหาตัวประกอบเฉพาะร่วม

หรม. ของสามจำนวนขึ้นไปมีค่าเท่ากับผลคูณของตัวประกอบเฉพาะของจำนวนเหล่านั้น แต่ก็สามารถหาได้จากการหา หรม. ของแต่ละคู่จำนวน

gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)

ดังนั้นขั้นตอนวิธีแบบยูคลิดที่หาหรม.ของสองจำนวนจะสามารถหาหรม.ของหลายจำนวนได้ด้วยเช่นกัน

กระบวนการ

ขั้นตอนวิธีแบบยูคลิดดำเนินเป็นขั้นตอน โดยผลลัพธ์ในแต่ละขั้นตอนจะถูกใช้ในขั้นตอนต่อไป ให้ k เป็นจำนวนเต็มที่นับจำนวนขั้นตอนในวิธีการยูคลิด เริ่มจากศูนย์ ดังนั้นในขั้นตอนที่หนึ่งมีค่า k = 0 ขั้นตอนที่สองมีค่า k = 1 เป็นแบบนี้ไปเรื่อย ๆ

แต่ละขั้นตอนเริ่มด้วยเศษสองจำนวนที่มีค่าไม่เป็นลบ r_k−1 และ r_k−2 เนื่องจากวิธีการนี้จะทำให้เศษมีค่าลดลงในทุกขั้นตอนเสมอ r_k−1 มีค่าน้อยกว่าเศษตัวก่อน r_k−2 เป้าหมายของขั้นตอนที่ k คือหาผลหาร q_k และเศษ r_k ที่สอดคล้องกับสมการ

${\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k}}$ 

จะได้ว่า 0 ≤ r_k < r_k−1 กล่าวได้ว่า จำนวนที่มากกว่า r_k−2 ถูกลบด้วยพหุคูณของจำนวนที่น้อยกว่า r_k−1 จนกว่าเศษ r_k จะมีค่าน้อยกว่า r_k−1

ในขั้นแรก (k = 0) เศษ r₋₂ และ r₋₁ มีค่าเท่ากับ a และ b ตามลำดับ ในขั้นต่อมา (k = 1) เศษมีค่าเท่ากับ b และเศษ r₀ ของขั้นแรก ทำแบบนี้ต่อไปเรื่อย ๆ ขั้นตอนวิธีดังกล่าวเขียนออกมาในรูปแบบลำดับของสมการได้ว่า

${\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\r_{0}&=q_{2}r_{1}+r_{2}\\r_{1}&=q_{3}r_{2}+r_{3}\\&\,\,\,\vdots \end{aligned}}}$ 

ถ้า a มีค่าน้อยกว่า b ให้สลับตัวเลขในขั้นแรก ตัวอย่างคือ ถ้า a < b ผลหารในขั้นแรก q₀ จะมีค่าเท่ากับศูนย์ และเศษ r₀ มีค่าเท่ากับ a ดังนั้น r_k จะมีค่าน้อยกว่า r_k−1 สำหรับทุก k ≥ 0

เพราะเศษมีค่าลดลงในทุกขั้นตอน แต่ไม่สามารถเป็นมีค่าเป็นลบ เศษ r_N จึงจะต้องเท่ากับศูนย์ในสักขั้นตอน

การพิสูจน์ความถูกต้อง

ความถูกต้องของขั้นตอนวิธีแบบยูคลิดสามารถพิสูจน์ได้โดยสองขั้นตอน ในขั้นตอนแรก เห็นได้ว่าเศษตัวสุดท้ายที่ไม่เท่ากับศูนย์ r_N−1 จะหารทั้ง a และ b ลงตัว เพราะมันเป็นตัวหารร่วม จึงมีค่าน้อยกว่าหรือเท่ากับตัวหารร่วมมาก g และในขั้นตอนที่สอง เห็นได้ว่าตัวหารร่วมใด ๆ ของ a และ b (รวมถึงตัวหารร่วมมาก g ด้วย) ต้องหาร r_N−1 ลงตัว ดังนั้น g ต้องมีค่าน้อยกว่าหรือเท่ากับ r_N−1 ข้อสรุปสองอันนี้ไม่แน่นอน เว้นแต่ r_N−1 = g

เพื่อแสดงให้เห็นว่า r_N−1 หารทั้ง a และ b ลงตัว (ขั้นแรก) และ r_N−1 หาร r_N−2 ลงตัว

r_N−2 = q_N r_N−1

เพราะเศษตัวสุดท้าย r_N คือศูนย์ ทำให้ r_N−1 หาร r_N−3 ลงตัวด้วย

r_N−3 = q_N−1 r_N−2 + r_N−1

g = gcd(a, b) = gcd(b, r₀) = gcd(r₀, r₁) = … = gcd(r_N−2, r_N−1) = r_N−1.

ตัวอย่างการใช้งาน

 

เพื่อให้เห็นภาพ ขั้นตอนวิธีแบบยุคลิดสามารถนำมาใช้หาตัวหารร่วมมากของ a = 1071 และ b = 462 ได้ เริ่มต้นด้วย นำ 1071 เป็นตัวตั้ง ลบกับตัวคูณของ 462 จนกว่าเศษจะน้อยกว่า 462 ซึ่งเมื่อพิจารณาแล้ว การคูณด้วย 2 นั้นสามารถนำมาใช้ในการลบออกได้ (q₀ = 2) โดยมีเศษคือ 147

1071 = 2 × 462 + 147.

ต่อมา ตัวคูณของ 147 จะถูกลบออกจาก 462 จนกว่าเศษจะมีค่าน้อยกว่า 147 เมื่อพิจารณาแล้ว การคูณด้วย 3 นั้นสามารถนำมาใช้ในการลบออกได้

462 = 3 × 147 + 21.

ต่อมา ตัวคูณของ 21 จะถูกลบออกจาก 147 จนกว่าเศษจะมีค่าน้อยกว่า 21 ซึ่งการคูณด้วย 7 นั้นสามารถนำมาใช้ในการลบออกได้ (q₂ = 7) ไม่เหลือเศษแล้ว

147 = 7 × 21 + 0.

การอธิบายเป็นภาพ

เราสามารถทำขั้นตอนวิธีแบบยูคลิดให้เห็นภาพได้ โดยใช้วิธีคล้ายกับการปูกระเบื้องในการหาตัวหารร่วมมาก สมมุติว่าเราต้องการปูพื้นที่สี่เหลี่ยมผืนผ้าขนาด ${\displaystyle a\times b}$  โดยใช้กระเบื้องสี่เหลี่ยมจัตุรัส โดยที่ a เป็นค่าที่มีค่ามากกว่าอีกจำนวน เริ่มแรก เราจะปูโดยใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด ${\displaystyle b\times b}$  แต่ว่า กลับเหลือพื้นที่ที่ปูไม่ได้ มีขนาดเป็น ${\displaystyle r_{0}\times b}$  โดยที่ ${\displaystyle r_{0}$  เราก็เลยเปลี่ยนไปใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด ${\displaystyle r_{0}\times r_{0}}$  แทน แต่ก็ยังปูพื้นที่ได้ไม่ครบอีก เหลือพื้นที่เป็น ${\displaystyle r_{1}\times r_{0}}$  เราก็เลยเปลี่ยนไปใช้กระเบื้องขนาด ${\displaystyle r_{1}\times r_{1}}$  แทน ทำแบบนี้ซ้ำไปเรื่อย ๆ จนกระทั่งไม่เหลือพื้นที่ที่ยังไม่ได้ปู นั่นคือ เมื่อกระเบื้องสี่เหลียมจัตุรัสสามารถปูพื้นที่ที่ยังไม่ได้ปูในขั้นที่แล้วได้ทั้งหมด โดยความยาวของด้านของสี่เหลี่ยมจัตุรัสที่เล็กที่สุดก็คือตัว ห.ร.ม. ของขนาดของสี่เหลี่ยมรูปต้นแบบนั่นเอง เช่น กระเบื้องสี่เหลี่ยมจัตุรัสขนาดเล็กที่สุดในรูปคือ ${\displaystyle 21\times 21}$  (ในรูปแสดงโดยใช้สีแดง) และ 21 เป็นตัวหารร่วมมากของ 1071 และ 462 ซึ่งเป็นรูปสี่เหลี่ยมต้นฉบับ (แสดงโดยใช้สีเขียว)

การหารแบบยูคลิด

ในทุกขั้นตอน k ขั้นตอนวิธีแบบยุคลิดคำนวณผลหาร q_k และเศษ r_k จากตัวเลขสองตัว r_k−1 และ r_k−2

r_k−2 = q_k r_k−1 + r_k

โดยที่ r_k เป็นจำนวนเต็มที่ไม่เป็นลบ และมีค่าน้อยกว่าค่าสัมบูรณ์ของ r_k−1 โดยมีทฤษฏีที่รับรองว่าขั้นตอนวิธีแบบยุคลิดจะมีผลหารและเศษเสมอ

ในขั้นตอนวิธีแบบยุคลิดแบบดั้งเดิม ผลหารและเศษหาได้จากการลบซ้ำ ๆ นั่นคือ

r_k = r_k−2 mod r_k−1.

การนำไปใช้งาน

การนำไปใช้งานของขั้นตอนวิธีแบบยูคลิดจะถูกเขียนในรูปแบบโค้ดเทียม

function gcd(a, b)     while b ≠ 0         t := b         b := a mod b         a := t     return a 

function gcd(a, b)     while a ≠ b          if a > b             a := a − b         else             b := b − a     return a 

ในรูปแบบเรียกซ้ำ จะขึ้นอยู่กับความเท่ากันของตัวหารร่วมมากของเศษเหลือต่อเนื่อง โดยมีเงื่อนไขการหยุดคือ gcd(r_N−1, 0) = r_N−1

function gcd(a, b)     if b = 0         return a     else         return gcd(b, a mod b) 

(หากค่าที่รับมาเป็นลบ หรือฟังก์ชัน mod อาจให้ค่าที่ติดลบ ต้องเปลี่ยน "return a" เป็น "return max(a, −a)")

 

ขั้นตอนวิธีแบบยุคลิดเป็นหนึ่งในขั้นตอนวิธีที่เก่าแก่ที่สุดที่ใช้กันอย่างแพร่หลาย ซึ่งปรากฏในหนังสือเอเลเมนส์ของยุคลิด [en] (300 ปีก่อนคริสต์ศักราช) โดยเฉพาะในหนังสือเล่มที่ 7 (ประพจน์ที่ 1-2) และในหนังสือเล่มที่ 10 (ประพจน์ที่ 2-3) ในหนังสือเล่มที่ 7 ขั้นตอนวิธีถูกสร้างขึ้นเพื่อใช้กับจำนวนเต็ม แต่ในหนังสือเล่มที่ 10 ได้นำไปใช้กับความยาวส่วนของเส้นตรง (ในการใช้สมัยใหม่นี้ อาจพูดได้ว่ามันถูกสร้างขึ้นเพื่อใช้กับจำนวนจริง แต่ในอดีต ความยาว พื้นที่ และปริมาตร ซึ่งนับว่าเป็นจำนวนจริงในปัจจุบัน ไม่ได้ถูกวัดด้วยหน่วยเดียวกันและไม่ได้มีหน่วยธรรมชาติเป็นของตนเอง อาจกล่าวได้ว่าแนวคิดเกี่ยวกับจำนวนจริงไม่เป็นที่รู้จักในขณะนั้น) ขั้นตอนวิธีถัดมานั้นเกี่ยวกับเรขาคณิต ห. ร. ม. ของความยาว a และ b สอดคล้องกับความยาวที่มากที่สุด g ซึ่งวัด a และ b กล่าวคือ ความยาว a และ b ทั้งคู่ต่างก็เป็นพหุคูณของความยาว g

ขั้นตอนวิธีนี้อาจไม่ได้ถูกคิดค้นโดยยุคลิด ผู้ซึ่งรวบรวมผลลัพธ์จากนักคณิตศาสตร์ในหนังสือ เอเลเมนส์ ของเขา นักคณิตศาสตร์และประวัติศาสตร์ B. L. van der Waerden [en] ได้เสนอแนะว่า เนื้อหาในหนังสือเล่มที่ 7 ได้รับมาจากตำราเรียนเกี่ยวกับทฤษฎีจำนวน ซึ่งเขียนโดยนักคณิตศาสตร์ในโรงเรียนของพีทาโกรัส ขั้นตอนวิธีอาจเป็นที่รู้จักจาก Eudoxus of Cnidus [en] (ราว 375 ปีก่อนคริสต์ศักราช) ขั้นตอนวิธีนี้อาจเกิดขึ้นก่อน Eudoxus พิจารณาจากการใช้ศัพท์เฉพาะ ἀνθυφαίρεσις (anthyphairesis หรือการลบส่วนกลับ) ในงานของยุคลิดและแอริสตอเติล

หลายศตวรรษต่อมา ขั้นตอนวิธีของยุคลิดถูกค้นพบทั้งในประเทศอินเดียและจีน โดยแรกเริ่มเพื่อแก้ปัญหาสมการไดโอแฟนไทน์ [en] ซึ่งเกิดขึ้นในดาราศาสตร์และทำให้สามารถสร้างปฏิทินที่แม่นยำ ในช่วงท้ายศตวรรษที่ 5 นักคณิตศาสตร์และดาราศาสตร์ชาวอินเดีย อารยภัฏ ได้อธิบายขั้นตอนวิธีว่าเป็น "เครื่องบด" ซึ่งอาจมาจากประสิทธิภาพของมันในการแก้ปัญหาสมการไดโอแฟนไทน์ ถึงแม้ว่ากรณีพิเศษของทฤษฎีบทเศษเหลือของจีน [en] จะถูกอธิบายในหนังสือจีนชื่อ ซุนซีสวนจิ้ง [en] โดยผลเฉลยทั่วไปถูกเผยแพร่โดย Qin Jiushao [en] ในหนังสือของเขาชื่อ Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections [en]) ขั้นตอนวิธีแบบยุคลิดถูกอธิบายในเชิงตัวเลขครั้งแรกและเป็นที่รู้จักอย่างมากในยุโรปในหนังสือ Problèmes plaisants et délectables ฉบับที่ 2 ของ Bachet [en] (Pleasant and enjoyable problems, 1624) ในยุโรป ขั้นตอนวิธีแบบยุคลิดถูกใช้เพื่อแก้ปัญหาสมการไดโอแฟนไทน์และใช้เพื่อพัฒนาเศษส่วนต่อเนื่อง ขั้นตอนวิธีแบบยุคลิดแบบขยาย [en] ถูกตีพิมพ์โดยนักคณิตศาสตร์ชาวอังกฤษชื่อ นิโคลัส ซอนเดอร์ซัน [en] ซึ่งเชื่อว่ามันเกิดมาจาก โรเจอร์ โคตส์ [en] เพื่อเป็นวิธีสำหรับคำนวณเศษส่วนต่อเนื่องอย่างมีประสิทธิภาพ

ในศตวรรษที่ 19 ขั้นตอนวิธีแบบยุคลิดนำไปสู่การพัฒนาระบบจำนวนแบบใหม่ เช่น จำนวนเต็มเกาส์เซียน [en] และจำนวนเต็มไอเซนสไตน์ [en] ในปี 1815 คาร์ล ฟรีดริช เกาส์ได้ใช้ขั้นตอนวิธีแบบยุคลิดในการสาธิตการแยกตัวประกอบได้อย่างเดียวในจำนวนเต็มเกาส์เซียน [en] ถึงแม้ผลงานของเขาจะได้ตีพิมพ์ครั้งแรกในปี 1832 ก็ตาม เกาส์ได้พูดถึงขั้นตอนวิธีในหนังสือ Disquisitiones Arithmeticae [en] ของเขา (ถูกตีพิมพ์ในปี 1801) แต่ใช้เป็นเพียงวิธีสำหรับเศษส่วนต่อเนื่อง Peter Gustav Lejeune Dirichlet [en] เป็นคนแรกที่อธิบายขั้นตอนวิธีแบบยุคลิดเพื่อเป็นพื้นฐานสำหรับทฤษฏีจำนวนอื่น ๆ Lejeune Dirichlet ได้ระบุว่าผลลัพธ์ของทฤษฎีจำนวนหลายอัน เช่น การแยกตัวประกอบได้อย่างเดียว (Unique factorization) จะเป็นจริงสำหรับระบบจำนวนใด ๆ ที่สามารถใช้ขั้นตอนวิธีแบบยุคลิดได้ การบรรยายของ Lejeune Dirichlet ในหัวข้อทฤษฎีจำนวนถูกแก้ไขและต่อเติมโดย Richard Dedekind [en] ผู้ใช้ขั้นตอนวิธีของยุคลิดในการศึกษาจำนวนเชิงพีชคณิต ซึ่งเป็นรูปแบบจำนวนแบบใหม่ ตัวอย่างเช่น Dedekind เป็นคนแรกที่พิสูจน์ Fermat's theorem on sums of two squares [en] โดยใช้การแยกตัวประกอบได้อย่างเดียวของจำนวนเต็มเกาส์เซียน Dedekind ยังนิยามแนวคิดของโดเมนแบบยุคลิด [en] หรือระบบจำนวนซึ่งสามารถนิยามขั้นตอนวิธีแบบยุคลิดฉบับทั่วไป (ดังที่อธิบายด้านล่าง) ในทศวรรษปลายของศตวรรษที่ 19 ขั้นตอนวิธีแบบยุคลิดค่อย ๆ ถูกลดความสำคัญลงโดยทฤษฎี ideal [en] ของ dedekind ซึ่งมีความทั่วไปมากขึ้น

การประยุกต์ใช้อื่น ๆ ของขั้นตอนวิธีของยุคลิดถูกพัฒนาขึ้นในศตวรรษที่ 19 ในปี 1829 Charles Sturm [en] ได้แสดงว่าขั้นตอนวิธีนั้นเป็นประโยชน์ในวิธี Sturm chain [en] ซึ่งใช้สำหรับการนับรากที่แท้จริงของพหุนามในช่วงที่สนใจ

ขั้นตอนวิธีแบบยุคลิดเป็นขั้นตอนวิธีความสัมพันธ์ของจำนวนเต็ม [en] ซึ่งคือวิธีที่ใช้ในการหาความสัมพันธ์ของจำนวนเต็มในจำนวนจริงเทียบเท่า ขั้นตอนวิธีความสัมพันธ์ของจำนวนเต็ม [en] ใหม่หลายอันได้ถูกพัฒนาขึ้น เช่น ขั้นตอนวิธีของ Helaman Ferguson [en] และ R.W. Forcade (1979) และ LLL algorithm [en]

ในปี 1969 Cole และ Davie ได้พัฒนาเกมผู้เล่นสองคนโดยมีพื้นฐานจากขั้นตอนวิธีแบบยุคลิด ชื่อว่า The Game of Euclid ซึ่งมีกลยุทธ์ที่ดีที่สุด ผู้เล่นจะเริ่มต้นจากกองหินซึ่งมี a และ b ก้อน เมื่อถึงตาของผู้เล่นแล้วจะทำการนำหินออกจากกองที่มีจำนวนมากกว่าเป็นจำนวนเท่ากับพหุคูณ m ของจำนวนหินในกองที่น้อยกว่า ดังนั้น ถ้าทั้งสองกองมีหิน x และ y ก้อนตามลำดับ เมื่อ x มากกว่า y ผู้เล่นคนต่อไปสามารถนำหินออกจากกองที่มีจำนวนหินมากกว่า ทำให้จำนวนหินลดจาก x ก้อนเหลือ x - my ก้อน ตราบเท่าที่ยังคงเป็นจำนวนเต็มที่ไม่ติดลบ ผู้ชนะคือผู้เล่นคนแรกที่ทำให้กองใดกองหนึ่งของตนเองเหลือหินเท่ากับ 0

เอกลักษณ์ของเบซู

เอกลักษณ์ของเบซูระบุว่าตัวหารร่วมมาก g ของจำนวนนับสองจำนวน a และ b สามารถเขียนเป็นผลรวมเชิงเส้นของจำนวนนับ a และ b ได้ กล่าวอีกนัยหนึ่ง คือ สามารถหาจำนวนนับ s และ t ที่ทำให้ g = sa + tb ได้เสมอ

จำนวนนับ s และ t สามารถคำนวณได้จากผลหาร q₀, q₁, ... โดยการย้อนกลับลำดับของสมการในอัลกอริธึมของยุคลิด โดยเริ่มต้นจากสมการรองสุดท้าย ซึ่งสามารถเขียน g ในรูปของผลหาร q_N−1 และเศษที่เหลือสองตัวก่อนหน้า r_N−2 และ r_N−3 ได้ดังนี้

g = r_N−1 = r_N−3 − q_N−1 r_N−2 .

เศษที่เหลือทั้งสองนั้นสามารถเขียนให้อยู่ในรูปของผลหารและเศษที่เหลือก่อนหน้าได้เช่นกัน

r_N−2 = r_N−4 − q_N−2 r_N−3 และ
r_N−3 = r_N−5 − q_N−3 r_N−4 .

เมื่อแทนค่า r_N−2 และ r_N−3 ลงในสมการแรก จะได้ g เป็นผลรวมเชิงเส้นของเศษเหลือ r_N−4 และ r_N−5 การแทนที่สมการที่เหลือด้วยเศษที่เหลือก่อนหน้าสามารถทำต่อไปได้เรื่อย ๆ จนกว่าจะถึงจำนวนนับเดิม a และ b

r₂ = r₀ − q₂ r₁
r₁ = b − q₁ r₀
r₀ = a − q₀ b.

หลังจากแทนที่ส่วนที่เหลือทั้งหมด r₀, r₁, ... สมการสุดท้ายจะแสดงให้เห็นว่า g เป็นผลรวมเชิงเส้นของ a และ b คือ g = sa + tb จากเอกลักษณ์ของเบซู อัลกอริธึมข้างต้นจึงสามารถเขียนในรูปทั่วไปของโดเมนยุคลิด [en]ได้