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

ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด  หรือ ขั้นตอนวิธีของยุคลิด เป็นวิธีคำนวณตัวหารร่วมมาก (หรม.) ของจำนวนเต็มสองจำนวน ตั้งชื่อตามยุคลิด นักคณิตศาสตร์ชาวกรีกผู้อธิบายทฤษฎีนี้ใน "อิลิเมนต์ของยุคลิด" เล่ม VII และ X
ตัวหารร่วมมากของจำนวนเต็มสองจำนวนคือจำนวนเต็มมากที่สุดที่หารทั้งสองจำนวนนั้นได้โดยไม่เหลือเศษ
ขั้นตอนวิธีแบบยุคลิดเริ่มต้นด้วยจำนวนเต็มบวกคู่หนึ่ง แล้วสร้างจำนวนคู่ใหม่ประกอบด้วยจำนวนที่น้อยกว่าและผลต่างระหว่างจำนวนทั้งสอง จากนั้นทำซ้ำจนจำนวนทั้งสองเท่ากัน จำนวนในขั้นตอนสุดท้ายเป็นตัวหารร่วมมากของจำนวนเต็มบวกเริ่มต้น
หลักการสำคัญคือ หรม. ไม่เปลี่ยนค่าถ้านำจำนวนที่น้อยกว่าลบจำนวนที่มากกว่า เช่น หรม. ของ 252 และ 105 เท่ากับ หรม. ของ 147 (= 252 − 105) และ 105 จำนวนที่มากกว่าถูกลดลดค่าลงเสมอ ทำให้การทำวิธีนี้ซ้ำได้จำนวนที่เล็กลง การซ้ำนี้จึงจบอย่างแน่นอนเมื่อทั้งสองจำนวนมีค่าเท่ากัน (ถ้าทำอีกหนึ่งครั้ง จำนวนใดจำนวนหนึ่งจะเป็น 0)
หลักฐานเกี่ยวกับขั้นตอนวิธีแบบยุคลิดพบในหนังสือ "Elements" ของยุคลิด (ในช่วงศตวรรษที่ 3 ก่อนคริสตกาล) ทำให้เป็นขั้นตอนวิธีเก่าแก่ที่สุดเกี่ยวกับจำนวนที่ยังใช้โดยทั่วไป ขั้นตอนวิธีฉบับดังเดิมใช้สำหรับจำนวนธรรมชาติและความยาวเชิงเรขาคณิต (จำนวนจริง) แต่นักคณิตศาสตร์ได้ขยายการใช้งานไปยังจำนวนชนิดอื่น เช่น จำนวนเต็มเกาส์เซียนและพหุนามหนึ่งตัวแปร อันนำไปสู่แนวคิดเชิงพีชคณิตนามธรรมสมัยใหม่ เช่น โดเมนแบบยุคลิด ซึ่งเป็นริงที่สามารถทำขั้นตอนวิธีของยุคลิดได้
ขั้นตอนวิธีของยุคลิดมีการประยุกต์ใช้ในทางทฤษฎีและปฏิบัติ อาจใช้ก่อกำเนิดที่สำคัญหลายรูปแบบที่พบในวัฒนธรรมต่าง ๆ ทั่วโลก ขั้นตอนวิธีนี้เป็นส่วนประกอบสำคัญของการเข้ารหัสอาร์เอสเอ (การเข้ารหัสลับแบบกุญแจอสมมาตรที่ใช้ทั่วไปในการพาณิชย์อิเล็กทรอนิกส์) ขั้นตอนวิธีแบบยุคลิดใช้แก้สมการไดโอแฟนไทน์แบบรูปแบบ เช่นการหาจำนวนที่สอดคล้องกับสมภาคหลายชุด (ทฤษฎีบทเศษเหลือของจีน) หรือตัวผกผันการคูณในฟิลด์จำกัด, ใช้สร้างเศษส่วนต่อเนื่อง, ใช้หาจำนวนรากจริงของพหุนามโดยวิธีโซ่ของสเติร์ม และในขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มสมัยใหม่ และที่สำคัญ ขั้นตอนวิธีของยุคลิดเป็นเครื่องมือสำหรับพิสูจน์ทฤษฎีบทในทฤษฎีจำนวน เช่น และทฤษฎีบทมูลฐานของเลขคณิต
ถ้าปรับปรุงขั้นตอนวิธีให้ใช้เศษหารจากวิธีหารแบบยุคลิดแทนที่จะเป็นการลบ ขั้นตอนวิธีของยุคลิดคำนวณค่าตัวหารร่วมมากของจำนวนขนาดใหญ่อย่างมีประสิทธิภาพ โดยใช้ขั้นตอนวิธีการหารเป็นจำนวนครั้งไม่เกินห้าเท่าของจำนวนหลักของจำนวนขนาดเล็กกว่า (ในฐานสิบ) ขั้นตอนวิธีแบบปรับปรุงนี้พิสูจน์ได้โดย #เปลี่ยนทาง เมื่อปี ค.ศ. 1844 นับเป็นจุดริเริ่มการศึกษาทฤษฎีความซับซ้อนในการคำนวณ และในคริสต์ศตวรรษที่ 20 มีการพัฒนาวิธีเพิ่มประสิทธิภาพในรูปแบบอื่นเพิ่มขึ้นมา
เมื่อย้อนขั้นตอนวิธีแบบยุคลิด ตัวหารร่วมมากสามารถเขียนในรูปผลรวมเชิงเส้นของสองจำนวนที่นำมาดำเนินการ โดยที่แต่ละจำนวนคูณกับจำนวนเต็ม เช่น ตัวหารร่วมมากของ 252 และ 105 คือ 21 และ #เปลี่ยนทาง สมบัตินี้เรียกว่าเอกลักษณ์ของเบซู
พื้นฐาน — ตัวหารร่วมมาก.
ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของจำนวนธรรมชาติสองจำนวน "a" และ "b" ค่าตัวหารร่วมมาก "g" เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง "a" และ "b" ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ ตัวประกอบร่วมค่ามากสุด , ตัวประกอบร่วมค่ามากสุด  และ 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 <math>\times</math> 1, สี่เหลี่ยมจัตุรัส 2 <math>\times</math> 2, สี่เหลี่ยมจัตุรัส 3 <math>\times</math> 3, สี่เหลี่ยมจัตุรัส 4 <math>\times</math> 4, สี่เหลี่ยมจัตุรัส 6<math>\times</math>6 หรือสี่เหลี่ยมจัตุรัส 12 <math>\times</math> 12 ดังนั้น 12 คือตัวหารร่วมมากของ 24 และ 60 โดยสี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 สามารถแบ่งเป็นตารางของสี่เหลี่ยมจัตุรัสยาวด้านละ 12 ที่มีสี่เหลี่ยมจัตุรัส 2 รูปติดด้านกว้าง (24/12 = 2) และสี่เหลี่ยมจัตุรัส 5 รูปติดด้านยาว (60/12 = 5) 
ตัวหารร่วมมากของสองจำนวน a และ b คือผลคูณของตัวประกอบเฉพาะที่สองจำนวนนี้มีร่วมกัน โดยตัวประกอบเฉพาะหนึ่งค่าสามารถนำมาคูณได้หลายรอบ ตราบที่ผลคูณของตัวประกอบเหล่านี้หาร a และ b ลงตัว ตัวอย่างเช่น 1386 แยกตัวประกอบได้เป็น 2 <math>\times</math> 3 <math>\times</math> 3 <math>\times</math> 7 <math>\times</math> 11 และ 3213 แยกตัวประกอบได้เป็น 3 <math>\times</math> 3 <math>\times</math> 3 <math>\times</math> 7 <math>\times</math> 17 ตัวหารร่วมมากของ 1386 และ 3213 จึงเท่ากับ 63 = 3 <math>\times</math> 3 <math>\times</math> 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" ที่สอดคล้องกับสมการ
<math>r_{k-2} = q_k r_{k-1} + r_k</math>
จะได้ว่า 0 ≤ "r""k" < "r""k"−1 กล่าวได้ว่า จำนวนที่มากกว่า "r""k"−2 ถูกลบด้วยพหุคูณของจำนวนที่น้อยกว่า "r""k"−1 จนกว่าเศษ "r""k" จะมีค่าน้อยกว่า "r""k"−1
ในขั้นแรก ("k" = 0) เศษ "r"−2 และ "r"−1 มีค่าเท่ากับ "a" และ "b" ตามลำดับ ในขั้นต่อมา ("k" = 1) เศษมีค่าเท่ากับ "b" และเศษ "r"0 ของขั้นแรก ทำแบบนี้ต่อไปเรื่อย ๆ ขั้นตอนวิธีดังกล่าวเขียนออกมาในรูปแบบลำดับของสมการได้ว่า
<math>\begin{align}
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{align}</math>
ถ้า "a" มีค่าน้อยกว่า "b" ให้สลับตัวเลขในขั้นแรก ตัวอย่างคือ ถ้า "a" < "b" ผลหารในขั้นแรก "q"0 จะมีค่าเท่ากับศูนย์ และเศษ "r"0 มีค่าเท่ากับ "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"0) = gcd("r"0, "r"1) = … = gcd("r""N"−2, "r""N"−1) = "r""N"−1.
ตัวอย่างการใช้งาน.
เพื่อให้เห็นภาพ ขั้นตอนวิธีแบบยุคลิดสามารถนำมาใช้หาตัวหารร่วมมากของ "a" = 1071 และ "b" = 462 ได้ เริ่มต้นด้วย นำ 1071 เป็นตัวตั้ง ลบกับตัวคูณของ 462 จนกว่าเศษจะน้อยกว่า 462 ซึ่งเมื่อพิจารณาแล้ว การคูณด้วย 2 นั้นสามารถนำมาใช้ในการลบออกได้ ("q"0 = 2) โดยมีเศษคือ 147
 1071 = 2 × 462 + 147.
