จำนวนเฉพาะ

จากวิกิพีเดีย สารานุกรมเสรี

ในคณิตศาสตร์ จำนวนเฉพาะ คือ จำนวนธรรมชาติที่มีตัวหารที่เป็นบวกอยู่ 2 ตัว คือ 1 และตัวมันเอง. จำนวนประกอบ คือ จำนวนธรรมชาติที่มีตัวหารที่เป็นบวก นอกเหนือจาก 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...

(ลำดับ A000040 [1] ใน สารานุกรมออนไลน์ของลำดับจำนวนเต็ม (On-Line Encyclopedia of Integer Sequences) ดูบทความ รายการของจำนวนเฉพาะ สำหรับจำนวนเฉพาะ 500 จำนวนแรก)

เซตของจำนวนเฉพาะทั้งหมดมักเขียนแทนด้วย ซึ่งเป็นตัวอักษร P ใหญ่แบบกระดานดำ เนื่องจาก 2 เป็นจำนวนเฉพาะตัวเดียวที่เป็นเลขคู่ ดังนั้นคำว่า จำนวนเฉพาะคี่ จะถูกใช้เพื่อหมายถึงจำนวนเฉพาะทั้งหมดที่ไม่ใช่ 2

สารบัญ 1 การแทนจำนวนธรรมชาติ ด้วยผลคูณของจำนวนเฉพาะ 2 มีจำนวนเฉพาะอยู่จำนวนเท่าไร? 3 การค้นหาจำนวนเฉพาะ 4 สมบัติบางประการของจำนวนเฉพาะ 5 จำนวนเฉพาะที่ใหญ่ที่สุดเท่าที่รู้ 6 การประยุกต์ 7 ช่องว่างระหว่างจำนวนเฉพาะ 8 คำคม

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

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

ไม่ว่าเราจะแยกตัวประกอบของ 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 ลงตัว ประพจน์นี้พิสูจน์โดยยุคลิด และมีชื่อเรียกว่า บทตั้งของยุคลิด ใช้ในการพิสูจน์เรื่องการแยกตัวประกอบได้อย่างเดียว
• ริง (ดูที่เลขคณิตมอดุลาร์) Z/nZ เป็นฟิลด์ ก็ต่อเมื่อ n เป็นจำนวนเฉพาะ
• ถ้า p เป็นจำนวนเฉพาะ และ a เป็นจำนวนเต็มใดๆแล้ว a^p − a หารด้วย p ลงตัว (ทฤษฎีบทน้อยของแฟร์มาต์)
• จำนวนเต็ม p > 1 เป็นจำนวนเฉพาะ ก็ต่อเมื่อ (p − 1)! + 1 หารด้วย p ลงตัว (ทฤษฎีบทของวิลสัน). บทกลับ, จำนวนเต็ม n > 4 เป็นจำนวนประกอบ ก็ต่อเมื่อ (n − 1)! หารด้วย n ลงตัว
• ถ้า n เป็นจำนวนเต็มบวกแล้ว จะมีจำนวนเฉพาะ p ที่ n < p < 2n (สัจพจน์ของเบอร์แทรนด์)
• สำหรับจำนวนเฉพาะ p > 2 จะมีจำนวนธรรมชาติ n ที่ทำให้ p = 4n ± 1
• สำหรับจำนวนเฉพาะ p > 3 จะมีจำนวนธรรมชาติ n ที่ทำให้ p = 6n ± 1

[แก้] จำนวนเฉพาะที่ใหญ่ที่สุดเท่าที่รู้

จำนวนเฉพาะที่ใหญ่ที่สุดเท่าที่รู้ตั้งแต่กันยายน พ.ศ. 2548 คือ 2^25964951 − 1 (ตัวเลขนี้มีความยาว 7,816,230 หลัก) มันเป็นจำนวนเฉพาะ Mersenneตัวที่ 42 M_25964951 ถูกค้นพบเมื่อวันที่ 18 กุมภาพันธ์ พ.ศ. 2548 โดยMartin Nowak สมาชิกที่มีบทบาทของ GIMPS

