การหารลงตัวและจำนวนเฉพาะ

การหารลงตัว ตัวหารร่วมมาก และจำนวนเฉพาะเป็นรากฐานของทฤษฎีจำนวน: จำนวนเต็มทุกจำนวนสร้างขึ้นจากการคูณของจำนวนเฉพาะ และวิธีการสร้างนี้เป็นตัวกำหนดผลลัพธ์เกือบทั้งหมดในภายหลัง

Definition

จำนวนเต็ม a หาร b ลงตัว ถ้า b เท่ากับ a คูณด้วยจำนวนเต็มบางจำนวน; จำนวนเฉพาะคือจำนวนเต็มที่มากกว่าหนึ่งซึ่งมีตัวหารที่เป็นบวกเพียงแค่หนึ่งและตัวมันเองเท่านั้น การหารลงตัวและจำนวนเฉพาะเกี่ยวข้องกับการแยกตัวประกอบเชิงการคูณของจำนวนเต็มและหน่วยการสร้างที่ไม่สามารถลดทอนได้ของการแยกตัวประกอบนั้น

Scope

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

Core questions

• อัลกอริทึมแบบยุคลิดคำนวณตัวหารร่วมมากและให้เอกลักษณ์ของเบซูต์ได้อย่างไร?
• เหตุใดบทตั้งของยุคลิดจึงบังคับให้การแยกตัวประกอบเป็นจำนวนเฉพาะมีเพียงหนึ่งเดียว?
• จะพิสูจน์ได้อย่างไรว่ามีจำนวนเฉพาะเป็นอนันต์ และการพิสูจน์ดังกล่าวเผยให้เห็นอะไรบ้าง?
• จำนวนเฉพาะมีการกระจายตัวอย่างไรในหมู่จำนวนเต็ม และการตัดสินความเป็นจำนวนเฉพาะในทางปฏิบัติทำได้อย่างไร?

Key theories

ขั้นตอนวิธีการหารและอัลกอริทึมแบบยุคลิด

จำนวนเต็มใดๆ ที่หารด้วยจำนวนเต็มบวก จะได้ผลหารและเศษที่เฉพาะเจาะจง; การทำซ้ำขั้นตอนนี้จะให้ตัวหารร่วมมาก และโดยการแทนค่าย้อนกลับ จะได้จำนวนเต็มที่แสดงเป็นผลรวมเชิงเส้น (เอกลักษณ์ของเบซูต์)

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

จำนวนเต็มทุกจำนวนที่มากกว่าหนึ่งเป็นผลคูณของจำนวนเฉพาะซึ่งมีเพียงหนึ่งเดียวเมื่อไม่คำนึงถึงลำดับ; บทตั้งของยุคลิด (จำนวนเฉพาะที่หารผลคูณลงตัวจะหารตัวประกอบตัวใดตัวหนึ่งลงตัว) เป็นขั้นตอนสำคัญ

ความเป็นอนันต์ของจำนวนเฉพาะ

ข้อโต้แย้งแบบคลาสสิกของยุคลิดแสดงให้เห็นว่าไม่มีรายการจำนวนเฉพาะที่จำกัดใดสมบูรณ์; สูตรผลคูณของออยเลอร์สำหรับฟังก์ชันซีตาให้การพิสูจน์เชิงวิเคราะห์และวัดความหนาแน่นของจำนวนเฉพาะผ่านการลู่ออกของผลรวมส่วนกลับของจำนวนเฉพาะ

Clinical relevance

การแยกตัวประกอบอย่างรวดเร็วและการทดสอบความเป็นจำนวนเฉพาะเป็นรากฐานของการเข้ารหัส: ความปลอดภัยของ RSA ขึ้นอยู่กับความยากในการแยกตัวประกอบผลคูณขนาดใหญ่ของจำนวนเฉพาะสองจำนวน ในขณะที่การทดสอบความเป็นจำนวนเฉพาะที่มีประสิทธิภาพ (เช่น Miller-Rabin) ทำให้การสร้างคีย์เป็นไปได้ในทางปฏิบัติ

History

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

Key figures

• Euclid
• Eratosthenes
• Leonhard Euler
• Etienne Bezout

Seminal works

• hardyWright2008

Frequently asked questions

หนึ่งเป็นจำนวนเฉพาะหรือไม่?

ไม่ หนึ่งถูกยกเว้นตามคำจำกัดความเพื่อให้การแยกตัวประกอบเฉพาะมีเพียงหนึ่งเดียว; หากหนึ่งนับเป็นจำนวนเฉพาะ ทุกจำนวนจะมีวิธีการแยกตัวประกอบเป็นอนันต์

เอกลักษณ์ของเบซูต์ใช้ทำอะไร?

เอกลักษณ์นี้ระบุว่าตัวหารร่วมมากของจำนวนเต็มสองจำนวนคือผลรวมเชิงเส้นของจำนวนเต็มเหล่านั้น ซึ่งเป็นพื้นฐานสำหรับการคำนวณส่วนกลับมอดุโลและการแก้สมการไดโอแฟนไทน์เชิงเส้น