|
0
ใน[[คณิตศาสตร์]] '''จำนวนเฉพาะ''' ([[ภาษาอังกฤษ|อังกฤษ]] : prime number) คือ [[จำนวนธรรมชาติ]]ที่มี[[ตัวหาร]]ที่เป็นบวกอยู่ 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]]...<br />{{OEIS|id=A000040}}
ดูบทความ [[รายชื่อจำนวนเฉพาะ]] สำหรับจำนวนเฉพาะ 500 จำนวนแรก สำหรับเลข 1 ไม่ถือว่าเป็นจำนวนเฉพาะตามนิยาม
เซตของจำนวนเฉพาะทั้งหมดมักเขียนแทนด้วย <math>\mathbb P</math> เนื่องจาก 2 เป็นจำนวนเฉพาะตัวเดียวที่เป็นเลขคู่ ดังนั้นคำว่า '''จำนวนเฉพาะคี่''' จะถูกใช้เพื่อหมายถึงจำนวนเฉพาะทั้งหมดที่ไม่ใช่ 2
== การแทนจำนวนธรรมชาติ ด้วยผลคูณของจำนวนเฉพาะ ==
[[ทฤษฎีบทมูลฐานของเลขคณิต]]กล่าวว่า จำนวนเต็มบวกทุกตัวสามารถเขียนได้ในรูปผลคูณของจำนวนเฉพาะ และเขียนได้แบบเดียวเท่านั้น จำนวนเฉพาะเป็นเหมือน "บล็อกก่อสร้าง"ของจำนวนธรรมชาติ ตัวอย่างเช่น
:<math>23244 = 2^2 \times 3 \times 13 \times 149</math>
ไม่ว่าเราจะแยกตัวประกอบของ 23244 แบบใดโดยไม่คำนึงถึงลำดับของตัวประกอบแล้ว มันก็จะไม่ต่างไปจากนี้
== มีจำนวนเฉพาะอยู่จำนวนเท่าไร? ==
มีจำนวนเฉพาะอยู่มากเป็น[[อนันต์]] บทพิสูจน์ที่เก่าแก่ที่สุดสำหรับประโยคนี้ คิดขึ้นโดยนักคณิตศาสตร์ชาวกรีกชื่อ [[ยุคลิด]] ในหนังสือ ''Elements'' (Book IX, Proposition 20) ยุคลิดกล่าวในหนังสือของเขาว่า "มีจำนวนเฉพาะ มากกว่าจำนวนเฉพาะ[จำนวนจำกัด]ที่กำหนดให้" บทพิสูจน์ของเขาสามารถสรุปย่อๆได้ว่า:
:ให้ดูจำนวนเฉพาะมีจำนวนจำกัด ซึ่งเรากำหนดว่ามันเป็นจำนวนเฉพาะที่มีอยู่ทั้งหมด คูณจำนวนทั้งหมดเข้าด้วยกันและ บวก 1 ผลลัพธ์ที่ได้จะไม่สามารถหารด้วยจำนวนเฉพาะใดๆในเซตได้ เพราะว่าไม่ว่าจะหารด้วยตัวใดก็จะเหลือเศษ 1 ดังนั้น มันจะต้องเป็นจำนวนเฉพาะ หรืออาจจะมีจำนวนเฉพาะที่หารมันลงตัวแต่ไม่ได้อยู่ในเซตจำกัดนี้ ดังนั้น เซตนี้ไม่ได้มีจำนวนเฉพาะทั้งหมด
== การค้นหาจำนวนเฉพาะ ==
[[ตะแกรงเอราทอสเทนีส]] และ [[ตะแกรงของ Atkin]] เป็นวิธีที่ใช้สร้างรายการจำนวนเฉพาะทั้งหมดตามจำนวนที่กำหนดอย่างรวดเร็ว
ในทางปฏิบัติ เราต้องการตรวจสอบว่าเลขที่กำหนดให้ว่าเป็นจำนวนเฉพาะหรือไม่ มากกว่าจะสร้างรายการจำนวนเฉพาะทั้งหมดขึ้นมา ซึ่งวิธีที่ทดสอบ จะให้คำตอบด้วย[[ความน่าจะเป็น]] เราสามารถตรวจสอบเลขที่มีขนาดใหญ่ (มี 1 พันหลักขึ้นไป) ว่าเป็นจำนวนเฉพาะหรือไม่ได้อย่างรวดเร็ว โดยใช้[[การทดสอบความเป็นจำนวนเฉพาะ]]ด้วยความน่าจะเป็น (probabilistic primality tests) ซึ่งวิธีนี้ จะต้องทำการสุ่มตัวเลขขึ้นมาตัวหนึ่ง เรียกว่า "พยาน" (witness) และใช้สูตรที่เกี่ยวข้องกับพยาน และจำนวนเฉพาะ ''N'' ทำการทดสอบ หลังจากที่ทดสอบไปหลายรอบ เราจะตอบได้ว่า ''N'' เป็น"จำนวนประกอบอย่างแน่นอน" หรือ ''N'' "อาจเป็นจำนวนเฉพาะ" วิธีทดสอบไม่สามารถให้คำตอบได้ว่าเป็นจำนวนเฉพาะอย่างแน่นอนหรือไม่ การทดสอบบางครั้ง เมื่อใส่จำนวนประกอบลงไป ก็ให้คำตอบว่า"อาจเป็นจำนวนเฉพาะ"เสมอ ไม่ว่าจะเลือกพยานตัวใดก็ตาม จำนวนเหล่านี้เรียกว่า [[จำนวนเฉพาะเทียม]] (pseudoprimes) สำหรับการทดสอบ
== สมบัติบางประการของจำนวนเฉพาะ ==
* ถ้า ''p'' เป็นจำนวนเฉพาะ และ ''p'' หาร ''ab'' ลงตัวแล้ว ''p'' หาร ''a'' ลงตัว หรือ ''p'' หาร ''b'' ลงตัว ประพจน์นี้พิสูจน์โดยยุคลิด และมีชื่อเรียกว่า ''บทตั้งของยุคลิด'' ใช้ในการพิสูจน์เรื่องการแยกตัวประกอบได้อย่างเดียว
* [[ริง]] (ดูที่[[เลขคณิตมอ/''n'''''Z''' เป็น[[ฟีลด์]] ก็ต่อเมื่อ ''n'' เป็นจำนวนเฉพาะ
* ถ้า ''p'' เป็นจำนวนเฉพาะ และ ''a'' เป็นจำนวนเต็มใดๆแล้ว ''a''<sup>''p''</sup> − ''a'' หารด้วย ''p'' ลงตัว ([[ทฤษฎีบทน้อยของแฟร์มาต์]])
* จำนวนเต็ม ''p'' > 1 เป็นจำนวนเฉพาะ ก็ต่อเมื่อ (''p'' − 1) ! + 1 หารด้วย ''p'' ลงตัว ([[ทฤษฎีบทของวิลสัน]]). บทกลับ, จำนวนเต็ม ''n'' > 4 เป็นจำนวนประกอบ ก็ต่อเมื่อ (''n'' − 1) ! หารด้วย ''n'' ลงตัว
* ถ้า ''n'' เป็นจำนวนเต็มบวกแล้ว จะมีจำนวนเฉพาะ ''p'' ที่ ''n'' < ''p'' < 2''n'' ([[สัจพจน์ของเบอร์แทรนด์]])
* สำหรับจำนวนเฉพาะ ''p'' > 2 จะมีจำนวนธรรมชาติ ''n'' ที่ทำให้ ''p'' = 4''n'' ± 1
* สำหรับจำนวนเฉพาะ ''p'' > 3 จะมีจำนวนธรรมชาติ ''n'' ที่ทำให้ ''p'' = 6''n'' ± 1
== การประยุกต์ ==
จำนวนเฉพาะที่มีขนาดใหญ่มาก (ใหญ่กว่า 10<sup>100</sup>) นำไปใช้ประโยชน์ในขั้นตอนวิธี[[วิทยาการเข้ารหัสลับ|เข้ารหัสลับแบบกุญแจสาธารณะ]] นอกจากนี้ยังใช้ใน[[ตารางแฮช]] (hash tables) และ[[เครื่องสุ่มเลขเทียม]]
== ช่องว่างระหว่างจำนวนเฉพาะ ==
{{บทความหลัก|ช่องว่างจำนวนเฉพาะ}}
ให้ ''p''<sub>''n''</sub> คือจำนวนเฉพาะตัวที่ ''n'' (นั่นคือ ''p''<sub>1</sub> = 2, ''p''<sub>2</sub> = 3, ...) ''ช่องว่าง'' ''g''<sub>''n''</sub> ระหว่างจำนวนเฉพาะ ''p''<sub>''n''</sub> กับ ''p''<sub>''n'' + 1</sub> คือผลต่างของจำนวนเฉพาะสองจำนวนดังกล่าว นั่นคือ
::''g''<sub>''n''</sub> = ''p''<sub>''n'' + 1</sub> − ''p''<sub>''n''</sub>
เราจะได้ ''g''<sub>1</sub> = 3 − 2 = 1, ''g''<sub>2</sub> = 5 − 3 = 2, ''g''<sub>3</sub> = 7 − 5 = 2, และ ''g''<sub>4</sub> = 11 − 7 = 4 ลำดับ ''g''<sub>''n''</sub> ของช่องว่างระหว่างจำนวนเฉพาะ เป็นลำดับที่มีการศึกษากันอย่างมาก
สำหรับจำนวนนับ ''N'' ใดๆ ที่มากกว่า 1
::''N''! + 2, ''N''! + 3, ..., ''N''! + ''N''
เป็นลำดับของจำนวนประกอบที่ติดกัน ''N'' − 1 ตัว ดังนั้น เราสามารถสร้างช่องว่างระหว่างจำนวนเฉพาะให้มีขนาดใหญ่เท่าใดก็ได้ นั่นคือ สำหรับจำนวน ''N'' ใดๆ จะมีจำนวนเต็ม ''n'' ซึ่ง ''g''<sub>''n''</sub> > ''N'' (เลือก ''n'' ที่ทำให้ ''p''<sub>''n''</sub> มีค่ามากที่สุด และน้อยกว่า ''N''! + 2)
ช่องว่างระหว่างจำนวนเฉพาะใดๆ มีค่าน้อยมากเมื่อเทียบกับจำนวนเฉพาะ ดังนั้น ''g''<sub>''n''</sub>/''p''<sub>''n''</sub> จึงมีค่าเข้าใกล้ 0 เมื่อ ''n'' เข้าใกล้อนันต์ [[ข้อความคาดการณ์จำนวนเฉพาะคู่แฝด]]กล่าวว่า มี ''n'' ที่ทำให้ ''g''<sub>''n''</sub> = 2 อยู่ไม่จำกัด
== จำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบ ==
{{บทความหลัก|จำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบ}}
จำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบ ธันวาคม พ.ศ. 2549 คือ 2<sup>43112609</sup> − 1 (ตัวเลขนี้มีความยาว 12,978,189 หลัก) มันเป็น[[จำนวนเฉพาะแมร์แซน]]ตัวที่ 47 (M<sub>43112609</sub>) ถูกค้นพบเมื่อวันที่ [[23 สิงหาคม]] [[พ.ศ. 2551]] โดย [[GIMPS]]
== อ้างอิง ==
* [http://www.manager.co.th/Science/ViewNews.aspx?NewsID=9490000000923 ม.มิสซูรีพบจำนวนเฉพาะขนาดใหญ่ที่สุด 9.1 ล้านหลัก] โดย ผู้จัดการออนไลน์ 5 มกราคม 2549 06:55 น.
* [http://primes.utm.edu/largest.html]
== แหล่งข้อมูลอื่น ==
{{วิกิคำคม|จำนวนเฉพาะ}}
* 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]
* [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]
* [http://web.archive.org/20040604053354/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] — 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]
{{ตัวหารจำนวนเต็ม}}
[[หมวดหมู่:จำนวนเฉพาะ| ]]
| 