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

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

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

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

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

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

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

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

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

เมื่อย้อนขั้นตอนวิธีแบบยุคลิด ตัวหารร่วมมากสามารถเขียนในรูปผลรวมเชิงเส้นของสองจำนวนที่นำมาดำเนินการ โดยที่แต่ละจำนวนคูณกับจำนวนเต็ม เช่น ตัวหารร่วมมากของ 252 และ 105 คือ 21 และ  สมบัตินี้เรียกว่าเอกลักษณ์ของเบซู

## พื้นฐาน — ตัวหารร่วมมาก

ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของจำนวนธรรมชาติสองจำนวน *a* และ *b* ค่าตัวหารร่วมมาก *g* เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง *a* และ *b* ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ **ตัวประกอบร่วมค่ามากสุด** (), **ตัวประกอบร่วมค่ามากสุด** () และ **greatest common measure** (GCM) ตัวหารร่วมมากมักเขียนแทนด้วย gcd(*a*,&nbsp;*b*) หรือ (*a*,&nbsp;*b*), แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ

ถ้า gcd(*a*,&nbsp;*b*)&nbsp;=&nbsp;1 แล้ว *a* กับ *b* เป็นจำนวนเฉพาะสัมพัทธ์ ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า *a* หรือ *b* เป็นจำนวนเฉพาะเองแต่อย่างใด เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6&nbsp;=&nbsp;2&nbsp;×&nbsp;3 and 35&nbsp;=&nbsp;5&nbsp;×&nbsp;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 \times 1, สี่เหลี่ยมจัตุรัส 2 \times 2, สี่เหลี่ยมจัตุรัส 3 \times 3, สี่เหลี่ยมจัตุรัส 4 \times 4, สี่เหลี่ยมจัตุรัส 6\times6 หรือสี่เหลี่ยมจัตุรัส 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 (เท่ากับค่าผลคูณว่าง) หรือก็คือทั้งสองจำนวนนั้นเป็นจำนวนเฉพาะสัมพัทธ์ ข้อได้เปรียบของขั้นตอนวิธีแบบยุคลิดคือสามารถหาค่าตัวหารร่วมมากโดยไม่ต้องหาตัวประกอบเฉพาะร่วม    

หรม. ของสามจำนวนขึ้นไปมีค่าเท่ากับผลคูณของตัวประกอบเฉพาะของจำนวนเหล่านั้น แต่ก็สามารถหาได้จากการหา หรม. ของแต่ละคู่จำนวน   

: 

ดังนั้นขั้นตอนวิธีแบบยูคลิดที่หาหรม.ของสองจำนวนจะสามารถหา หรม. ของหลายจำนวนได้ด้วยเช่นกัน

## คำอธิบาย

### กระบวนการ
ขั้นตอนวิธีแบบยูคลิดดำเนินเป็นขั้นตอน โดยผลลัพธ์ในแต่ละขั้นตอนจะถูกใช้ในขั้นตอนต่อไป ให้ *k* เป็นจำนวนเต็มที่นับจำนวนขั้นตอนในวิธีการยูคลิด เริ่มจากศูนย์ ดังนั้นในขั้นตอนที่หนึ่งมีค่า *k*&nbsp;=&nbsp;0 ขั้นตอนที่สองมีค่า *k*&nbsp;=&nbsp;1 เป็นแบบนี้ไปเรื่อย ๆ

แต่ละขั้นตอนเริ่มด้วยเศษสองจำนวนที่มีค่าไม่เป็นลบ *r**k*&minus;1 และ *r**k*&minus;2 เนื่องจากวิธีการนี้จะทำให้เศษมีค่าลดลงในทุกขั้นตอนเสมอ *r**k*&minus;1 มีค่าน้อยกว่าเศษตัวก่อน *r**k*&minus;2 เป้าหมายของขั้นตอนที่ k คือหาผลหาร *q**k* และเศษ *r**k* ที่สอดคล้องกับสมการ

:r_{k-2} = q_k r_{k-1} + r_k

จะได้ว่า 0 ≤ *r**k*&nbsp;*k*&minus;1 กล่าวได้ว่า จำนวนที่มากกว่า *r**k*&minus;2 ถูกลบด้วยพหุคูณของจำนวนที่น้อยกว่า *r**k*&minus;1 จนกว่าเศษ *r**k* จะมีค่าน้อยกว่า *r**k*&minus;1

ในขั้นแรก (*k*&nbsp;=&nbsp;0) เศษ *r*−2 และ *r*−1 มีค่าเท่ากับ *a* และ *b* ตามลำดับ ในขั้นต่อมา (*k*&nbsp;=&nbsp;1) เศษมีค่าเท่ากับ *b* และเศษ *r*0 ของขั้นแรก ทำแบบนี้ต่อไปเรื่อย ๆ ขั้นตอนวิธีดังกล่าวเขียนออกมาในรูปแบบลำดับของสมการได้ว่า

:\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}

ถ้า *a* มีค่าน้อยกว่า *b* ให้สลับตัวเลขในขั้นแรก ตัวอย่างคือ ถ้า *a*&nbsp;0 จะมีค่าเท่ากับศูนย์ และเศษ *r*0 มีค่าเท่ากับ *a* ดังนั้น *r**k* จะมีค่าน้อยกว่า *r**k*−1 สำหรับทุก *k*&nbsp;≥&nbsp;0

เพราะเศษมีค่าลดลงในทุกขั้นตอน แต่ไม่สามารถเป็นมีค่าเป็นลบ เศษ *r**N* จึงจะต้องเท่ากับศูนย์ในสักขั้นตอน

