จำนวนเฉพาะ

ลำดับของจำนวนเฉพาะเริ่มต้นด้วย

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ... (ลำดับ  A000040)

ในเดือนธันวาคม พ.ศ. 2561 มีข่าวจำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบ ซึ่งมีความยาว 24,862,048 หลัก

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

${\displaystyle 23244=2^{2}\times 3\times 13\times 149}$ 

ไม่ว่าเราจะแยกตัวประกอบของ 23244 แบบใดโดยไม่คำนึงถึงลำดับของตัวประกอบแล้ว มันก็จะไม่ต่างไปจากนี้

การแยกตัวประกอบได้อย่างเดียว

• ถ้า p เป็นจำนวนเฉพาะ และ p หาร ab ลงตัวแล้ว p หาร a ลงตัว หรือ p หาร b ลงตัว ประพจน์นี้พิสูจน์โดยยุคลิด และมีชื่อเรียกว่า บทตั้งของยุคลิด ใช้ในการพิสูจน์เรื่องการแยกตัวประกอบได้อย่างเดียว

การมีอยู่นับไม่ถ้วน

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

บทพิสูจน์ของยุคลิดนั้นเริ่มต้นโดยพิสูจน์ว่า รายการจำกัด ${\displaystyle p_{1},p_{2},\dotsc ,p_{n}}$  ของจำนวนเฉพาะใด ๆ จะมีจำนวนเฉพาะอื่นที่ไม่อยู่ในลำดับนี้ แนวคิดหลักของบทพิสูจน์นี้คือ คูณจำนวนเฉพาะ ${\displaystyle p_{1},p_{2},\dotsc ,p_{n}}$  ในรายการทุกตัวเข้าด้วยกัน แล้วบวกหนึ่งให้กับผลคูณที่ได้ ซึ่งจะได้เป็นจำนวนใหม่

${\displaystyle N=p_{1}\cdot p_{2}\dotsb p_{n}+1}$ 

โดยทฤษฎีบทหลักมูลของเลขคณิต จะได้ว่าจำนวนนี้ต้องแยกตัวประกอบเป็นผลคูณของจำนวนเฉพาะได้

${\displaystyle N=q_{1}\cdot q_{2}\dotsb q_{m}}$ 

(${\displaystyle N}$  อาจะมีตัวประกอบเป็นจำนวนเฉพาะตัวเดียวหรือหลายตัวก็ได้ และตัวประกอบเฉพาะเหล่านั้นอาจซ้ำกันก็ได้) แต่เนื่องจากจำนวนเฉพาะใด ๆ ในรายการ ${\displaystyle p_{1},p_{2},\dotsc ,p_{n}}$  เมื่อนำไปหาร ${\displaystyle N}$  แล้วจะหารไม่ลงตัวเสมอ ดังนั้น ตัวประกอบเฉพาะ ${\displaystyle q_{1},q_{2}\dotsc ,q_{m}}$  ของ ${\displaystyle N}$  ต้องเป็นจำนวนเฉพาะอื่นนอกเหนือจากในรายการ ${\displaystyle p_{1},p_{2},\dotsc ,p_{n}}$  จึงทำให้ได้ทันทีว่า มีจำนวนเฉพาะอยู่เป็นอนันต์

นอกจากบทพิสูจน์ของยูคลิดแล้ว ยังมีบทพิสูจน์ว่าจำนวนเฉพาะมีเป็นอนันต์ในแบบอื่น ๆ อีก เช่น บทพิสูจน์ของออยเลอร์โดยใช้วิธีการทางคณิตวิเคราะห์ บทพิสูจน์ของคริสเตียน ก็อลท์บัคโดยอาศัยจำนวนแฟร์มา บทพิสูจน์เชิงทอพอโลยีของฮิลแลล ฟัวร์ทสเตนแบร์ก และบทพิสูจน์ของเอิร์นส์ คุมเมอร์

การหาจำนวนเฉพาะ

ตะแกรงเอราทอสเทนีส และ ตะแกรงของ Atkin เป็นวิธีที่ใช้สร้างรายการจำนวนเฉพาะทั้งหมดตามจำนวนที่กำหนดอย่างรวดเร็ว

ในทางปฏิบัติ เราต้องการตรวจสอบว่าเลขที่กำหนดให้ว่าเป็นจำนวนเฉพาะหรือไม่ มากกว่าจะสร้างรายการจำนวนเฉพาะทั้งหมดขึ้นมา ซึ่งวิธีที่ทดสอบ จะให้คำตอบด้วยความน่าจะเป็น เราสามารถตรวจสอบเลขที่มีขนาดใหญ่ (มี 1 พันหลักขึ้นไป) ว่าเป็นจำนวนเฉพาะหรือไม่ได้อย่างรวดเร็ว โดยใช้การทดสอบความเป็นจำนวนเฉพาะด้วยความน่าจะเป็น (probabilistic primality tests) ซึ่งวิธีนี้ จะต้องทำการสุ่มตัวเลขขึ้นมาตัวหนึ่ง เรียกว่า "พยาน" (witness) และใช้สูตรที่เกี่ยวข้องกับพยาน และจำนวนเฉพาะ N ทำการทดสอบ หลังจากที่ทดสอบไปหลายรอบ เราจะตอบได้ว่า N เป็น "จำนวนประกอบอย่างแน่นอน" หรือ N "อาจเป็นจำนวนเฉพาะ" วิธีทดสอบไม่สามารถให้คำตอบได้ว่าเป็นจำนวนเฉพาะอย่างแน่นอนหรือไม่ การทดสอบบางครั้ง เมื่อใส่จำนวนประกอบลงไป ก็ให้คำตอบว่า "อาจเป็นจำนวนเฉพาะ" เสมอ ไม่ว่าจะเลือกพยานตัวใดก็ตาม จำนวนเหล่านี้เรียกว่า จำนวนเฉพาะเทียม (pseudoprimes) สำหรับการทดสอบ

สาขาเลขคณิตมอดุลาร์และฟีลด์จำกัด

• ถ้า p เป็นจำนวนเฉพาะ และ a เป็นจำนวนเต็มใดๆแล้ว a^p − a หารด้วย p ลงตัว (ทฤษฎีบทน้อยของแฟร์มาต์)
• จำนวนเต็ม p > 1 เป็นจำนวนเฉพาะ ก็ต่อเมื่อ (p − 1) ! + 1 หารด้วย p ลงตัว (ทฤษฎีบทของวิลสัน) ยิ่งไปกว่านั้น จำนวนเต็ม n > 4 เป็นจำนวนประกอบ ก็ต่อเมื่อ (n− 1) ! หารด้วย n ลงตัว

จำนวนเฉพาะที่มีขนาดใหญ่มาก (ใหญ่กว่า 10¹⁰⁰) นำไปใช้ประโยชน์ในขั้นตอนวิธีเข้ารหัสลับแบบกุญแจสาธารณะ นอกจากนี้ยังใช้ในตารางแฮช (hash tables) และเครื่องสุ่มเลขเทียม

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