ขั้นตอนวิธีแบบยุคลิด
พัฒนาการทางประวัติศาสตร์

ขั้นตอนวิธีแบบยุคลิดเป็นหนึ่งในขั้นตอนวิธีที่เก่าแก่ที่สุดที่ใช้กันอย่างแพร่หลาย ซึ่งปรากฏในหนังสือเอเลเมนส์ของยุคลิด [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