ขั้นตอนวิธีแบบยุคลิด
 |
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด
|
ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด (อังกฤษ: 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) ตัวหารร่วมมากมักเขียนแทนด้วย หรม.(a, b) หรือ (a, b),[3] แม้ว่าสัญลักษณ์แบบหลังใช้สำหรับความคิดรวบยอดทางคณิตศาสตร์อีกหลายอย่าง เช่น เวกเตอร์พิกัดสองมิติ
ถ้า หรม.(a, b) = 1 แล้ว a กับ b เป็นจำนวนเฉพาะสัมพัทธ์[4] ความเป็นจำนวนเฉพาะสัมพัทธ์ไม่ได้บ่งบอกว่า a หรือ b เป็นจำนวนเฉพาะเองแต่อย่างใด[5] เช่น 6 และ 35 ต่างไม่ใช่จำนวนเฉพาะ เพราะต่างมีตัวประกอบเฉพาะจำนวนละสองตัว: 6 = 2 × 3 and 35 = 5 × 7 อย่างไรก็ตาม 6 และ 35 เป็นจำนวนเฉพาะสัมพัทธ์ ไม่มีจำนวนธรรมชาตินอกเหนือจาก 1 หารทั้ง 6 และ 35 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน
หมายเหตุ[แก้]
- ก. ^ ตำราบางเล่มที่ใช้โดยทั่วไป เช่น 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
