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

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

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

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

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

หลักการสำคัญคือ หรม. ไม่เปลี่ยนค่าถ้านำจำนวนที่น้อยกว่าลบจำนวนที่มากกว่า เช่น หรม. ของ 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) ตัวหารร่วมมากมักเขียนแทนด้วย 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 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน

สี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 ประกอบด้วยสี่เหลี่ยมขนาดด้านละ 12 จำนวนสิบรูป ซึ่ง 12 คือตัวหารร่วมมากของ 24 และ 60 ในกรณีทั่วไป สี่เหลี่ยมผืนผ้ากว้าง a ยาว b จะแบ่งเป็นสี่เหลี่ยมจัตุรัสย่อยด้านละ c ได้เฉพาะในกรณีที่ c เป็นตัวหารร่วมของ a และ b

ให้ 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 $\times$ 1, สี่เหลี่ยมจัตุรัส 2 $\times$ 2, สี่เหลี่ยมจัตุรัส 3 $\times$ 3, สี่เหลี่ยมจัตุรัส 4 $\times$ 4, สี่เหลี่ยมจัตุรัส 6$\times$6 หรือสี่เหลี่ยมจัตุรัส 12 $\times$ 12 ดังนั้น 12 คือตัวหารร่วมมากของ 24 และ 60 โดยสี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 สามารถแบ่งเป็นตารางของสี่เหลี่ยมจัตุรัสยาวด้านละ 12 ที่มีสี่เหลี่ยมจัตุรัส 2 รูปติดด้านกว้าง (24/12 = 2) และสี่เหลี่ยมจัตุรัส 5 รูปติดด้านยาว (60/12 = 5)

ตัวหารร่วมมากของสองจำนวน a และ b คือผลคูณของตัวประกอบเฉพาะที่สองจำนวนนี้มีร่วมกัน โดยตัวประกอบเฉพาะหนึ่งค่าสามารถนำมาคูณได้หลายรอบ ตราบที่ผลคูณของตัวประกอบเหล่านี้หาร a และ b ลงตัว ตัวอย่างเช่น 1386 แยกตัวประกอบได้เป็น 2 $\times$ 3 $\times$ 3 $\times$ 7 $\times$ 11 และ 3213 แยกตัวประกอบได้เป็น 3 $\times$ 3 $\times$ 3 $\times$ 7 $\times$ 17 ตัวหารร่วมมากของ 1386 และ 3213 จึงเท่ากับ 63 = 3 $\times$ 3 $\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 ที่สอดคล้องกับสมการ

$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₀ ของขั้นแรก ทำแบบนี้ต่อไปเรื่อย ๆ ขั้นตอนวิธีดังกล่าวเขียนออกมาในรูปแบบลำดับของสมการได้ว่า

${\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 ต่อมา สี่เหลี่ยมจัตุรัสขนาด 462×462 ถูกวางลงไป ทำให้เหลือสี่เหลี่ยมพืนผ้าขนาด 462×147 โดยสี่เหลี่ยมพืนผ้านี้จะถูกวางทับโดยสี่เหลี่ยมจัตุรัสขนาด 147×147 จนกระทั่งเหลือสี่เหลี่ยมพื้นผ้าขนาด 21×147 ที่เหลือก็นำสี่เหลี่ยมจัตุรัสขนาด 21×21 มาวางให้ครบ ทำให้ไม่เหลือพื้นที่ที่ยังไม่ได้ปิด จึงสรุปได้ว่า ขนาดของสี่เหลี่ยมจัตุรัสที่เล็กที่สุด (21) คือ ห.ร.ม. ของ 1071 และ 462

เพื่อให้เห็นภาพ ขั้นตอนวิธีแบบยุคลิดสามารถนำมาใช้หาตัวหารร่วมมากของ 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.

ขั้นที่ k	สมการ	ผลหาร (q) และเศษเหลือ (r)
0	1071 = q0 462 + r0	q0 = 2 และ r0 = 147
1	462 = q1 147 + r1	q1 = 3 และ r1 = 21
2	147 = q2 21 + r2	q2 = 7 และ r2 = 0; อัลกอริทึมจบลง

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

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

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

บทความหลัก: Euclidean division

ในทุกขั้นตอน 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)")

พัฒนาการทางประวัติศาสตร์

ขั้นตอนวิธีแบบยุคลิดอาจถูกคิดค้นขึ้นก่อนยุคลิด ซึ่งในภาพนี้ที่ถูกวาดขึ้นในปี 1474 ยุคลิดได้ถือเข็มทิศไว้ในมือ

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

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

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

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

"ขั้นตอนวิธีแบบยุคลิด นับเป็นคุณปู่ของขั้นตอนวิธีทั้งหมด เพราะ มันเป็นขั้นตอนวิธีไม่ชัดแจ้งที่เก่าแก่ที่สุดที่ยังมีการใช้อยู่ในปัจจุบัน"

โดนัลด์ คนูธ, The Art of Computer Programming, เล่มที่ 2: Seminumerical Algorithms, พิมพ์ครั้งที่ 2 (1981), 318.

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

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

ในปี 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 จากเอกลักษณ์ของเบซู อัลกอริธึมข้างต้นจึงสามารถเขียนในรูปทั่วไปของโดเมนยุคลิดได้

หมายเหตุ

• ก. ^{^} ตำราบางเล่มที่ใช้โดยทั่วไป เช่น Topics in Algebra ของ I. N. Herstein และ Algebra ของ Serge Langใช้คำว่า "Euclidean algorithm" หมายถึงวิธีหารแบบยุคลิด

บรรณานุกรม

• Cohen, H. (1993). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. ISBN 0-387-55640-0.
• Cohn, H. (1962). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X.
• Cox, D.; Little, J.; O'Shea, D. (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (2nd ed.). Springer-Verlag. ISBN 0-387-94680-2.
• Crandall, R.; Pomerance, C. (2001). Prime Numbers: A Computational Perspective (1st ed.). New York: Springer-Verlag. ISBN 0-387-94777-9.
• Lejeune Dirichlet, P. G. (1894). Dedekind, Richard (บ.ก.). Vorlesungen über Zahlentheorie (Lectures on Number Theory) (ภาษาเยอรมัน). Braunschweig: Vieweg. LCCN 03005859. OCLC 490186017.. See also Vorlesungen über Zahlentheorie
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison–Wesley. ISBN 0-201-89684-2.
• LeVeque, W. J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9.
• Mollin, R. A. (2008). Fundamental Number Theory with Applications (2nd ed.). Boca Raton: Chapman & Hall/CRC. ISBN 978-1-4200-6659-3.
• Ore, O. (1948). Number Theory and Its History. New York: McGraw–Hill.
• Rosen, K. H. (2000). Elementary Number Theory and its Applications (4th ed.). Reading, MA: Addison–Wesley. ISBN 0-201-87073-8.
• Schroeder, M. (2005). Number Theory in Science and Communication (4th ed.). Springer-Verlag. ISBN 0-387-15800-6.
• Stark, H. (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8.
• Stillwell, J. (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2.
• Stillwell, J. (2003). Elements of Number Theory. New York: Springer-Verlag. ISBN 0-387-95587-9.
• Tattersall, J. J. (2005). Elementary Number Theory in Nine Chapters. Cambridge: Cambridge University Press. ISBN 978-0-521-85014-8.