### การพิสูจน์ความถูกต้อง
ความถูกต้องของขั้นตอนวิธีแบบยูคลิดสามารถพิสูจน์ได้โดยสองขั้นตอน ในขั้นตอนแรก เห็นได้ว่าเศษตัวสุดท้ายที่ไม่เท่ากับศูนย์ *r**N*−1 จะหารทั้ง *a* และ *b* ลงตัว เพราะมันเป็นตัวหารร่วม จึงมีค่าน้อยกว่าหรือเท่ากับตัวหารร่วมมาก *g* และในขั้นตอนที่สอง เห็นได้ว่าตัวหารร่วมใด ๆ ของ *a* และ *b* (รวมถึงตัวหารร่วมมาก *g* ด้วย) ต้องหาร *r**N*−1 ลงตัว ดังนั้น *g* ต้องมีค่าน้อยกว่าหรือเท่ากับ *r**N*−1 ข้อสรุปสองอันนี้ไม่แน่นอน เว้นแต่ *r**N*−1&nbsp;=&nbsp;*g*

เพื่อแสดงให้เห็นว่า *r**N*−1 หารทั้ง *a* และ *b* ลงตัว (ขั้นแรก) และ *r**N*−1 หาร *r**N*−2 ลงตัว

: 

เพราะเศษตัวสุดท้าย *r**N* คือศูนย์ ทำให้ *r**N*−1 หาร *r**N*−3 ลงตัวด้วย

: 

: 

### ตัวอย่างการใช้งาน

เพื่อให้เห็นภาพ ขั้นตอนวิธีแบบยุคลิดสามารถนำมาใช้หาตัวหารร่วมมากของ *a*&nbsp;=&nbsp;1071 และ *b*&nbsp;=&nbsp;462 ได้ เริ่มต้นด้วย นำ 1071 เป็นตัวตั้ง ลบกับตัวคูณของ 462 จนกว่าเศษจะน้อยกว่า 462 ซึ่งเมื่อพิจารณาแล้ว การคูณด้วย 2 นั้นสามารถนำมาใช้ในการลบออกได้ (*q*0&nbsp;=&nbsp;2) โดยมีเศษคือ 147

: 

ต่อมา ตัวคูณของ 147 จะถูกลบออกจาก 462 จนกว่าเศษจะมีค่าน้อยกว่า 147 เมื่อพิจารณาแล้ว การคูณด้วย 3 นั้นสามารถนำมาใช้ในการลบออกได้

: 

ต่อมา ตัวคูณของ 21 จะถูกลบออกจาก 147 จนกว่าเศษจะมีค่าน้อยกว่า 21 ซึ่งการคูณด้วย 7 นั้นสามารถนำมาใช้ในการลบออกได้ (*q*2&nbsp;=&nbsp;7) ไม่เหลือเศษแล้ว

: 

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

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

ในทุกขั้นตอน *k* ขั้นตอนวิธีแบบยุคลิดคำนวณผลหาร *q**k* และเศษ *r**k* จากตัวเลขสองตัว *r**k*−1 และ *r**k*−2

: 

โดยที่ *r**k* เป็นจำนวนเต็มที่ไม่เป็นลบ และมีค่าน้อยกว่าค่าสัมบูรณ์ของ *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,&nbsp;0)&nbsp;=&nbsp;*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)")

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

ขั้นตอนวิธีแบบยุคลิดเป็นหนึ่งในขั้นตอนวิธีที่เก่าแก่ที่สุดที่ใช้กันอย่างแพร่หลาย ซึ่งปรากฏใน (300&nbsp;ปีก่อนคริสต์ศักราช) โดยเฉพาะในหนังสือเล่มที่ 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''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb'' ได้เสมอ

จำนวนนับ s และ t สามารถคำนวณได้จากผลหาร ''q''<sub>0</sub>, ''q''<sub>1</sub>, ... โดยการย้อนกลับลำดับของสมการในอัลกอริธึมของยุคลิด โดยเริ่มต้นจากสมการรองสุดท้าย ซึ่งสามารถเขียน ''g'' ในรูปของผลหาร ''q''<sub>''N''−1</sub> และเศษที่เหลือสองตัวก่อนหน้า ''r''<sub>''N''−2</sub> และ ''r''<sub>''N''−3</sub> ได้ดังนี้

: 

เศษที่เหลือทั้งสองนั้นสามารถเขียนให้อยู่ในรูปของผลหารและเศษที่เหลือก่อนหน้าได้เช่นกัน

:  และ
: 

เมื่อแทนค่า ''r''<sub>''N''−2</sub> และ ''r''<sub>''N''−3</sub> ลงในสมการแรก จะได้ ''g'' เป็นผลรวมเชิงเส้นของเศษเหลือ ''r''<sub>''N''−4</sub> และ ''r''<sub>''N''−5</sub> การแทนที่สมการที่เหลือด้วยเศษที่เหลือก่อนหน้าสามารถทำต่อไปได้เรื่อย ๆ จนกว่าจะถึงจำนวนนับเดิม ''a'' และ ''b''

: 
: 
: 

หลังจากแทนที่ส่วนที่เหลือทั้งหมด ''r''<sub>0</sub>, ''r''<sub>1</sub>, ... สมการสุดท้ายจะแสดงให้เห็นว่า ''g'' เป็นผลรวมเชิงเส้นของ ''a'' และ ''b'' คือ ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb'' จากเอกลักษณ์ของเบซู อัลกอริธึมข้างต้นจึงสามารถเขียนในรูปทั่วไปของได้

== หมายเหตุ ==

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

## อ้างอิง

## บรรณานุกรม
* 
* 
* 
* 
* . See also Vorlesungen über Zahlentheorie
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 

## แหล่งข้อมูลอื่น

หมวดหมู่:ทฤษฎีจำนวน