ดูต้นฉบับสำหรับ จำนวนเฉพาะ

[[ไฟล์:Primes-vs-composites.svg|thumb|[[จำนวนประกอบ]]สามารถสร้างเป็นสี่เหลี่ยมผืนผ้าที่ทุกด้านยาวมากกว่า 1 ได้ แต่[[จำนวนเฉพาะ]]ทำไม่ได้]]
ใน[[คณิตศาสตร์]] '''จำนวนเฉพาะ''' ({{langx|en|prime number}}) คือ [[จำนวนเต็มบวก]]ที่มากกว่า 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 ตัวเลข|127]], [[131 ตัวเลข|131]], [[137 ตัวเลข|137]], [[139 ตัวเลข|139]], [[149 ตัวเลข|149]], [[151 ตัวเลข|151]], [[157 ตัวเลข|157]], [[163 ตัวเลข|163]], [[167 ตัวเลข|167]], [[173 ตัวเลข|173]], [[179 ตัวเลข|179]], [[181 ตัวเลข|181]], [[191 ตัวเลข|191]], [[193 ตัวเลข|193]], [[197 ตัวเลข|197]], [[199 ตัวเลข|199]], ... {{OEIS|id=A000040}}
{{main|รายชื่อจำนวนเฉพาะ}}
ในเดือนธันวาคม พ.ศ. 2561 มีข่าว[[จำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบ]] ซึ่งมีความยาว 24,862,048 หลัก<ref name="GIMPS-2018">{{cite web |title=GIMPS Project Discovers Largest Known Prime Number: 2<sup>82,589,933</sup>-1 |url=https://www.mersenne.org/primes/press/M82589933.html |date=21 December 2018 |work=Mersenne Research, Inc. |access-date=21 December 2018 }}</ref>

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

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

:<math>23244 = 2^2 \times 3 \times 13 \times 149</math>

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

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

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

{{โครงส่วน}}

=== การมีอยู่นับไม่ถ้วน ===
{{หลัก|ทฤษฎีบทของยุคลิด}}

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

บทพิสูจน์ของยุคลิดนั้นเริ่มต้นโดยพิสูจน์ว่า<ref>{{cite book |title=Euclid's Elements : all thirteen books complete in one volume : the Thomas L. Heath translation |publisher=Green Lion Press |location=Santa Fe, N.M. |isbn=9781888009194}}</ref> รายการจำกัด <math>p_1, p_2, \dotsc, p_n</math> ของจำนวนเฉพาะใด ๆ จะมีจำนวนเฉพาะอื่นที่ไม่อยู่ในลำดับนี้ แนวคิดหลักของบทพิสูจน์นี้คือ คูณจำนวนเฉพาะ  <math>p_1, p_2, \dotsc, p_n</math> ในรายการทุกตัวเข้าด้วยกัน แล้วบวกหนึ่งให้กับผลคูณที่ได้ ซึ่งจะได้เป็นจำนวนใหม่

: <math> N =  p_1\cdot p_2\dotsb p_n + 1</math>

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

: <math> N = q_1 \cdot q_2 \dotsb q_m</math>

(<math>N</math> อาจะมีตัวประกอบเป็นจำนวนเฉพาะตัวเดียวหรือหลายตัวก็ได้ และตัวประกอบเฉพาะเหล่านั้นอาจซ้ำกันก็ได้) แต่เนื่องจากจำนวนเฉพาะใด ๆ ในรายการ <math>p_1, p_2, \dotsc, p_n</math> เมื่อนำไปหาร <math> N </math> แล้วจะหารไม่ลงตัวเสมอ ดังนั้น ตัวประกอบเฉพาะ <math> q_1, q_2 \dotsc, q_m</math> ของ <math> N </math> ต้องเป็นจำนวนเฉพาะอื่นนอกเหนือจากในรายการ <math>p_1, p_2, \dotsc, p_n</math> จึงทำให้ได้ทันทีว่า มีจำนวนเฉพาะอยู่เป็นอนันต์

นอกจากบทพิสูจน์ของยูคลิดแล้ว ยังมีบทพิสูจน์ว่าจำนวนเฉพาะมีเป็นอนันต์ในแบบอื่น ๆ อีก เช่น บทพิสูจน์ของ[[เลออนฮาร์ด ออยเลอร์|ออยเลอร์]]โดยใช้วิธีการทาง[[คณิตวิเคราะห์]] บทพิสูจน์ของ[[คริสเตียน ก็อลท์บัค]]โดยอาศัย[[จำนวนแฟร์มา]]<ref>[http://www.math.dartmouth.edu/~euler/correspondence/letters/OO0722.pdf จดหมาย] จากก็อลท์บัคถึงออยเลอร์, กรกฎาคม ค.ศ. 1730.</ref> บทพิสูจน์เชิง[[ทอพอโลยี]]ของ[[ฮิลแลล ฟัวร์ทสเตนแบร์ก]]<ref>{{cite journal |last1=Furstenberg |first1=Harry |title=On the Infinitude of Primes |url=https://archive.org/details/sim_american-mathematical-monthly_1955-05_62_5/page/n53 |journal=The American Mathematical Monthly |date=May 1955 |volume=62 |issue=5 |pages=353 |doi=10.2307/2307043|issn = 0002-9890}}</ref> และบทพิสูจน์ของ[[เอิร์นส์ คุมเมอร์]]<ref>{{cite book |last1=Ribenboim |first1=Paulo |title=The little book of bigger primes |year=2004 |url=https://archive.org/details/littlebookofbigg0000ribe |publisher=Springer |location=New York |isbn=978-0-387-20169-6 |edition=2nd}}</ref>

=== การหาจำนวนเฉพาะ ===
{{บทความหลัก|ช่องว่างจำนวนเฉพาะ}}

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

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

== สมบัติเชิงวิเคราะห์ ==

== พีชคณิตนามธรรม ==

=== สาขาเลขคณิตมอดุลาร์และฟีลด์จำกัด ===
* ถ้า ''p'' เป็นจำนวนเฉพาะ และ ''a'' เป็นจำนวนเต็มใดๆแล้ว ''a''<sup>''p''</sup> − ''a'' หารด้วย ''p'' ลงตัว ([[ทฤษฎีบทน้อยของแฟร์มาต์]])
* จำนวนเต็ม ''p'' > 1 เป็นจำนวนเฉพาะ ก็ต่อเมื่อ (''p'' − 1) ! + 1 หารด้วย ''p'' ลงตัว ([[ทฤษฎีบทของวิลสัน]]) ยิ่งไปกว่านั้น จำนวนเต็ม ''n'' > 4 เป็นจำนวนประกอบ ก็ต่อเมื่อ (''n''− 1) ! หารด้วย ''n'' ลงตัว
{{โครงส่วน}}

== การประยุกต์ ==
จำนวนเฉพาะที่มีขนาดใหญ่มาก (ใหญ่กว่า 10<sup>100</sup>) นำไปใช้ประโยชน์ในขั้นตอนวิธี[[วิทยาการเข้ารหัสลับ|เข้ารหัสลับแบบกุญแจสาธารณะ]] นอกจากนี้ยังใช้ใน[[ตารางแฮช]] (hash tables) และ[[เครื่องสุ่มเลขเทียม]]
{{โครงส่วน}}
== ดูเพิ่ม ==
*[[การพิสูจน์ว่าผลรวมของส่วนกลับของจำนวนเฉพาะทั้งหมดลู่ออก]] <!--ยังสามารถใช้กับ n/จำนวนเฉพาะ ไม่ใช่แค่ 1/จำนวนเฉพาะ-->
*[[การพิสูจน์สูตรผลคูณของออยเลอร์สำหรับฟังก์ชันซีตาของรีมันน์]]

== อ้างอิง ==
{{รายการอ้างอิง}}

== แหล่งข้อมูลอื่น ==
{{วิกิคำคม|จำนวนเฉพาะ}}
* Caldwell, Chris, The [[Prime Pages]] at [http://primes.utm.edu/ primes.utm.edu].
* [http://mathworld.wolfram.com/topics/PrimeNumbers.html Prime Numbers at MathWorld]
* [http://www.quikstream.com.au/primenumbers.html Prime sequencing technologies] {{Webarchive|url=https://web.archive.org/web/20080413141436/http://www.quikstream.com.au/primenumbers.html |date=2008-04-13 }} 
* [http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html MacTutor history of prime numbers]
* [http://www.primepuzzles.net/ The prime puzzles]
* [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html An English translation of Euclid's proof that there are infinitely many primes]
* [http://www.numberspiral.com/index.html Number Spiral with prime patterns]
* [http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier] {{Webarchive|url=https://web.archive.org/web/20060925090553/http://www.maths.ex.ac.uk/~mwatkins/zeta/vardi.html |date=2006-09-25 }}
* [https://web.archive.org/web/20040604053354/http://www.eff.org/awards/coop.php EFF Cooperative Computing Awards]
* ''[http://demonstrations.wolfram.com/WhyANumberIsPrime/ Why a Number Is Prime]'' by Enrique Zeleny, [[The Wolfram Demonstrations Project]].

=== คำนวณและสร้างจำนวนเฉพาะ ===
* [http://www.numberempire.com/primenumbers.php Online Prime Number Generator and Checker] - instantly checks and finds prime numbers up to 128 digits long (does NOT require Java or Javascript)
* [http://www.easycalculation.com/prime-number.php Prime number calculator] — Check prime number, and find next largest and next smallest prime numbers (requires Javascript).
* [http://www.alpertron.com.ar/ECM.HTM Fast Online primality test — Dario Alpern's personal site] – Makes use of the Elliptic Curve Method (up to thousands digits numbers check!, requires Java)
* [http://publicliterature.org/tools/prime_number_generator Prime Number Generator] {{Webarchive|url=https://web.archive.org/web/20090814005741/http://publicliterature.org/tools/prime_number_generator/ |date=2009-08-14 }} — Generates a given number of primes above a given start number.
* [http://wims.unice.fr/wims/wims.cgi?module=tool/number/primes.en Primes] from WIMS is an online prime generator.
* [http://www.bigprimes.net/archive/prime.php Huge database of prime numbers]

{{ตัวหารจำนวนเต็ม}}

[[หมวดหมู่:จำนวนเฉพาะ| ]]
[[หมวดหมู่:จำนวนเต็ม]]
[[หมวดหมู่:ทฤษฎีจำนวน]]