ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด (อังกฤษ: Euclidean Algorithm)[a] หรือขั้นตอนวิธีของยุคลิด เป็นวิธีคำนวณตัวหารร่วมมาก (หรม.) ของจำนวนเต็มสองจำนวน ตั้งชื่อตามยุคลิด นักคณิตศาสตร์ชาวกรีกผู้อธิบายทฤษฎีนี้ในอิลิเมนต์ของยุคลิดเล่ม VII และ X [1]ตัวหารร่วมมากของจำนวนเต็มสองจำนวนคือจำนวนมากที่สุดที่หารทั้งสองได้โดยไม่เหลือเศษรูปอย่างง่ายที่สุดของขั้นตอนวิธีแบบยุคลิดเริ่มด้วยจำนวนเต็มบวกคู่หนึ่ง และสร้างจำนวนคู่หนึ่งที่ประกอบด้วยจำนวนที่น้อยกว่าและผลต่างระหว่างจำนวนทั้งสอง กระบวนการทำซ้ำจนจำนวนทั้งสองเท่ากัน จำนวนสุดท้ายเป็นตัวหารร่วมมากของจำนวนเต็มบวกที่ขั้นตอนเริ่มหลักการสำคัญคือ หรม. ไม่เปลี่ยนค่าถ้านำจำนวนที่น้อยกว่าลบจำนวนที่มากกว่า เช่น หรม. ของ 252 และ 105 เท่ากับ หรม. ของ 147 (= 252 − 105) และ 105 เพราะว่าจำนวนที่มากกว่าถูกลด การทำวิธีนี้ซ้ำทำให้ได้จำนวนเล็กลง การซ้ำนี้จึงจบอย่างแน่นอนเมื่อทั้งสองจำนวนมีค่าเท่ากัน (ถ้าทำอีกหนึ่งครั้ง จำนวนใดจำนวนหนึ่งจะเป็น 0)หลักฐานเกี่ยวกับขั้นตอนวิธีแบบยุคลิดพบในหนังสือ Elements ของยุคลิด (ในช่วงศตวรรษที่ 3 ก่อนคริสตกาล) ทำให้เป็นขั้นตอนวิธีเก่าแก่ที่สุดเกี่ยวกับจำนวนที่ยังใช้โดยทั่วไป ขั้นตอนวิธีฉบับดังเดิมใช้สำหรับจำนวนธรรมชาติและความยาวเชิงเรขาคณิต (จำนวนจริง) แต่นักคณิตศาสตร์ได้ขยายการใช้งานไปยังจำนวนชนิดอื่น เช่น จำนวนเต็มเกาส์เซียนและพหุนามหนึ่งตัวแปร อันนำไปสู่แนวคิดเชิงพีชคณิตนามธรรมสมัยใหม่ เช่นโดเมนแบบยุคลิด ขั้นตอนวิธีของยุคลิดได้นำไปใช้กับโครงสร้างทางคณิตศาสตร์อื่นๆ เช่น เงื่อน และพหุนามหลายตัวแปรขั้นตอนวิธีนี้มีการประยุกต์ใช้ในทางทฤษฎีและปฏิบัติ อาจใช้ก่อกำเนิดจังหวะดนตรีที่สำคัญหลายรูปแบบที่พบในวัฒนธรรมต่างๆ ทั่วโลก[2] ขั้นตอนวิธีนี้เป็นส่วนประกอบสำคัญของการเข้ารหัสอาร์เอสเอ (การเข้ารหัสลับแบบกุญแจอสมมาตรที่ใช้ทั่วไปในการพาณิชย์อิเล็กทรอนิกส์) ขั้นตอนวิธีนี้ใช้แก้สมการไดโอแฟนไทน์ เช่นการหาจำนวนที่สอดคล้องกับสมภาคหลายชุด(ทฤษฎีบทเศษเหลือของจีน) หรือ ตัวผกผันการคูณของเซตจำกัด และยังสามารถใช้สร้างเศษส่วนต่อเนื่องด้วยวิธีโซ่ของสเติร์มสำหรับหารากจำนวนจริงของพหุนาม และในขั้นตอนวิธีการแยกตัวประกอบของจำนวนเต็มสมัยใหม่ ที่สำคัญ เป็นเครื่องมือสำหรับพิสูจน์ทฤษฎีบทในทฤษฎีจำนวนสมัยใหม่ เช่นทฤษฎีบทผลรวมกำลังสองของลากรองจ์และทฤษฎีบทมูลฐานของเลขคณิตถ้าปรับปรุงขั้นตอนวิธีให้ใช้เศษหารจากวิธีหารแบบยุคลิดแทนที่จะเป็นการลบ ขั้นตอนวิธีของยุคลิดคำนวณค่าตัวหารร่วมมากของจำนวนขนาดใหญ่อย่างมีประสิทธิภาพ: ขั้นตอนวิธีนี้ไม่ใช้ขั้นตอนการหารจำนวนมากกว่าห้าเท่าของจำนวนหลัก(สำหรับเลขฐานสิบ)ของจำนวนขนาดเล็กกว่า โดย Gabriel Lamé พิสูจน์เมื่อปี ค.ศ. 1844 และริเริ่มการศึกษา ทฤษฎีความซับซ้อนในการคำนวณ วิธีเพิ่มประสิทธิภาพของขั้นตอนวิธีได้พัฒนาในคริสต์ศตวรรษที่ 20เมื่อย้อนขั้นตอนวิธีแบบยุคลิด ตัวหารร่วมมากสามารถเขียนในรูปผลรวมเชิงเส้นของสองจำนวนที่นำมาดำเนินการ แต่ละจำนวนคูณกับจำนวนเต็ม เช่น ตัวหารร่วมมากของ 252 และ 105 คือ 21 และ21 = [5 × 105] + [(−2) × 252] สมบัตินี้เรียกว่าเอกลักษณ์ของเบซู