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

วิธีของยุคลิดสำหรับหาตัวหารร่วมมาก (หรม.) ของความยาวเริ่มต้น BA และ DC ซึ่งต่างนิยามให้เป็นพหุคูณของความยาว"หน่วย"เดียวกัน เพราะว่า DC สั้นกว่าจึงใช้"วัด" BA แต่เพียงครั้งเดียวเพราะเศษ EA น้อยกว่า CD ใช้ EA วัดความยาว DC ที่สั้นกว่าสองครั้ง จะเหลือเศษ FC สั้นกว่า EA แล้วใช้ FC วัดความยาว EA สามครั้ง เพราะว่าขั้นตอนนี้ไม่มีเศษ จึงจบโดยมี FC เป็น หรม. ด้านขวาเป็นตัวอย่างของนิโคมาคัสโดยจำนวน 49 และ 21 ให้ผลลัพธ์ค่าตัวหารร่วมมากเป็น 7 (ประยุกต์จาก Heath 1908:300)

ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด (อังกฤษ: Euclidean Algorithm) หรือขั้นตอนวิธีของยุคลิด เป็นวิธีคำนวณตัวหารร่วมมาก (หรม.) ของจำนวนเต็มสองจำนวน ตั้งชื่อตามยุคลิด นักคณิตศาสตร์ชาวกรีกผู้อธิบายทฤษฎีนี้ในอิลิเมนต์ของยุคลิดเล่ม VII และ X

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

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

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

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

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

ถ้าปรับปรุงขั้นตอนวิธีให้ใช้เศษหารจากวิธีหารแบบยุคลิดแทนที่จะเป็นการลบ ขั้นตอนวิธีของยุคลิดคำนวณค่าตัวหารร่วมมากของจำนวนขนาดใหญ่อย่างมีประสิทธิภาพ: ขั้นตอนวิธีนี้ไม่ใช้ขั้นตอนการหารจำนวนมากกว่าห้าเท่าของจำนวนหลัก(สำหรับเลขฐานสิบ)ของจำนวนขนาดเล็กกว่า โดย Gabriel Lamé พิสูจน์เมื่อปี ค.ศ. 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) ตัวหารร่วมมากมักเขียนแทนด้วย หรม.(a, b) หรือ (a, b), แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ

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