จำนวนเฉพาะ

                    จำนวนเฉพาะ  

จำนวนเฉพาะ หมายถึง จำนวนนับที่มากกว่า 1 ซึ่งมีตัวประกอบเพียงสองตัว คือ 1 และตัวเอง

นักคณิตศาสตร์ชาวกรีก  ชื่อ  เอราโตสเทเนส (Eratosthenes)  เป็นผู้คิดวิธีการหาจำนวนเฉพาะจากจำนวนนับ  ตั้งแต่ 1 ถึง n ด้วยวิธีการตัดจำนวนนับที่ไม่เป็นจำนวนเฉพาะทิ้ง เราเรียกวิธีการนี้ว่า ตะแกรงของเอราโตสเทเนส (The Sieve of Eratosthenes)
            วิธีการของตะแกรงของเอราโตสเทเนส

1. 1 ไม่ใช่จำนวนฉพาะตัดทิ้ง
2. 2 เป็นจำนวนเฉพาะ ให้วงกลมรอบล้อม
3. ตัดจำนวนนับที่มี 2 เป็นตัวประกอบทิ้ง
4. 3 เป็นจำนวนเฉพาะ ให้วงกลมรอบล้อม
5. ตัดจำนวนนับที่มี 3 เป็นตัวประกอบทิ้ง
6. 5 เป็นจำนวนเฉพาะ ให้วงกลมรอบล้อม
7. ตัดจำนวนนับที่มี 5 เป็นตัวประกอบทิ้ง
8. 7 เป็นจำนวนเฉพาะ ให้วงกลมรอบล้อม
9. ตัดจำนวนนับที่มี 7 เป็นตัวประกอบทิ้ง
10. จำนวนนับที่เหลือจากการตัดทิ้งทั้งหมด เป็นจำนวนเฉพาะ
11. ดำเนินการเช่นนี้ไปเรื่อย ๆ ตัวอย่าง ลำดับของจำนวนเฉพาะเริ่มต้นด้วย 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... การแทนจำนวนธรรมชาติ ด้วยผลคูณของจำนวนเฉพาะ

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

    ไม่ว่าเราจะแยกตัวประกอบของ 23244 แบบใดโดยไม่คำนึงถึงลำดับของตัวประกอบแล้ว มันก็จะไม่ต่างไปจากนี้ มีจำนวนเฉพาะอยู่จำนวนเท่าไร? มีจำนวนเฉพาะอยู่เป็นจำนวนมากโดยหาค่ามิได้ บทพิสูจน์ที่เก่าแก่ที่สุดสำหรับประโยคนี้ คิดขึ้นโดยนักคณิตศาสตร์ชาวกรีกชื่อ ยุคลิด ในหนังสือ Elements (Book IX, Proposition 20) ยุคลิดกล่าวในหนังสือของเขาว่า "มีจำนวนเฉพาะ มากกว่าจำนวนเฉพาะ[จำนวนจำกัด]ที่กำหนดให้" บทพิสูจน์ของเขาสามารถสรุปย่อๆได้ว่า: ให้ดูจำนวนเฉพาะมีจำนวนจำกัด ซึ่งเรากำหนดว่ามันเป็นจำนวนเฉพาะที่มีอยู่ทั้งหมด คูณจำนวนทั้งหมดเข้าด้วยกันและ บวก 1 ผลลัพธ์ที่ได้จะไม่สามารถหารด้วยจำนวนเฉพาะใดๆใสสนเซตได้ เพราะว่าไม่ว่าจะหารด้วยตัวใดก็จะเหลือเศษ 1 ดังนั้น มันจะต้องเป็นจำนวนเฉพาะ หรืออาจจะมีจำนวนเฉพาะที่หารมันลงตัวแต่ไม่ได้อยู่ในเซตจำกัดนี้ ดังนั้น เซตนี้ไม่ได้มีจำนวนเฉพาะทั้งหมด การค้นหาจำนวนเฉพาะ ตะแกรงเอราทอสเทนีส และ ตะแกรงของ Atkin เป็นวิธีที่ใช้สร้างรายการจำนวนเฉพาะทั้งหมดตามจำนวนที่กำหนดอย่างรวดเร็ว ในทางปฏิบัติ เราต้องการตรวจสอบว่าเลขที่กำหนดให้ว่าเป็นจำนวนเฉพาะหรือไม่ มากกว่าจะสร้างรายการจำนวนเฉพาะทั้งหมดขึ้นมา ซึ่งวิธีที่ทดสอบ จะให้คำตอบด้วยความน่าจะเป็น เราสามารถตรวจสอบเลขที่มีขนาดใหญ่ (มี 1 พันหลักขึ้นไป) ว่าเป็นจำนวนเฉพาะหรือไม่ได้อย่างรวดเร็ว โดยใช้การทดสอบความเป็นจำนวนเฉพาะด้วยความน่าจะเป็น (probabilistic primality tests) ซึ่งวิธีนี้ จะต้องทำการสุ่มตัวเลขขึ้นมาตัวหนึ่ง เรียกว่า "พยาน" (witness) และใช้สูตรที่เกี่ยวข้องกับพยาน และจำนวนเฉพาะ N ทำการทดสอบ หลังจากที่ทดสอบไปหลายรอบ เราจะตอบได้ว่า N เป็น"จำนวนประกอบอย่างแน่นอน" หรือ N "อาจเป็นจำนวนเฉพาะ" วิธีทดสอบไม่สามารถให้คำตอบได้ว่าเป็นจำนวนเฉพาะอย่างแน่นอนหรือไม่ การทดสอบบางครั้ง เมื่อใส่จำนวนประกอบลงไป ก็ให้คำตอบว่า"อาจเป็นจำนวนเฉพาะ"เสมอ ไม่ว่าจะเลือกพยานตัวใดก็ตาม จำนวนเหล่านี้เรียกว่า จำนวนเฉพาะเทียม (pseudoprimes) สำหรับการทดสอบ

       จำนวนเฉพาะที่มากที่สุดเท่าที่รู้ตั้งแต่ ธันวาคม พ.ศ. 2549 คือ 230402457 − 1 (ตัวเลขนี้มีความยาว 9,152,052 หลัก) มันเป็นจำนวนเฉพาะแมร์กแซนตัวที่ 43 M30402457 ถูกค้นพบเมื่อวันที่ 15 ธันวาคม พ.ศ. 2549 โดยดร.สตีเฟน บูนและ ดร.เคอร์ติส คูเปอร์ สมาชิกของ GIMPS
    
    

    จำนวนเฉพาะที่มากที่สุดเท่าที่รู้รองลงมากันยายน พ.ศ. 2548 คือ 225964951 − 1 (ตัวเลขนี้มีความยาว 7,816,230 หลัก) มันเป็นจำนวนเฉพาะแมร์กแซนตัวที่ 42 M25964951 ถูกค้นพบเมื่อวันที่ 18 กุมภาพันธ์ พ.ศ. 2548 โดยMartin Nowak สมาชิกที่มีบทบาทของ GIMPS จำนวนเฉพาะที่มากที่สุดเท่าที่รู้รองลงมา คือ 224036583 − 1 (ตัวเลขนี้มีความยาว 7,235,733 หลัก) มันเป็นจำนวนเฉพาะแมร์กแซนตัวที่ 41 M24036583 ถูกค้นพบเมื่อวันที่ 15 พฤษภาคม พ.ศ. 2547 โดยJosh Findley (สมาชิกของ GIMPS) และประกาศในปลายเดือนพฤษภาคม พ.ศ. 2547 จำนวนเฉพาะที่มากเป็นอันดับสามเท่าที่รู้ คือ 220996011 − 1 (ตัวเลขนี้มีความยาว 6,320,430 หลัก) มันเป็นจำนวนเฉพาะแมร์กแซนตัวที่ 40 M20996011 ถูกค้นพบเมื่อวันที่ 17 พฤศจิกายน พ.ศ. 2546 โดยMichael Shafer (และ GIMPS) และประกาศในต้นเดือนธันวาคม พ.ศ. 2546

จำนวนประกอบ คือ จำนวนธรรมชาติที่มีตัวหารที่เป็นบวก นอกเหนือจาก 1 และตัวมันเอง

ตัวอย่างเช่น  10  เกิดจาก 2 x 5
       30  เกิดจาก 2 x 3 x 5
       42  เกิดจาก 2 x 3 x 7

มีอีกมากมายขอให้ทำความเข้าใจ