ขั้นตอนวิธีแบบยุคลิดและทฤษฎีจำนวน

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง ขั้นตอนวิธีแบบยุคลิดและทฤษฎีจำนวน

ขั้นตอนวิธีแบบยุคลิด vs. ทฤษฎีจำนวน

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

จำนวนเต็ม

ำนวนเต็ม คือจำนวนที่สามารถเขียนได้โดยปราศจากองค์ประกอบทางเศษส่วนหรือทศนิยม ตัวอย่างเช่น 21, 4, −2048 เหล่านี้คือจำนวนเต็ม แต่ 9.75, 5, √2 เหล่านี้ไม่ใช่จำนวนเต็ม เศษของจำนวนเต็มเป็นเศษย่อยของจำนวนจริง และประกอบด้วยจำนวนธรรมชาติ (1, 2, 3,...) ศูนย์ (0) และตัวผกผันการบวกของจำนวนธรรมชาติ (−1, −2, −3,...) เซตของจำนวนเต็มทั้งหมดมักแสดงด้วย Z ตัวหนา (หรือ \mathbb ตัวหนาบนกระดานดำ, U+2124) มาจากคำในภาษาเยอรมันว่า Zahlen แปลว่าจำนวน จำนวนเต็ม (พร้อมด้วยการดำเนินการการบวก) ก่อร่างเป็นกรุปเล็กที่สุดอันประกอบด้วยโมนอยด์เชิงการบวกของจำนวนธรรมชาติ จำนวนเต็มก่อให้เกิดเซตอนันต์นับได้เช่นเดียวกับจำนวนธรรมชาติ สิ่งเหล่านี้ในทฤษฎีจำนวนเชิงพีชคณิตทำให้เข้าใจได้โดยสามัญว่า จำนวนเต็มซึ่งฝังตัวอยู่ในฟีลด์ของจำนวนตรรกยะ หมายถึง จำนวนเต็มตรรกยะ เพื่อแยกแยะออกจากจำนวนเต็มเชิงพีชคณิตที่ได้นิยามไว้กว้างกว.

ขั้นตอนวิธีแบบยุคลิดและจำนวนเต็ม · จำนวนเต็มและทฤษฎีจำนวน · ดูเพิ่มเติม »

ทฤษฎีบทมูลฐานของเลขคณิต

ทฤษฎีบทมูลฐานของเลขคณิต หรือ ทฤษฎีบทการแยกตัวประกอบได้อย่างเดียว (fundamental theorem of arithmetic หรือ unique factorization theorem) ในคณิตศาสตร์และทฤษฎีจำนวน คือประโยคซึ่งกล่าวว่า จำนวนเต็มบวกทุกจำนวนที่มากกว่า 1 สามารถเขียนอยู่ในรูปผลคูณของจำนวนเฉพาะได้วิธีเดียวเท่านั้น ตัวอย่างเช่น เราสามารถเขียน และไม่มีทางที่จะแยกตัวประกอบของ 6936 หรือ 1200 ได้เป็นอย่างอื่น ถ้าเราไม่สนใจลำดับของตัวประกอบ เพื่อที่จะให้ทฤษฏีบทนี้ใช้ได้กับจำนวน 1 เราจะถือว่า 1 เป็นผลคูณของของจำนวนเฉพาะศูนย์จำนวน (ดูใน ผลคูณว่าง).

ขั้นตอนวิธีแบบยุคลิดและทฤษฎีบทมูลฐานของเลขคณิต · ทฤษฎีจำนวนและทฤษฎีบทมูลฐานของเลขคณิต · ดูเพิ่มเติม »