จำนวนเฉพาะ

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา
จำนวนประกอบสามารถสร้างเป็นสี่เหลี่ยมผืนผ้าได้ แต่จำนวนเฉพาะทำไม่ได้

ในคณิตศาสตร์ จำนวนเฉพาะ (อังกฤษ: 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... (ลำดับ OEISA000040)

ในเดือนธันวาคม 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) และเครื่องสุ่มเลขเทียม

อ้างอิง[แก้]

  1. "GIMPS Project Discovers Largest Known Prime Number: 282,589,933-1". Mersenne Research, Inc. 21 December 2018. สืบค้นเมื่อ 21 December 2018.
  2. Euclid's Elements : all thirteen books complete in one volume : the Thomas L. Heath translation. Santa Fe, N.M.: Green Lion Press. ISBN 9781888009194.
  3. จดหมาย จากก็อลท์บัคถึงออยเลอร์, กรกฎาคม ค.ศ. 1730.
  4. Furstenberg, Harry (May 1955). "On the Infinitude of Primes". The American Mathematical Monthly. 62 (5): 353. doi:10.2307/2307043.
  5. Ribenboim, Paulo. The little book of bigger primes (2nd ed.). New York: Springer. ISBN 978-0-387-20169-6.

แหล่งข้อมูลอื่น[แก้]

คำนวณและสร้างจำนวนเฉพาะ[แก้]