ในวิชาคณิตศาสตร์ ขั้นตอนวิธีแบบยุคลิด (อังกฤษ : Euclidean Algorithm )[a] ขั้นตอนวิธีของยุคลิด เป็นวิธีคำนวณตัวหารร่วมมาก (หรม.) ของจำนวนเต็มสองจำนวน ตั้งชื่อตามยุคลิด นักคณิตศาสตร์ ชาวกรีก ผู้อธิบายทฤษฎีนี้ในอิลิเมนต์ของยุคลิด เล่ม 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 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 ลงตัว เพราะไม่มีตัวประกอบเฉพาะร่วมกัน
หมายเหตุ ก. ^ Topics in Algebra ของ I. N. Herstein และ Algebra ของ Serge Langใช้คำว่า "Euclidean algorithm" หมายถึงวิธีหารแบบยุคลิด
อ้างอิง
นตอนว, แบบย, คล, งก, ามภาษา, ในบทความน, ไว, ให, านและผ, วมแก, ไขบทความศ, กษาเพ, มเต, มโดยสะดวก, เน, องจากว, เด, ยภาษาไทยย, งไม, บทความด, งกล, าว, กระน, ควรร, บสร, างเป, นบทความโดยเร, วท, ดในว, ชาคณ, ตศาสตร, งกฤษ, euclidean, algorithm, หร, อข, นตอนว, ของย, คล, . lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudinwichakhnitsastr khntxnwithiaebbyukhlid xngkvs Euclidean Algorithm a hruxkhntxnwithikhxngyukhlid epnwithikhanwntwharrwmmak hrm khxngcanwnetmsxngcanwn tngchuxtamyukhlid nkkhnitsastrchawkrikphuxthibaythvsdiniinxiliemntkhxngyukhlidelm VII aela X 1 withikhxngyukhlidsahrbhatwharrwmmak hrm khxngkhwamyawerimtn BA aela DC sungtangniyamihepnphhukhunkhxngkhwamyaw hnwy ediywkn ephraawa DC snkwacungich wd BA aetephiyngkhrngediywephraaess EA nxykwa CD ich EA wdkhwamyaw DC thisnkwasxngkhrng caehluxess FC snkwa EA aelwich FC wdkhwamyaw EA samkhrng ephraawakhntxnniimmiess cungcbodymi FC epn hrm dankhwaepntwxyangkhxngniokhmakhsodycanwn 49 aela 21 ihphllphthkhatwharrwmmakepn 7 prayuktcak Heath 1908 300 twharrwmmakkhxngcanwnetmsxngcanwnkhuxcanwnmakthisudthiharthngsxngidodyimehluxessrupxyangngaythisudkhxngkhntxnwithiaebbyukhliderimdwycanwnetmbwkkhuhnung aelasrangcanwnkhuhnungthiprakxbdwycanwnthinxykwaaelaphltangrahwangcanwnthngsxng krabwnkarthasacncanwnthngsxngethakn canwnsudthayepntwharrwmmakkhxngcanwnetmbwkthikhntxnerimhlkkarsakhykhux hrm imepliynkhathanacanwnthinxykwalbcanwnthimakkwa echn hrm khxng 252 aela 105 ethakb hrm khxng 147 252 105 aela 105 ephraawacanwnthimakkwathukld karthawithinisathaihidcanwnelklng karsanicungcbxyangaennxnemuxthngsxngcanwnmikhaethakn thathaxikhnungkhrng canwnidcanwnhnungcaepn 0 hlkthanekiywkbkhntxnwithiaebbyukhlidphbinhnngsux Elements khxngyukhlid inchwngstwrrsthi 3 kxnkhristkal thaihepnkhntxnwithiekaaekthisudekiywkbcanwnthiyngichodythwip khntxnwithichbbdngedimichsahrbcanwnthrrmchatiaelakhwamyawechingerkhakhnit canwncring aetnkkhnitsastridkhyaykarichnganipyngcanwnchnidxun echn canwnetmekasesiynaelaphhunamhnungtwaepr xnnaipsuaenwkhidechingphichkhnitnamthrrmsmyihm echnodemnaebbyukhlid khntxnwithikhxngyukhlididnaipichkbokhrngsrangthangkhnitsastrxun echn enguxn aelaphhunamhlaytwaeprkhntxnwithinimikarprayuktichinthangthvsdiaelaptibti xacichkxkaenidcnghwadntrithisakhyhlayrupaebbthiphbinwthnthrrmtang thwolk 2 khntxnwithiniepnswnprakxbsakhykhxngkarekharhsxarexsex karekharhslbaebbkuyaecxsmmatrthiichthwipinkarphanichyxielkthrxniks khntxnwithiniichaeksmkaridoxaefnithn echnkarhacanwnthisxdkhlxngkbsmphakhhlaychud thvsdibthessehluxkhxngcin hrux twphkphnkarkhunkhxngestcakd aelayngsamarthichsrangessswntxenuxngdwywithioskhxngsetirmsahrbharakcanwncringkhxngphhunam aelainkhntxnwithikaraeyktwprakxbkhxngcanwnetmsmyihm thisakhy epnekhruxngmuxsahrbphisucnthvsdibthinthvsdicanwnsmyihm echnthvsdibthphlrwmkalngsxngkhxnglakrxngcaelathvsdibthmulthankhxngelkhkhnitthaprbprungkhntxnwithiihichessharcakwithiharaebbyukhlidaethnthicaepnkarlb khntxnwithikhxngyukhlidkhanwnkhatwharrwmmakkhxngcanwnkhnadihyxyangmiprasiththiphaph khntxnwithiniimichkhntxnkarharcanwnmakkwahaethakhxngcanwnhlk sahrbelkhthansib khxngcanwnkhnadelkkwa ody Gabriel Lame phisucnemuxpi kh s 1844 aelarierimkarsuksa thvsdikhwamsbsxninkarkhanwn withiephimprasiththiphaphkhxngkhntxnwithiidphthnainkhriststwrrsthi 20emuxyxnkhntxnwithiaebbyukhlid twharrwmmaksamarthekhiyninrupphlrwmechingesnkhxngsxngcanwnthinamadaeninkar aetlacanwnkhunkbcanwnetm echn twharrwmmakkhxng 252 aela 105 khux 21 aela21 5 105 2 252 smbtinieriykwaexklksnkhxngebsuphunthan twharrwmmak aekikhdubthkhwamhlkthi twharrwmmak khntxnwithiaebbyukhlidkhanwnkhatwharrwmmak hrm khxngcanwnthrrmchatisxngcanwn a aela b khatwharrwmmak g epncanwnthrrmchatikhamaksudthiharthng a aela b lngtw khathimikhwamhmayehmuxnkb hrm idaek twprakxbrwmkhamaksud xngkvs greatest common factor GCF twprakxbrwmkhamaksud xngkvs highest common factor HCF aela greatest common measure GCM twharrwmmakmkekhiynaethndwy hrm a b hrux a b 3 aemwasylksnaebbhlngichsahrbkhwamkhidrwbyxdthangkhnitsastrxikhlayxyang echn ewketxrphikdsxngmititha hrm a b 1 aelw a kb b epncanwnechphaasmphthth 4 khwamepncanwnechphaasmphththimidbngbxkwa a hrux b epncanwnechphaaexngaetxyangid 5 echn 6 aela 35 tangimichcanwnechphaa ephraatangmitwprakxbechphaacanwnlasxngtw 6 2 3 and 35 5 7 xyangirktam 6 aela 35 epncanwnechphaasmphthth immicanwnthrrmchatinxkehnuxcak 1 harthng 6 aela 35 lngtw ephraaimmitwprakxbechphaarwmknhmayehtu aekikhk tarabangelmthiichodythwip echn Topics in Algebra khxng I N Herstein aela Algebra khxng Serge Langichkhawa Euclidean algorithm hmaythungwithiharaebbyukhlidxangxing aekikh 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 32ekhathungcak https th wikipedia org w index php title khntxnwithiaebbyukhlid amp oldid 5820996, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ , อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
