ขั้นตอนวิธีแบบยุคลิด
![]() | ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |

ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด (อังกฤษ: 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] สมบัตินี้เรียกว่าเอกลักษณ์ของเบซู
พื้นฐาน — ตัวหารร่วมมาก[แก้]
ขั้นตอนวิธีแบบยุคลิดคำนวณค่าตัวหารร่วมมาก (หรม.) ของจำนวนธรรมชาติสองจำนวน a และ b ค่าตัวหารร่วมมาก g เป็นจำนวนธรรมชาติค่ามากสุดที่หารทั้ง a และ b ลงตัว คำที่มีความหมายเหมือนกับ หรม. ได้แก่ ตัวประกอบร่วมค่ามากสุด (อังกฤษ: greatest common factor, GCF), ตัวประกอบร่วมค่ามากสุด (อังกฤษ: highest common factor, HCF) และ greatest common measure (GCM) ตัวหารร่วมมากมักเขียนแทนด้วย gcd(a, b) หรือ (a, b),[3] แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ
ถ้า gcd(a, b) = 1 แล้ว a กับ b เป็นจำนวนเฉพาะสัมพัทธ์[4] ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า a หรือ b เป็นจำนวนเฉพาะเองแต่อย่างใด[5] เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6 = 2 × 3 and 35 = 5 × 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 1, สี่เหลี่ยมจัตุรัส 2 2, สี่เหลี่ยมจัตุรัส 3 3, สี่เหลี่ยมจัตุรัส 4 4, สี่เหลี่ยมจัตุรัส 66 หรือสี่เหลี่ยมจัตุรัส 12 12 ดังนั้น 12 คือตัวหารร่วมมากของ 24 และ 60 โดยสี่เหลี่ยมผืนผ้ากว้าง 24 ยาว 60 สามารถแบ่งเป็นตารางของสี่เหลี่ยมจัตุรัสยาวด้านละ 12 ที่มีสี่เหลี่ยมจัตุรัส 2 รูปติดด้านกว้าง (24/12 = 2) และสี่เหลี่ยมจัตุรัส 5 รูปติดด้านยาว (60/12 = 5)
ตัวหารร่วมมากของสองจำนวน a และ b คือผลคูณของตัวประกอบเฉพาะที่สองจำนวนนี้มีร่วมกัน โดยตัวประกอบเฉพาะหนึ่งค่าสามารถนำมาคูณได้หลายรอบ ตราบที่ผลคูณของตัวประกอบเหล่านี้หาร a และ b ลงตัว ตัวอย่างเช่น 1386 แยกตัวประกอบได้เป็น 2 3 3 7 11 และ 3213 แยกตัวประกอบได้เป็น 3 3 3 7 17 ตัวหารร่วมมากของ 1386 และ 3213 จึงเท่ากับ 63 = 3 3 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 เป็นแบบนี้ไปเรื่อย ๆ
แต่ละขั้นตอนเริ่มด้วยเศษสองจำนวนที่มีค่าไม่เป็นลบ rk−1 และ rk−2 เนื่องจากวิธีการนี้จะทำให้เศษมีค่าลดลงในทุกขั้นตอนเสมอ rk−1 มีค่าน้อยกว่าเศษตัวก่อน rk−2 เป้าหมายของขั้นตอนที่ k คือหาผลหาร qk และเศษ rk ที่สอดคล้องกับสมการ
จะได้ว่า 0 ≤ rk < rk−1 กล่าวได้ว่า จำนวนที่มากกว่า rk−2 ถูกลบด้วยพหุคูณของจำนวนที่น้อยกว่า rk−1 จนกว่าเศษ rk จะมีค่าน้อยกว่า rk−1
ในขั้นแรก (k = 0) เศษ r−2 และ r−1 มีค่าเท่ากับ a และ b ตามลำดับ ในขั้นต่อมา (k = 1) เศษมีค่าเท่ากับ b และเศษ r0 ของขั้นแรก ทำแบบนี้ต่อไปเรื่อย ๆ ขั้นตอนวิธีดังกล่าวเขียนออกมาในรูปแบบลำดับของสมการได้ว่า
ถ้า a มีค่าน้อยกว่า b ให้สลับตัวเลขในขั้นแรก ตัวอย่างคือ ถ้า a < b ผลหารในขั้นแรก q0 จะมีค่าเท่ากับศูนย์ และเศษ r0 มีค่าเท่ากับ a ดังนั้น rk จะมีค่าน้อยกว่า rk−1 สำหรับทุก k ≥ 0
เพราะเศษมีค่าลดลงในทุกขั้นตอน แต่ไม่สามารถเป็นมีค่าเป็นลบ เศษ rN จึงจะต้องเท่ากับศูนย์ในสักขั้นตอน
การพิสูจน์ความถูกต้อง[แก้]
ความถูกต้องของขั้นตอนวิธีแบบยูคลิดสามารถพิสูจน์ได้โดยสองขั้นตอน ในขั้นตอนแรก เห็นได้ว่าเศษตัวสุดท้ายที่ไม่เท่ากับศูนย์ rN−1 จะหารทั้ง a และ b ลงตัว เพราะมันเป็นตัวหารร่วม จึงมีค่าน้อยกว่าหรือเท่ากับตัวหารร่วมมาก g และในขั้นตอนที่สอง เห็นได้ว่าตัวหารร่วมใด ๆ ของ a และ b (รวมถึงตัวหารร่วมมาก g ด้วย) ต้องหาร rN−1 ลงตัว ดังนั้น g ต้องมีค่าน้อยกว่าหรือเท่ากับ rN−1 ข้อสรุปสองอันนี้ไม่แน่นอน เว้นแต่ rN−1 = g
เพื่อแสดงให้เห็น
- rN−2 = qN rN−1
เพราะ
- rN−3 = qN−1 rN−2 + rN−1
ตัวอย่างการใช้งาน[แก้]