จำนวนเฉพาะที่ใหญ่ที่สุดเท่าที่รู้รองลงมา คือ 2^24036583 − 1 (ตัวเลขนี้มีความยาว 7,235,733 หลัก) มันเป็นจำนวนเฉพาะ Mersenneตัวที่ 41 M_24036583 ถูกค้นพบเมื่อวันที่ 15 พฤษภาคม พ.ศ. 2547 โดยJosh Findley (สมาชิกของ GIMPS) และประกาศในปลายเดือนพฤษภาคม พ.ศ. 2547

จำนวนเฉพาะที่ใหญ่เป็นอันดับสามเท่าที่รู้ คือ 2^20996011 − 1 (ตัวเลขนี้มีความยาว 6,320,430 หลัก) มันเป็นจำนวนเฉพาะ Mersenneตัวที่ 40 M_20996011 ถูกค้นพบเมื่อวันที่ 17 พฤศจิกายน พ.ศ. 2546 โดยMichael Shafer (และ GIMPS) และประกาศในต้นเดือนธันวาคม พ.ศ. 2546

[แก้] การประยุกต์

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

[แก้] ช่องว่างระหว่างจำนวนเฉพาะ

ให้ p_n คือจำนวนเฉพาะตัวที่ n (นั่นคือ p₁ = 2, p₂ = 3, ...) ช่องว่าง g_n ระหว่างจำนวนเฉพาะ p_n กับ p_{n + 1} คือจำนวนของจำนวนประกอบที่อยู่ระหว่างนั้น นั่นคือ

g_n = p_{n + 1} − p_n − 1

เราจะได้ g₁ = 0, g₂ = g₃ = 1, และ g₄ = 3 ลำดับ {g_n} ของช่องว่างระหว่างจำนวนเฉพาะ เป็นลำดับที่มีการศึกษากันอย่างมาก

สำหรับ N ใดๆ,

(N + 1)! + 2, (N + 1)! + 3, ..., (N + 1)! + N + 1

เป็นลำดับของจำนวนประกอบที่ติดกัน N ตัว ดังนั้น เราสามารถสร้างช่องว่างระหว่างจำนวนเฉพาะให้มีขนาดใหญ่เท่าใดก็ได้ นั่นคือ สำหรับจำนวน N ใดๆ จะมีจำนวนเต็ม n ซึ่ง g_n > N (เลือก n ที่ทำให้ p_n มีค่ามากที่สุด และน้อยกว่า (N + 1)! + 2) หรือกล่าวได้ว่า ช่องว่างระหว่างจำนวนเฉพาะใดๆ มีค่าน้อยมากเมื่อเทียบกับจำนวนเฉพาะ ดังนั้น g_n/p_n จึงมีค่าเข้าใกล้ 0 เมื่อ n เข้าใกล้อนันต์

เราจะกล่าวว่า g_n เป็นช่องว่างใหญ่สุด (maximal gap) ถ้า g_m < g_n สำหรับทุก m < n ช่องว่างใหญ่สุดที่มีค่ามากสุดเท่าที่รู้ในตอนนี้คือ ค้นพบโดย T. Nicely และ B. Nyman ในปี พ.ศ. 2542 มันเป็นช่องว่างใหญ่สุดที่เล็กเป็นอันดับที่ 64 และปรากฏหลังจำนวนเฉพาะ 169318231874637

ช่องว่างระหว่างจำนวนเฉพาะที่ใหญ่ที่สุดเท่าที่รู้ตั้งแต่ 1 มกราคม พ.ศ. 2548 มีขนาด 2254930

ข้อความคาดการณ์จำนวนเฉพาะคู่แฝดกล่าวว่า มี n ที่ทำให้ g_n = 1 อยู่ไม่จำกัด

[แก้] คำคม

"นักคณิตศาสตร์ได้พยายามอย่างไร้ประโยชน์ในการค้นหาลำดับบางอย่างของจำนวนเฉพาะ และพวกเราเชื่อว่ามันเป็นความลึกลับที่มนุษย์ไม่เคยเข้าใจ" — เลออนฮาร์ด ออยเลอร์

"พระเจ้าไม่ได้ทอยลูกเต๋า แต่มีบางอย่างที่แปลกประหลาดเกิดขึ้นกับจำนวนเฉพาะ" — พอล แอร์ดิช