จำนวนเฉพาะ
ในคณิตศาสตร์ จำนวนเฉพาะ (อังกฤษ: prime number) คือ จำนวนเต็มบวกที่มากกว่า 1 และมีตัวหารที่เป็นบวกอยู่ 2 ตัว คือ 1 กับตัวมันเอง ตรงข้ามกับจำนวนประกอบ
ลำดับของจำนวนเฉพาะเริ่มต้นด้วย
ในเดือนธันวาคม พ.ศ. 2561 มีข่าวจำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบ ซึ่งมีความยาว 24,862,048 หลัก[1]
การแทนจำนวนธรรมชาติ ด้วยผลคูณของจำนวนเฉพาะ
แก้ทฤษฎีบทมูลฐานของเลขคณิตกล่าวว่า จำนวนเต็มบวกทุกตัวสามารถเขียนได้ในรูปผลคูณของจำนวนเฉพาะ และเขียนได้แบบเดียวเท่านั้น จำนวนเฉพาะเป็นเหมือน "บล็อกก่อสร้าง" ของจำนวนธรรมชาติ ตัวอย่างเช่น
ไม่ว่าเราจะแยกตัวประกอบของ 23244 แบบใดโดยไม่คำนึงถึงลำดับของตัวประกอบแล้ว มันก็จะไม่ต่างไปจากนี้
สมบัติมูลฐาน
แก้การแยกตัวประกอบได้อย่างเดียว
แก้- ถ้า p เป็นจำนวนเฉพาะ และ p หาร ab ลงตัวแล้ว p หาร a ลงตัว หรือ p หาร b ลงตัว ประพจน์นี้พิสูจน์โดยยุคลิด และมีชื่อเรียกว่า บทตั้งของยุคลิด ใช้ในการพิสูจน์เรื่องการแยกตัวประกอบได้อย่างเดียว
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
การมีอยู่นับไม่ถ้วน
แก้มีจำนวนเฉพาะอยู่มากมายนับไม่ถ้วน ข้อเท็จจริงนี้พร้อมบทพิสูจน์ปรากฏเป็นครั้งแรกในหนังสือ Elements โดยยุคลิด จึงได้ชื่อว่าทฤษฎีบทของยุคลิด
บทพิสูจน์ของยุคลิดนั้นเริ่มต้นโดยพิสูจน์ว่า[2] รายการจำกัด ของจำนวนเฉพาะใด ๆ จะมีจำนวนเฉพาะอื่นที่ไม่อยู่ในลำดับนี้ แนวคิดหลักของบทพิสูจน์นี้คือ คูณจำนวนเฉพาะ ในรายการทุกตัวเข้าด้วยกัน แล้วบวกหนึ่งให้กับผลคูณที่ได้ ซึ่งจะได้เป็นจำนวนใหม่
โดยทฤษฎีบทหลักมูลของเลขคณิต จะได้ว่าจำนวนนี้ต้องแยกตัวประกอบเป็นผลคูณของจำนวนเฉพาะได้
( อาจะมีตัวประกอบเป็นจำนวนเฉพาะตัวเดียวหรือหลายตัวก็ได้ และตัวประกอบเฉพาะเหล่านั้นอาจซ้ำกันก็ได้) แต่เนื่องจากจำนวนเฉพาะใด ๆ ในรายการ เมื่อนำไปหาร แล้วจะหารไม่ลงตัวเสมอ ดังนั้น ตัวประกอบเฉพาะ ของ ต้องเป็นจำนวนเฉพาะอื่นนอกเหนือจากในรายการ จึงทำให้ได้ทันทีว่า มีจำนวนเฉพาะอยู่เป็นอนันต์
นอกจากบทพิสูจน์ของยูคลิดแล้ว ยังมีบทพิสูจน์ว่าจำนวนเฉพาะมีเป็นอนันต์ในแบบอื่น ๆ อีก เช่น บทพิสูจน์ของออยเลอร์โดยใช้วิธีการทางคณิตวิเคราะห์ บทพิสูจน์ของคริสเตียน ก็อลท์บัคโดยอาศัยจำนวนแฟร์มา[3] บทพิสูจน์เชิงทอพอโลยีของฮิลแลล ฟัวร์ทสเตนแบร์ก[4] และบทพิสูจน์ของเอิร์นส์ คุมเมอร์[5]
การหาจำนวนเฉพาะ
แก้ตะแกรงเอราทอสเทนีส และ ตะแกรงของ Atkin เป็นวิธีที่ใช้สร้างรายการจำนวนเฉพาะทั้งหมดตามจำนวนที่กำหนดอย่างรวดเร็ว
ในทางปฏิบัติ เราต้องการตรวจสอบว่าเลขที่กำหนดให้ว่าเป็นจำนวนเฉพาะหรือไม่ มากกว่าจะสร้างรายการจำนวนเฉพาะทั้งหมดขึ้นมา ซึ่งวิธีที่ทดสอบ จะให้คำตอบด้วยความน่าจะเป็น เราสามารถตรวจสอบเลขที่มีขนาดใหญ่ (มี 1 พันหลักขึ้นไป) ว่าเป็นจำนวนเฉพาะหรือไม่ได้อย่างรวดเร็ว โดยใช้การทดสอบความเป็นจำนวนเฉพาะด้วยความน่าจะเป็น (probabilistic primality tests) ซึ่งวิธีนี้ จะต้องทำการสุ่มตัวเลขขึ้นมาตัวหนึ่ง เรียกว่า "พยาน" (witness) และใช้สูตรที่เกี่ยวข้องกับพยาน และจำนวนเฉพาะ N ทำการทดสอบ หลังจากที่ทดสอบไปหลายรอบ เราจะตอบได้ว่า N เป็น "จำนวนประกอบอย่างแน่นอน" หรือ N "อาจเป็นจำนวนเฉพาะ" วิธีทดสอบไม่สามารถให้คำตอบได้ว่าเป็นจำนวนเฉพาะอย่างแน่นอนหรือไม่ การทดสอบบางครั้ง เมื่อใส่จำนวนประกอบลงไป ก็ให้คำตอบว่า "อาจเป็นจำนวนเฉพาะ" เสมอ ไม่ว่าจะเลือกพยานตัวใดก็ตาม จำนวนเหล่านี้เรียกว่า จำนวนเฉพาะเทียม (pseudoprimes) สำหรับการทดสอบ
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
สมบัติเชิงวิเคราะห์
แก้พีชคณิตนามธรรม
แก้สาขาเลขคณิตมอดุลาร์และฟีลด์จำกัด
แก้- ถ้า p เป็นจำนวนเฉพาะ และ a เป็นจำนวนเต็มใดๆแล้ว ap − a หารด้วย p ลงตัว (ทฤษฎีบทน้อยของแฟร์มาต์)
- จำนวนเต็ม p > 1 เป็นจำนวนเฉพาะ ก็ต่อเมื่อ (p − 1) ! + 1 หารด้วย p ลงตัว (ทฤษฎีบทของวิลสัน) ยิ่งไปกว่านั้น จำนวนเต็ม n > 4 เป็นจำนวนประกอบ ก็ต่อเมื่อ (n− 1) ! หารด้วย n ลงตัว
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
การประยุกต์
แก้จำนวนเฉพาะที่มีขนาดใหญ่มาก (ใหญ่กว่า 10100) นำไปใช้ประโยชน์ในขั้นตอนวิธีเข้ารหัสลับแบบกุญแจสาธารณะ นอกจากนี้ยังใช้ในตารางแฮช (hash tables) และเครื่องสุ่มเลขเทียม
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
ดูเพิ่ม
แก้อ้างอิง
แก้- ↑ "GIMPS Project Discovers Largest Known Prime Number: 282,589,933-1". Mersenne Research, Inc. 21 December 2018. สืบค้นเมื่อ 21 December 2018.
- ↑ Euclid's Elements : all thirteen books complete in one volume : the Thomas L. Heath translation. Santa Fe, N.M.: Green Lion Press. ISBN 9781888009194.
- ↑ จดหมาย จากก็อลท์บัคถึงออยเลอร์, กรกฎาคม ค.ศ. 1730.
- ↑ Furstenberg, Harry (May 1955). "On the Infinitude of Primes". The American Mathematical Monthly. 62 (5): 353. doi:10.2307/2307043. ISSN 0002-9890.
- ↑ Ribenboim, Paulo. The little book of bigger primes (2nd ed.). New York: Springer. ISBN 978-0-387-20169-6.
แหล่งข้อมูลอื่น
แก้- Caldwell, Chris, The Prime Pages at primes.utm.edu.
- Prime Numbers at MathWorld
- Prime sequencing technologies เก็บถาวร 2008-04-13 ที่ เวย์แบ็กแมชชีน
- 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 เก็บถาวร 2006-09-25 ที่ เวย์แบ็กแมชชีน
- EFF Cooperative Computing Awards
- 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 เก็บถาวร 2009-08-14 ที่ เวย์แบ็กแมชชีน — Generates a given number of primes above a given start number.
- Primes from WIMS is an online prime generator.
- Huge database of prime numbers