เพื่อให้เห็นภาพ ขั้นตอนวิธีแบบยุคลิดสามารถนำมาใช้หาตัวหารร่วมมากของ a = 1071 และ b = 462 ได้ เริ่มต้นด้วย นำ 1071 เป็นตัวตั้ง ลบกับตัวคูณของ 462 จนกว่าเศษจะน้อยกว่า 462 ซึ่งเมื่อพิจารณาแล้ว การคูณด้วย 2 นั้นสามารถนำมาใช้ในการลบออกได้ (q0 = 2) โดยมีเศษคือ 147
- 1071 = 2 × 462 + 147.
ต่อมา ตัวคูณของ 147 จะถูกลบออกจาก 462 จนกว่าเศษจะมีค่าน้อยกว่า 147 เมื่อพิจารณาแล้ว การคูณด้วย 3 นั้นสามารถนำมาใช้ในการลบออกได้
- 462 = 3 × 147 + 21.
ต่อมา ตัวคูณของ 21 จะถูกลบออกจาก 147 จนกว่าเศษจะมีค่าน้อยกว่า 21 ซึ่งการคูณด้วย 7 นั้นสามารถนำมาใช้ในการลบออกได้ (q2 = 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; อัลกอริทึมจบลง |
การอธิบายเป็นภาพ[แก้]
เราสามารถทำขั้นตอนวิธีแบบยูคลิดให้เห็นภาพได้ โดยใช้วิธีคล้ายกับการปูกระเบื้องในการหาตัวหารร่วมมาก[6] สมมุติว่าเราต้องการปูพื้นที่สี่เหลี่ยมผืนผ้าขนาด โดยใช้กระเบื้องสี่เหลี่ยมจัตุรัส โดยที่ a เป็นค่าที่มีค่ามากกว่าอีกจำนวน เริ่มแรก เราจะปูโดยใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด แต่ว่า กลับเหลือพื้นที่ที่ปูไม่ได้ มีขนาดเป็น โดยที่ เราก็เลยเปลี่ยนไปใช้กระเบื้องสี่เหลี่ยมจัตุรัสขนาด แทน แต่ก็ยังปูพื้นที่ได้ไม่ครบอีก เหลือพื้นที่เป็น เราก็เลยเปลี่ยนไปใช้กระเบื้องขนาด แทน ทำแบบนี้ซ้ำไปเรื่อย ๆ จนกระทั่งไม่เหลือพื้นที่ที่ยังไม่ได้ปู นั่นคือ เมื่อกระเบื้องสี่เหลียมจัตุรัสสามารถปูพื้นที่ที่ยังไม่ได้ปูในขั้นที่แล้วได้ทั้งหมด โดยความยาวของด้านของสี่เหลี่ยมจัตุรัสที่เล็กที่สุดก็คือตัว ห.ร.ม. ของขนาดของสี่เหลี่ยมรูปต้นแบบนั่นเอง เช่น กระเบื้องสี่เหลี่ยมจัตุรัสขนาดเล็กที่สุดในรูปคือ (ในรูปแสดงโดยใช้สีแดง) และ 21 เป็นตัวหารร่วมมากของ 1071 และ 462 ซึ่งเป็นรูปสี่เหลี่ยมต้นฉบับ (แสดงโดยใช้สีเขียว)
การหารแบบยูคลิด[แก้]
ในทุกขั้นตอน
- rk−2 = qk rk−1 + rk
- rk = rk−2 mod rk−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
ในรูปแบบเรียกซ้ำ[7] จะขึ้นอยู่กับความเท่ากันของตัวหารร่วมมากของเศษเหลือต่อเนื่อง โดยมีเงื่อนไขการหยุดคือ gcd(rN−1, 0) = rN−1
function gcd(a, b) if b = 0 return a else return gcd(b, a mod b)
(หากค่าที่รับมาเป็นลบ หรือฟังก์ชัน mod อาจให้ค่าที่ติดลบ ต้องเปลี่ยน "return a" เป็น "return max(a, −a)")
หมายเหตุ[แก้]
- ก. ^ ตำราบางเล่มที่ใช้โดยทั่วไป เช่น Topics in Algebra ของ I. N. Herstein และ Algebra ของ Serge Langใช้คำว่า "Euclidean algorithm" หมายถึงวิธีหารแบบยุคลิด
อ้างอิง[แก้]
- ↑ Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
- ↑ http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf
- ↑ Stark 1978, p. 16
- ↑ Stark 1978, p. 21
- ↑ LeVeque 1996, p. 32
- ↑ Kimberling, C. (1983). "A Visual Euclidean Algorithm". Mathematics Teacher. 76: 108–109.
- ↑ Stillwell 1997, p. 14