ต่อมา ตัวคูณของ 147 จะถูกลบออกจาก 462 จนกว่าเศษจะมีค่าน้อยกว่า 147 เมื่อพิจารณาแล้ว การคูณด้วย 3 นั้นสามารถนำมาใช้ในการลบออกได้
 462 = 3 × 147 + 21.
ต่อมา ตัวคูณของ 21 จะถูกลบออกจาก 147 จนกว่าเศษจะมีค่าน้อยกว่า 21 ซึ่งการคูณด้วย 7 นั้นสามารถนำมาใช้ในการลบออกได้ ("q"2 = 7) ไม่เหลือเศษแล้ว
 147 = 7 × 21 + 0.
การอธิบายเป็นภาพ.
เราสามารถทำขั้นตอนวิธีแบบยูคลิดให้เห็นภาพได้ โดยใช้วิธีคล้ายกับการปูกระเบื้องในการหาตัวหารร่วมมาก สมมุติว่าเราต้องการปูพื้นที่สี่เหลี่ยมผืนผ้าขนาด <math>a \times b</math> โดยใช้กระเบื้องสี่เหลี่ยมจัตุรัส โดยที่ "a" เป็นค่าที่มีค่ามากกว่าอีกจำนวน เริ่มแรก เราจะปูโดยใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด <math>b \times b</math> แต่ว่า กลับเหลือพื้นที่ที่ปูไม่ได้ มีขนาดเป็น <math>r_0 \times b</math> โดยที่ <math>r_0 < b</math> เราก็เลยเปลี่ยนไปใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด <math>r_0 \times r_0</math> แทน แต่ก็ยังปูพื้นที่ได้ไม่ครบอีก เหลือพื้นที่เป็น <math>r_1 \times r_0</math> เราก็เลยเปลี่ยนไปใช้กระเบื้องขนาด <math>r_1 \times r_1</math> แทน ทำแบบนี้ซ้ำไปเรื่อย ๆ จนกระทั่งไม่เหลือพื้นที่ที่ยังไม่ได้ปู นั่นคือ เมื่อกระเบื้องสี่เหลียมจัตุรัสสามารถปูพื้นที่ที่ยังไม่ได้ปูในขั้นที่แล้วได้ทั้งหมด โดยความยาวของด้านของสี่เหลี่ยมจัตุรัสที่เล็กที่สุดก็คือตัว ห.ร.ม. ของขนาดของสี่เหลี่ยมรูปต้นแบบนั่นเอง เช่น กระเบื้องสี่เหลี่ยมจัตุรัสขนาดเล็กที่สุดในรูปคือ <math>21 \times 21</math> (ในรูปแสดงโดยใช้สีแดง) และ 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)
พัฒนาการทางประวัติศาสตร์.
ขั้นตอนวิธีแบบยุคลิดเป็นหนึ่งในขั้นตอนวิธีที่เก่าแก่ที่สุดที่ใช้กันอย่างแพร่หลาย ซึ่งปรากฏใน#เปลี่ยนทาง (300 ปีก่อนคริสต์ศักราช) โดยเฉพาะในหนังสือเล่มที่ 7 (ประพจน์ที่ 1-2) และในหนังสือเล่มที่ 10 (ประพจน์ที่ 2-3) ในหนังสือเล่มที่ 7 ขั้นตอนวิธีถูกสร้างขึ้นเพื่อใช้กับจำนวนเต็ม แต่ในหนังสือเล่มที่ 10 ได้นำไปใช้กับความยาวส่วนของเส้นตรง (ในการใช้สมัยใหม่นี้ อาจพูดได้ว่ามันถูกสร้างขึ้นเพื่อใช้กับจำนวนจริง แต่ในอดีต ความยาว พื้นที่ และปริมาตร ซึ่งนับว่าเป็นจำนวนจริงในปัจจุบัน ไม่ได้ถูกวัดด้วยหน่วยเดียวกันและไม่ได้มีหน่วยธรรมชาติเป็นของตนเอง อาจกล่าวได้ว่าแนวคิดเกี่ยวกับจำนวนจริงไม่เป็นที่รู้จักในขณะนั้น) ขั้นตอนวิธีถัดมานั้นเกี่ยวกับเรขาคณิต ห. ร. ม. ของความยาว "a" และ "b" สอดคล้องกับความยาวที่มากที่สุด "g" ซึ่งวัด "a" และ "b" กล่าวคือ ความยาว "a" และ "b" ทั้งคู่ต่างก็เป็นพหุคูณของความยาว "g"
ขั้นตอนวิธีนี้อาจไม่ได้ถูกคิดค้นโดยยุคลิด ผู้ซึ่งรวบรวมผลลัพธ์จากนักคณิตศาสตร์ในหนังสือ "เอเลเมนส์" ของเขา นักคณิตศาสตร์และประวัติศาสตร์ #เปลี่ยนทาง ได้เสนอแนะว่า เนื้อหาในหนังสือเล่มที่ 7 ได้รับมาจากตำราเรียนเกี่ยวกับทฤษฎีจำนวน ซึ่งเขียนโดยนักคณิตศาสตร์ในโรงเรียนของพีทาโกรัส ขั้นตอนวิธีอาจเป็นที่รู้จักจาก #เปลี่ยนทาง (ราว 375 ปีก่อนคริสต์ศักราช) ขั้นตอนวิธีนี้อาจเกิดขึ้นก่อน Eudoxus พิจารณาจากการใช้ศัพท์เฉพาะ ἀνθυφαίρεσις ("anthyphairesis" หรือการลบส่วนกลับ) ในงานของยุคลิดและแอริสตอเติล
หลายศตวรรษต่อมา ขั้นตอนวิธีของยุคลิดถูกค้นพบทั้งในประเทศอินเดียและจีน โดยแรกเริ่มเพื่อแก้ปัญหา#เปลี่ยนทาง ซึ่งเกิดขึ้นในดาราศาสตร์และทำให้สามารถสร้างปฏิทินที่แม่นยำ ในช่วงท้ายศตวรรษที่ 5 นักคณิตศาสตร์และดาราศาสตร์ชาวอินเดีย อารยภัฏ ได้อธิบายขั้นตอนวิธีว่าเป็น "เครื่องบด" ซึ่งอาจมาจากประสิทธิภาพของมันในการแก้ปัญหาสมการไดโอแฟนไทน์ ถึงแม้ว่ากรณีพิเศษของ#เปลี่ยนทาง จะถูกอธิบายในหนังสือจีนชื่อ "#เปลี่ยนทาง " โดยผลเฉลยทั่วไปถูกเผยแพร่โดย #เปลี่ยนทาง ในหนังสือของเขาชื่อ "Shushu Jiuzhang" (數書九章 "#เปลี่ยนทาง ") ขั้นตอนวิธีแบบยุคลิดถูกอธิบายในเชิงตัวเลขครั้งแรกและเป็นที่รู้จักอย่างมากในยุโรปในหนังสือ "Problèmes plaisants et délectables" ฉบับที่ 2 ของ #เปลี่ยนทาง ("Pleasant and enjoyable problems", 1624) ในยุโรป ขั้นตอนวิธีแบบยุคลิดถูกใช้เพื่อแก้ปัญหาสมการไดโอแฟนไทน์และใช้เพื่อพัฒนาเศษส่วนต่อเนื่อง #เปลี่ยนทาง ถูกตีพิมพ์โดยนักคณิตศาสตร์ชาวอังกฤษชื่อ #เปลี่ยนทาง ซึ่งเชื่อว่ามันเกิดมาจาก #เปลี่ยนทาง เพื่อเป็นวิธีสำหรับคำนวณเศษส่วนต่อเนื่องอย่างมีประสิทธิภาพ
ในศตวรรษที่ 19 ขั้นตอนวิธีแบบยุคลิดนำไปสู่การพัฒนาระบบจำนวนแบบใหม่ เช่น #เปลี่ยนทาง และ#เปลี่ยนทาง ในปี 1815 คาร์ล ฟรีดริช เกาส์ได้ใช้ขั้นตอนวิธีแบบยุคลิดในการสาธิตการแยกตัวประกอบได้อย่างเดียวใน#เปลี่ยนทาง ถึงแม้ผลงานของเขาจะได้ตีพิมพ์ครั้งแรกในปี 1832 ก็ตาม เกาส์ได้พูดถึงขั้นตอนวิธีในหนังสือ "#เปลี่ยนทาง " ของเขา (ถูกตีพิมพ์ในปี 1801) แต่ใช้เป็นเพียงวิธีสำหรับเศษส่วนต่อเนื่อง #เปลี่ยนทาง เป็นคนแรกที่อธิบายขั้นตอนวิธีแบบยุคลิดเพื่อเป็นพื้นฐานสำหรับทฤษฏีจำนวนอื่น ๆ Lejeune Dirichlet ได้ระบุว่าผลลัพธ์ของทฤษฎีจำนวนหลายอัน เช่น การแยกตัวประกอบได้อย่างเดียว (Unique factorization) จะเป็นจริงสำหรับระบบจำนวนใด ๆ ที่สามารถใช้ขั้นตอนวิธีแบบยุคลิดได้ การบรรยายของ Lejeune Dirichlet ในหัวข้อทฤษฎีจำนวนถูกแก้ไขและต่อเติมโดย #เปลี่ยนทาง ผู้ใช้ขั้นตอนวิธีของยุคลิดในการศึกษาจำนวนเชิงพีชคณิต ซึ่งเป็นรูปแบบจำนวนแบบใหม่ ตัวอย่างเช่น Dedekind เป็นคนแรกที่พิสูจน์ #เปลี่ยนทาง โดยใช้การแยกตัวประกอบได้อย่างเดียวของจำนวนเต็มเกาส์เซียน Dedekind ยังนิยามแนวคิดของ#เปลี่ยนทาง หรือระบบจำนวนซึ่งสามารถนิยามขั้นตอนวิธีแบบยุคลิดฉบับทั่วไป (ดังที่อธิบายด้านล่าง) ในทศวรรษปลายของศตวรรษที่ 19 ขั้นตอนวิธีแบบยุคลิดค่อย ๆ ถูกลดความสำคัญลงโดยทฤษฎี #เปลี่ยนทาง ของ dedekind ซึ่งมีความทั่วไปมากขึ้น
การประยุกต์ใช้อื่น ๆ ของขั้นตอนวิธีของยุคลิดถูกพัฒนาขึ้นในศตวรรษที่ 19 ในปี 1829 #เปลี่ยนทาง ได้แสดงว่าขั้นตอนวิธีนั้นเป็นประโยชน์ในวิธี #เปลี่ยนทาง ซึ่งใช้สำหรับการนับรากที่แท้จริงของพหุนามในช่วงที่สนใจ
ขั้นตอนวิธีแบบยุคลิดเป็น#เปลี่ยนทาง ซึ่งคือวิธีที่ใช้ในการหาความสัมพันธ์ของจำนวนเต็มในจำนวนจริงเทียบเท่า #เปลี่ยนทาง ใหม่หลายอันได้ถูกพัฒนาขึ้น เช่น ขั้นตอนวิธีของ #เปลี่ยนทาง และ R.W. Forcade (1979) และ #เปลี่ยนทาง 
ในปี 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"0, "q"1, ... โดยการย้อนกลับลำดับของสมการในอัลกอริธึมของยุคลิด โดยเริ่มต้นจากสมการรองสุดท้าย ซึ่งสามารถเขียน "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"2 = "r"0 − "q"2 "r"1
 "r"1 = "b" − "q"1 "r"0
 "r"0 = "a" − "q"0 "b"
หลังจากแทนที่ส่วนที่เหลือทั้งหมด "r"0, "r"1, ... สมการสุดท้ายจะแสดงให้เห็นว่า "g" เป็นผลรวมเชิงเส้นของ "a" และ "b" คือ "g" = "sa" + "tb" จากเอกลักษณ์ของเบซู อัลกอริธึมข้างต้นจึงสามารถเขียนในรูปทั่วไปของ#เปลี่ยนทาง ได้
หมายเหตุ.
<templatestyles src="Refbegin/styles.css" />