จำนวนเฉพาะ

[thumb|[จำนวนประกอบสามารถสร้างเป็นสี่เหลี่ยมผืนผ้าที่ทุกด้านยาวมากกว่า 1 ได้ แต่จำนวนเฉพาะทำไม่ได้]]
ในคณิตศาสตร์ **จำนวนเฉพาะ** () คือ จำนวนเต็มบวกที่มากกว่า 1 และมีตัวหารที่เป็นบวกอยู่ 2 ตัว คือ 1 กับตัวมันเอง ตรงข้ามกับจำนวนประกอบ

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

:: 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, ... 

 จำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบซึ่งเป็นจำนวนเฉพาะแมร์แซนมีความยาว 41,024,320 หลัก

## การแทนจำนวนธรรมชาติ ด้วยผลคูณของจำนวนเฉพาะ

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

:23244 = 2^2 \times 3 \times 13 \times 149

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

## สมบัติมูลฐาน

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

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

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

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

:  N =  p_1\cdot p_2\dotsb p_n + 1

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

:  N = q_1 \cdot q_2 \dotsb q_m

(N อาจะมีตัวประกอบเป็นจำนวนเฉพาะตัวเดียวหรือหลายตัวก็ได้ และตัวประกอบเฉพาะเหล่านั้นอาจซ้ำกันก็ได้) แต่เนื่องจากจำนวนเฉพาะใด ๆ ในรายการ p_1, p_2, \dotsc, p_n เมื่อนำไปหาร  N  แล้วจะหารไม่ลงตัวเสมอ ดังนั้น ตัวประกอบเฉพาะ  q_1, q_2 \dotsc, q_m ของ  N  ต้องเป็นจำนวนเฉพาะอื่นนอกเหนือจากในรายการ 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* ลงตัว

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

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

## อ้างอิง

## แหล่งข้อมูลอื่น

* Caldwell, Chris, The Prime Pages at primes.utm.edu.
* Prime Numbers at MathWorld
* Prime sequencing technologies  
* MacTutor history of prime numbers
* The prime puzzles
* An English translation of Euclid's proof that there are infinitely many primes
* Number Spiral with prime patterns
* An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier 
* EFF Cooperative Computing Awards
* *[http://demonstrations.wolfram.com/WhyANumberIsPrime/ Why a Number Is Prime]* by Enrique Zeleny, The Wolfram Demonstrations Project.

### คำนวณและสร้างจำนวนเฉพาะ
* Online Prime Number Generator and Checker - instantly checks and finds prime numbers up to 128 digits long (does NOT require Java or Javascript)
* Prime number calculator — Check prime number, and find next largest and next smallest prime numbers (requires Javascript).
* Fast Online primality test — Dario Alpern's personal site – Makes use of the Elliptic Curve Method (up to thousands digits numbers check!, requires Java)
* Prime Number Generator  — Generates a given number of primes above a given start number.
* Primes from WIMS is an online prime generator.
* Huge database of prime numbers


หมวดหมู่:จำนวนเต็ม
หมวดหมู่:ทฤษฎีจำนวน