จำนวนเฉพาะ: ประวัติศาสตร์และข้อเท็จจริง วิธีค้นหาจำนวนเฉพาะ

ทฤษฎีบท.

จำนวนเฉพาะมีจำนวนอนันต์

การพิสูจน์.

สมมติว่านี่ไม่ใช่กรณี นั่นคือ สมมติว่ามีจำนวนเฉพาะ n ตัวเท่านั้น และจำนวนเฉพาะเหล่านี้คือ p 1, p 2, ..., p n ให้เราแสดงว่าเราสามารถหาจำนวนเฉพาะที่แตกต่างจากที่ระบุได้เสมอ

พิจารณาจำนวน p เท่ากับ p 1 ·p 2 ·…·p n +1 เห็นได้ชัดว่าจำนวนนี้แตกต่างจากจำนวนเฉพาะแต่ละตัว p 1, p 2, ..., p n หากจำนวน p เป็นจำนวนเฉพาะ แสดงว่าทฤษฎีบทนั้นได้รับการพิสูจน์แล้ว ถ้าจำนวนนี้เป็นจำนวนประกอบ ดังนั้นโดยอาศัยทฤษฎีบทที่แล้ว จะมีตัวหารเฉพาะของจำนวนนี้ (เราแสดงว่ามัน p n+1) ให้เราแสดงว่าตัวหารนี้ไม่ตรงกับตัวเลขใดๆ p 1, p 2, ..., p n

หากไม่เป็นเช่นนั้น ตามคุณสมบัติของการหารลงตัว ผลคูณ p 1 ·p 2 ·…·p n จะถูกหารด้วย p n+1 แต่จำนวน p ก็หารด้วย p n+1 ลงตัวเช่นกัน ซึ่งเท่ากับผลรวม p 1 ·p 2 ·…·p n +1 ตามมาว่า p n+1 ต้องหารเทอมที่สองของผลบวกนี้ ซึ่งเท่ากับ 1 แต่เป็นไปไม่ได้

ดังนั้นจึงได้รับการพิสูจน์แล้วว่าสามารถพบจำนวนเฉพาะใหม่ได้เสมอซึ่งไม่รวมอยู่ในจำนวนเฉพาะที่กำหนดไว้ล่วงหน้า จึงมีจำนวนเฉพาะมากมายนับไม่ถ้วน

ดังนั้น เนื่องจากจำนวนเฉพาะมีจำนวนอนันต์ เมื่อรวบรวมตารางจำนวนเฉพาะ คุณจึงจำกัดตัวเองจากด้านบนให้เหลือเพียงจำนวนใดจำนวนหนึ่ง เช่น 100, 1,000, 10,000 เป็นต้น

ตะแกรงเอราทอสเธเนส

ตอนนี้เราจะพูดถึงวิธีสร้างตารางจำนวนเฉพาะ สมมติว่าเราต้องสร้างตารางจำนวนเฉพาะจนถึง 100

วิธีที่ชัดเจนที่สุดในการแก้ปัญหานี้คือการตรวจสอบจำนวนเต็มบวกตามลำดับ โดยเริ่มจาก 2 ถึงลงท้ายด้วย 100 ว่ามีตัวหารบวกที่มากกว่า 1 และน้อยกว่าจำนวนที่ทดสอบ (จากคุณสมบัติการหารลงตัวที่เราทราบ ว่าค่าสัมบูรณ์ของตัวหารไม่เกินค่าสัมบูรณ์ของเงินปันผลไม่เป็นศูนย์) หากไม่พบตัวหารดังกล่าว จำนวนที่กำลังทดสอบจะเป็นจำนวนเฉพาะและนำไปใส่ลงในตารางจำนวนเฉพาะ หากพบตัวหารดังกล่าว จำนวนที่กำลังทดสอบจะเป็นจำนวนประกอบ จะไม่รวมอยู่ในตารางจำนวนเฉพาะ หลังจากนั้น การเปลี่ยนแปลงจะเกิดขึ้นกับตัวเลขถัดไป ซึ่งจะมีการตรวจสอบการมีอยู่ของตัวหารในทำนองเดียวกัน

มาอธิบายขั้นตอนแรกกัน

เราเริ่มต้นด้วยหมายเลข 2 จำนวน 2 ไม่มีตัวหารบวกนอกจาก 1 และ 2 ดังนั้นจึงเป็นเรื่องง่าย เราจึงใส่มันลงในตารางจำนวนเฉพาะ ในที่นี้จะบอกว่า 2 เป็นจำนวนเฉพาะที่น้อยที่สุด เรามาต่อกันที่อันดับ 3 กันเลย ตัวหารบวกที่เป็นไปได้ที่ไม่ใช่ 1 และ 3 คือเลข 2 แต่ 3 หารด้วย 2 ลงตัวไม่ได้ ดังนั้น 3 จึงเป็นจำนวนเฉพาะ และต้องรวมไว้ในตารางจำนวนเฉพาะด้วย เรามาต่อกันที่อันดับ 4 กันเลย ตัวหารบวกที่ไม่ใช่ 1 และ 4 อาจเป็นตัวเลข 2 และ 3 ได้ ลองตรวจสอบดู จำนวน 4 หารด้วย 2 ลงตัว ดังนั้น 4 จึงเป็นจำนวนประกอบและไม่จำเป็นต้องรวมไว้ในตารางจำนวนเฉพาะ โปรดทราบว่า 4 เป็นจำนวนประกอบที่เล็กที่สุด เรามาต่อกันที่อันดับ 5 กันเลย เราตรวจสอบว่าอย่างน้อยหนึ่งในตัวเลข 2, 3, 4 เป็นตัวหารหรือไม่ เนื่องจาก 5 หารด้วย 2, 3 หรือ 4 ไม่ลงตัว จึงเป็นจำนวนเฉพาะ และต้องเขียนลงในตารางจำนวนเฉพาะ จากนั้นจะมีการเปลี่ยนไปใช้ตัวเลข 6, 7 และต่อไปจนถึง 100

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

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

เรามาแสดงการทำงานของตะแกรงของ Eratosthenes เมื่อรวบรวมตารางจำนวนเฉพาะมากถึง 50

ขั้นแรกให้เขียนตัวเลข 2, 3, 4, ..., 50 ตามลำดับ

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

เลขตัวแรกถัดจาก 2 ที่ไม่ได้ขีดฆ่าคือ 3 หมายเลขนี้เป็นจำนวนเฉพาะ ตอนนี้จากหมายเลข 3 เราเลื่อนไปทางขวาอย่างต่อเนื่องด้วยตัวเลขสามตัว (โดยคำนึงถึงตัวเลขที่ขีดฆ่าไว้แล้ว) แล้วขีดฆ่าพวกมันออก วิธีนี้จะขีดฆ่าตัวเลขทั้งหมดที่เป็นผลคูณของสาม

เลขตัวแรกถัดจาก 3 ที่ไม่ได้ขีดฆ่าคือ 5 หมายเลขนี้เป็นจำนวนเฉพาะ ตอนนี้จากหมายเลข 5 เราเลื่อนไปทางขวาอย่างต่อเนื่องด้วยตัวเลข 5 ตัว (เรายังคำนึงถึงตัวเลขที่ขีดฆ่าก่อนหน้านี้ด้วย) และขีดฆ่าพวกมัน วิธีนี้จะขีดฆ่าตัวเลขทั้งหมดที่เป็นผลคูณของห้า

ต่อไป เราจะขีดฆ่าตัวเลขที่เป็นทวีคูณของ 7 จากนั้นคูณด้วย 11 และอื่นๆ กระบวนการจะสิ้นสุดลงเมื่อไม่มีตัวเลขให้ขีดฆ่าอีกต่อไป ด้านล่างนี้เป็นตารางจำนวนเฉพาะจนถึง 50 ที่ได้โดยใช้ตะแกรงเอราทอสเธนีส จำนวนที่ไม่ถูกขีดฆ่าทั้งหมดนั้นเป็นจำนวนเฉพาะ และจำนวนที่ขีดฆ่าทั้งหมดนั้นเป็นจำนวนประกอบ

เรามากำหนดและพิสูจน์ทฤษฎีบทที่จะเร่งกระบวนการรวบรวมตารางจำนวนเฉพาะโดยใช้ตะแกรงของเอราทอสเทนีสกันดีกว่า

ทฤษฎีบท.

ตัวหารบวกที่น้อยที่สุดของจำนวนประกอบ a ที่แตกต่างจากตัวหนึ่งจะต้องไม่เกิน โดยที่ มาจาก a

การพิสูจน์.

ให้เราแสดงด้วยตัวอักษร b ซึ่งเป็นตัวหารที่น้อยที่สุดของจำนวนประกอบ a ที่แตกต่างจากตัวหนึ่ง (ตัวเลข b เป็นจำนวนเฉพาะ ดังต่อจากทฤษฎีบทที่พิสูจน์แล้วในตอนต้นของย่อหน้าก่อนหน้า) จากนั้นจะมีจำนวนเต็ม q โดยที่ a=b·q (ในที่นี้ q คือจำนวนเต็มบวก ซึ่งเป็นไปตามกฎของการคูณจำนวนเต็ม) และ (สำหรับ b>q เงื่อนไขที่ b เป็นตัวหารที่น้อยที่สุดของ a จะถูกละเมิด เนื่องจาก q เป็นตัวหารของจำนวน a เนื่องจากความเท่าเทียมกัน a=q·b ) โดยการคูณทั้งสองด้านของอสมการด้วยค่าบวกและจำนวนเต็มที่มากกว่าหนึ่ง (เราได้รับอนุญาตให้ทำเช่นนี้) เราได้รับ จากการที่ และ .

ทฤษฎีบทที่ได้รับการพิสูจน์แล้วให้ประโยชน์อะไรแก่เราเกี่ยวกับตะแกรงของเอราทอสเทนีส

ประการแรก การขีดฆ่าจำนวนประกอบที่เป็นจำนวนทวีคูณของจำนวนเฉพาะ b ควรขึ้นต้นด้วยจำนวนที่เท่ากับ (ซึ่งตามมาจากอสมการ) ตัวอย่างเช่น การขีดฆ่าตัวเลขที่เป็นทวีคูณของทั้งสองควรเริ่มต้นด้วยตัวเลข 4, ทวีคูณของสามด้วยตัวเลข 9, ผลคูณของห้าด้วยตัวเลข 25 และอื่นๆ

ประการที่สอง การรวบรวมตารางจำนวนเฉพาะจนถึงจำนวน n โดยใช้ตะแกรงเอราทอสเธนีสจะถือว่าสมบูรณ์เมื่อจำนวนประกอบทั้งหมดที่เป็นจำนวนทวีคูณของจำนวนเฉพาะไม่เกิน ในตัวอย่างของเรา n=50 (เนื่องจากเรากำลังสร้างตารางจำนวนเฉพาะจนถึง 50) ดังนั้น ตะแกรงเอราทอสเทนีสจึงควรกำจัดจำนวนประกอบทั้งหมดที่เป็นผลคูณของจำนวนเฉพาะ 2, 3, 5 และ 7 ที่ทำ ไม่เกินรากที่สองทางคณิตศาสตร์ของ 50 นั่นคือ เราไม่จำเป็นต้องค้นหาและขีดฆ่าตัวเลขที่เป็นจำนวนทวีคูณของจำนวนเฉพาะ 11, 13, 17, 19, 23 และอื่นๆ จนถึง 47 อีกต่อไป เนื่องจากพวกมันจะถูกขีดฆ่าเป็นจำนวนทวีคูณของจำนวนเฉพาะที่มีขนาดเล็กกว่า 2 อีกต่อไป , 3, 5 และ 7 .

จำนวนนี้เป็นจำนวนเฉพาะหรือจำนวนประกอบ?

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

แน่นอน คุณสามารถลองใช้การทดสอบการหารลงตัวเพื่อพิสูจน์ว่าจำนวนที่กำหนดนั้นเป็นจำนวนประกอบ ตัวอย่างเช่น หากการทดสอบการหารลงตัวแสดงว่าจำนวนที่กำหนดหารด้วยจำนวนเต็มบวกที่มากกว่า 1 ลงตัวแล้ว จำนวนดั้งเดิมจะเป็นจำนวนประกอบ

ตัวอย่าง.

พิสูจน์ว่า 898,989,898,989,898,989 เป็นจำนวนประกอบ

สารละลาย.

ผลรวมของตัวเลขนี้คือ 9·8+9·9=9·17 เนื่องจากตัวเลขที่เท่ากับ 9·17 หารด้วย 9 ลงตัว ดังนั้นด้วยเกณฑ์การหารด้วย 9 ลงตัว จึงอาจโต้แย้งได้ว่าจำนวนเดิมก็หารด้วย 9 ลงตัวเช่นกัน ดังนั้นจึงเป็นแบบประกอบ

ข้อเสียเปรียบที่สำคัญของแนวทางนี้คือเกณฑ์การหารลงตัวไม่อนุญาตให้พิสูจน์ความเป็นไพรม์ของจำนวนได้ ดังนั้นเมื่อตรวจสอบตัวเลขเพื่อดูว่าเป็นจำนวนเฉพาะหรือจำนวนประกอบ จึงต้องดำเนินการแตกต่างออกไป

แนวทางที่สมเหตุสมผลที่สุดคือลองตัวหารที่เป็นไปได้ทั้งหมดของจำนวนที่กำหนด หากไม่มีตัวหารที่เป็นไปได้ที่เป็นตัวหารจริงของจำนวนที่กำหนด จำนวนนี้จะเป็นจำนวนเฉพาะ ไม่เช่นนั้นจะถูกประกอบเข้าด้วยกัน จากทฤษฎีบทที่พิสูจน์แล้วในย่อหน้าก่อน เป็นไปตามว่าจะต้องหาตัวหารของจำนวนที่กำหนด a ในจำนวนเฉพาะไม่เกิน ดังนั้น จำนวน a จึงสามารถหารตามลำดับด้วยจำนวนเฉพาะ (ซึ่งนำมาจากตารางจำนวนเฉพาะอย่างสะดวก) โดยพยายามหาตัวหารของจำนวน a หากพบตัวหาร จำนวน a จะเป็นจำนวนประกอบ ถ้าจำนวนเฉพาะในจำนวนไม่เกิน ไม่มีตัวหารของจำนวน a แสดงว่าจำนวน a นั้นเป็นจำนวนเฉพาะ

ตัวอย่าง.

ตัวเลข 11 723 ง่ายหรือประสม?

สารละลาย.

เรามาดูกันว่าตัวหารของจำนวน 11,723 สามารถเป็นจำนวนเฉพาะได้เท่าใด เมื่อต้องการทำเช่นนี้ มาประเมินกัน

มันค่อนข้างชัดเจนว่า ตั้งแต่ 200 2 = 40,000 และ 11,723<40 000 (при необходимости смотрите статью การเปรียบเทียบตัวเลข- ดังนั้น ตัวประกอบเฉพาะที่เป็นไปได้ของ 11,723 จึงน้อยกว่า 200 สิ่งนี้ทำให้งานของเราง่ายขึ้นมาก หากเราไม่ทราบสิ่งนี้ เราจะต้องผ่านจำนวนเฉพาะทั้งหมดไม่เกิน 200 แต่ไม่เกินจำนวน 11,723

หากต้องการคุณสามารถประเมินได้แม่นยำยิ่งขึ้น เนื่องจาก 108 2 =11,664 และ 109 2 =11,881 จากนั้น 108 2<11 723<109 2 , следовательно, - ดังนั้น จำนวนเฉพาะใดๆ ที่น้อยกว่า 109 อาจเป็นตัวประกอบเฉพาะของจำนวนที่กำหนด 11,723

ตอนนี้เราจะแบ่งจำนวน 11,723 ออกเป็นจำนวนเฉพาะตามลำดับ 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 . ถ้าจำนวน 11,723 หารด้วยจำนวนเฉพาะตัวใดตัวหนึ่ง ก็จะนำมาประกอบกัน ถ้าหารด้วยจำนวนเฉพาะใดๆ ที่เขียนไว้ไม่ลงตัว แสดงว่าจำนวนเดิมนั้นเป็นจำนวนเฉพาะ

เราจะไม่อธิบายกระบวนการแบ่งแยกที่น่าเบื่อหน่ายและซ้ำซากจำเจทั้งหมดนี้ สมมุติว่า 11,723 ทันที

จำนวนเฉพาะ

จำนวนธรรมชาติที่มากกว่าหนึ่งและไม่มีตัวหารนอกจากตัวมันเองและหนึ่ง: 2, 3, 5, 7, 11, 13... จำนวนเฉพาะนั้นไม่มีที่สิ้นสุด

เลขเด่น

จำนวนเต็มบวกที่มากกว่า 1 ซึ่งไม่มีตัวหารนอกจากตัวมันเองและ 1: 2, 3, 5, 7, 11, 13,... แนวคิดเรื่องจำนวนเป็นพื้นฐานในการศึกษาเรื่องการหารลงตัวของธรรมชาติ (จำนวนเต็มบวก ) ตัวเลข; กล่าวคือ ทฤษฎีบทหลักของทฤษฎีการหารลงตัวกำหนดว่าจำนวนเต็มบวกทุกจำนวน ยกเว้น 1 จะถูกแยกย่อยอย่างไม่ซ้ำกันในการผลคูณของตัวเลขจำนวนหนึ่ง (ไม่ได้คำนึงถึงลำดับของตัวประกอบ) มีจำนวนเฉพาะมากมายนับไม่ถ้วน (นักคณิตศาสตร์ชาวกรีกโบราณรู้จักข้อเสนอนี้ หลักฐานนี้มีอยู่ในหนังสือเล่มที่ 9 ของ Euclid’s Elements) คำถามเรื่องการหารจำนวนธรรมชาติลงตัว และคำถามที่เกี่ยวข้องกับจำนวนเฉพาะ จึงมีความสำคัญในการศึกษาเรื่องหมู่ โดยเฉพาะอย่างยิ่ง โครงสร้างของกลุ่มที่มีองค์ประกอบจำนวนจำกัดมีความสัมพันธ์อย่างใกล้ชิดกับวิธีที่องค์ประกอบจำนวนนี้ (ลำดับของกลุ่ม) ถูกแยกย่อยเป็นปัจจัยเฉพาะ ทฤษฎีตัวเลขพีชคณิตเกี่ยวข้องกับประเด็นเรื่องการหารจำนวนเต็มพีชคณิตลงตัว แนวคิดเรื่องจำนวนบางส่วนไม่เพียงพอสำหรับการสร้างทฤษฎีการหารลงตัว ซึ่งนำไปสู่การสร้างแนวคิดเรื่องอุดมคติ P. G. L. Dirichlet ก่อตั้งในปี 1837 ว่าความก้าวหน้าทางคณิตศาสตร์ a + bx สำหรับ x = 1, 2,... โดยมีจำนวนเต็มโคไพรม์ a และ b มีจำนวนเฉพาะจำนวนอนันต์ การพิจารณาการแจกแจงของจำนวนเฉพาะในชุดตัวเลขตามธรรมชาตินั้นเป็นเรื่องยากมาก ปัญหาในทฤษฎีจำนวน จัดทำขึ้นเพื่อศึกษาพฤติกรรมเชิงเส้นกำกับของฟังก์ชัน p(x) ซึ่งหมายถึงจำนวนเศษส่วนที่ไม่เกินจำนวนบวก x ผลลัพธ์แรกในทิศทางนี้เป็นของ P.L. Chebyshev ซึ่งในปี 1850 พิสูจน์ว่ามีค่าคงที่ a และ A สองตัวที่ ⦁< p(x) < ═при любых x ³ 2 [т. е., что p(х) растет, как функция ]. Хронологически следующим значительным результатом, уточняющим теорему Чебышева, является т. н. асимптотический закон распределения П. ч. (Ж. Адамар, 1896, Ш. Ла Валле Пуссен, 1896), заключающийся в том, что предел отношения p(х) к ═равен

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

(ผลิตภัณฑ์ขยายไปถึง P. h. p = 2, 3,...) ระบุครั้งแรกโดยแอล. ออยเลอร์; เอกลักษณ์นี้ใช้ได้กับทุกความซับซ้อนที่มีส่วนที่แท้จริงมากกว่าความสามัคคี จากอัตลักษณ์นี้ คำถามเกี่ยวกับการแจกแจงของตัวเลข P นำไปสู่การศึกษาฟังก์ชันพิเศษ µ ฟังก์ชันซีตา x(s) ซึ่งหาค่า Res > 1 ตามอนุกรม

ฟังก์ชันนี้ใช้ในการแจกแจงของจำนวนเฉพาะสำหรับจำนวนจริง s โดยเชบีเชฟ B. Riemann ชี้ให้เห็นถึงความสำคัญของการศึกษา x สำหรับค่าเชิงซ้อนของ s รีมันน์ตั้งสมมติฐานว่ารากทั้งหมดของสมการ x = 0 ที่อยู่ในครึ่งระนาบด้านขวามีส่วนจริงเท่ากับ 1/

สมมติฐานนี้ไม่ได้รับการพิสูจน์จนถึงปัจจุบัน (1975); การพิสูจน์จะช่วยแก้ปัญหาการแจกแจงจำนวนเฉพาะได้อย่างมาก คำถามเกี่ยวกับการแจกแจงจำนวนเฉพาะมีความเกี่ยวข้องอย่างใกล้ชิดกับปัญหาของโกลด์บัค ปัญหา "แฝด" ที่ยังไม่ได้รับการแก้ไข และปัญหาอื่นๆ ของทฤษฎีจำนวนวิเคราะห์ ปัญหาของ “แฝด” คือการหาว่าจำนวน P. ที่แตกต่างกันด้วย 2 (เช่น 11 และ 13) นั้นมีขอบเขตหรือไม่มีที่สิ้นสุด ตารางตัวเลข P. ที่อยู่ใน 11 ล้านตัวเลขธรรมชาติแรกแสดงให้เห็นว่ามี "ฝาแฝด" ที่มีขนาดใหญ่มาก (เช่น 10006427 และ 10006429) แต่นี่ไม่ใช่ข้อพิสูจน์ถึงความไม่มีที่สิ้นสุดของจำนวน ภายนอกตารางที่คอมไพล์แล้ว หมายเลข P. แต่ละตัวเป็นที่ทราบกันดีอยู่แล้วว่าสามารถใช้นิพจน์ทางคณิตศาสตร์อย่างง่ายได้ [เช่น ก่อตั้ง (1965) ว่า 211213 µ1 เป็นหมายเลข P. มี 3,376 หลัก].

วรรณกรรมแปล: Vinogradov I.M., พื้นฐานของทฤษฎีจำนวน, ฉบับที่ 8, M. , 1972; Hasse G. การบรรยายเรื่องทฤษฎีจำนวน ทรานส์ จากภาษาเยอรมัน ม. 2496; อิงแฮม เอ.อี. การแจกแจงของจำนวนเฉพาะ ทรานส์ จากภาษาอังกฤษ ม. µ ล. 2479; พราฮาร์ เค. การแจกแจงของจำนวนเฉพาะ ทรานส์ จากภาษาเยอรมัน ม. 2510; Trost E., จำนวนเฉพาะ, แปล, จากภาษาเยอรมัน, M., 1959.

วิกิพีเดีย

เลขเด่น

เลขเด่น- จำนวนธรรมชาติที่มีตัวหารตามธรรมชาติสองตัวพอดี - และตัวมันเอง กล่าวอีกนัยหนึ่งคือจำนวน xเป็นจำนวนเฉพาะถ้ามากกว่า 1 และหารลงตัวด้วย 1 และเท่านั้น x- ตัวอย่างเช่น 5 เป็นจำนวนเฉพาะ และ 6 เป็นจำนวนประกอบ เนื่องจากนอกเหนือจาก 1 และ 6 แล้ว ยังหารด้วย 2 และ 3 ได้อีกด้วย

จำนวนธรรมชาติที่มากกว่า 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 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 …

• การแปล

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

จำนวนสมบูรณ์มีผลรวมของตัวหารเองเท่ากับตัวมันเอง ตัวอย่างเช่น ตัวหารแท้ของเลข 6 คือ 1, 2 และ 3 1 + 2 + 3 = 6 ตัวหารแท้ของเลข 28 คือ 1, 2, 4, 7 และ 14 ยิ่งไปกว่านั้น 1 + 2 + 4 + 7 + 14 = 28.

ตัวเลขจะถูกเรียกว่าเป็นมิตรถ้าผลรวมของตัวหารแท้ของจำนวนหนึ่งเท่ากับอีกจำนวนหนึ่ง และในทางกลับกัน เช่น 220 และ 284 เราสามารถพูดได้ว่าจำนวนสมบูรณ์นั้นเป็นมิตรกับตัวมันเอง

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

เขายังแสดงด้วยว่าถ้าเลข 2n-1 เป็นจำนวนเฉพาะ แล้วเลข 2n-1 * (2n-1) ก็จะสมบูรณ์แบบ ออยเลอร์นักคณิตศาสตร์อีกคนสามารถแสดงในปี 1747 ว่าจำนวนสมบูรณ์ทั้งหมดสามารถเขียนในรูปแบบนี้ได้ จนถึงทุกวันนี้ ยังไม่ทราบว่ามีเลขสมบูรณ์คี่อยู่หรือไม่

ในปี 200 ปีก่อนคริสตกาล ชาวกรีก Eratosthenes มีอัลกอริธึมในการค้นหาจำนวนเฉพาะที่เรียกว่า Sieve of Eratosthenes

และจากนั้นก็เกิดการแตกหักครั้งใหญ่ในประวัติศาสตร์ของการศึกษาจำนวนเฉพาะ ที่เกี่ยวข้องกับยุคกลาง

การค้นพบต่อไปนี้เกิดขึ้นเมื่อต้นศตวรรษที่ 17 โดยนักคณิตศาสตร์แฟร์มาต์ เขาพิสูจน์การคาดเดาของอัลเบิร์ต จิราร์ดว่าจำนวนเฉพาะใดๆ ในรูปแบบ 4n+1 สามารถเขียนได้โดยไม่ซ้ำกันเป็นผลรวมของกำลังสองสองอัน และยังได้กำหนดทฤษฎีบทที่ว่าจำนวนใดๆ ก็ตามสามารถเขียนเป็นผลรวมของกำลังสองสี่ตัวได้

เขาได้พัฒนาวิธีการใหม่ในการแยกตัวประกอบจำนวนมาก และสาธิตให้กับตัวเลข 2027651281 = 44021 × 46061 นอกจากนี้ เขายังพิสูจน์ทฤษฎีบทเล็กๆ ของแฟร์มาต์ด้วย: ถ้า p เป็นจำนวนเฉพาะ แล้วสำหรับจำนวนเต็มใดๆ a มันจะเป็นจริงโดยที่ p = โมดูโล พี

ข้อความนี้พิสูจน์ครึ่งหนึ่งของสิ่งที่เรียกว่า "การคาดเดาแบบจีน" และมีอายุย้อนกลับไป 2,000 ปี: จำนวนเต็ม n เป็นจำนวนเฉพาะก็ต่อเมื่อ 2 n -2 หารด้วย n ลงตัวเท่านั้น ส่วนที่สองของสมมติฐานกลายเป็นเท็จ เช่น 2,341 - 2 หารด้วย 341 ลงตัว แม้ว่าจำนวน 341 จะประกอบกันก็ตาม: 341 = 31 × 11

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

แฟร์มาต์มีความสอดคล้องกับคนรุ่นราวคราวเดียวกับเขามาก โดยเฉพาะกับพระภิกษุชื่อมาเรน เมอร์เซน ในจดหมายฉบับหนึ่งของเขา เขาตั้งสมมติฐานว่าตัวเลขในรูปแบบ 2 n +1 จะเป็นจำนวนเฉพาะเสมอถ้า n เป็นกำลังของสอง เขาทดสอบค่านี้สำหรับ n = 1, 2, 4, 8 และ 16 และมั่นใจว่าในกรณีที่ n ไม่ใช่กำลังสอง จำนวนนั้นก็ไม่จำเป็นต้องเป็นจำนวนเฉพาะเสมอไป ตัวเลขเหล่านี้เรียกว่าตัวเลขของแฟร์มาต์ และเพียง 100 ปีต่อมาออยเลอร์แสดงให้เห็นว่าจำนวนถัดไป 2 32 + 1 = 4294967297 หารด้วย 641 ลงตัว จึงไม่ใช่จำนวนเฉพาะ

ตัวเลขในรูปแบบ 2 n - 1 ก็เป็นหัวข้อวิจัยเช่นกัน เนื่องจากเป็นเรื่องง่ายที่จะแสดงให้เห็นว่าถ้า n ประกอบเข้าด้วยกัน ตัวเลขนั้นก็จะประกอบกันด้วย ตัวเลขเหล่านี้เรียกว่าตัวเลข Mersenne เนื่องจากเขาได้ศึกษาตัวเลขเหล่านี้อย่างกว้างขวาง

แต่ไม่ใช่ทุกจำนวนที่อยู่ในรูป 2 n - 1 โดยที่ n เป็นจำนวนเฉพาะ จึงเป็นจำนวนเฉพาะ ตัวอย่างเช่น 2 11 - 1 = 2047 = 23 * 89 ค้นพบครั้งแรกในปี 1536

เป็นเวลาหลายปีมาแล้วที่ตัวเลขประเภทนี้ทำให้นักคณิตศาสตร์มีจำนวนเฉพาะที่รู้จักมากที่สุด M 19 ได้รับการพิสูจน์โดย Cataldi ในปี 1588 และเป็นเวลา 200 ปีที่เป็นจำนวนเฉพาะที่รู้จักมากที่สุด จนกระทั่งออยเลอร์พิสูจน์ว่า M 31 ก็เป็นจำนวนเฉพาะเช่นกัน บันทึกนี้คงอยู่ต่อไปอีกร้อยปี จากนั้นลูคัสก็แสดงให้เห็นว่า M 127 เป็นจำนวนเฉพาะ (และนี่คือตัวเลข 39 หลักอยู่แล้ว) และหลังจากนั้น การวิจัยก็ดำเนินต่อไปด้วยการถือกำเนิดของคอมพิวเตอร์

ในปี 1952 ความเป็นเลิศของตัวเลข M 521, M 607, M 1279, M 2203 และ M 2281 ได้รับการพิสูจน์แล้ว

ภายในปี พ.ศ. 2548 สามารถค้นพบจำนวนเฉพาะของเมอร์แซนน์ได้ 42 ตัว ที่ใหญ่ที่สุดคือ M 25964951 ประกอบด้วย 7816230 หลัก

งานของออยเลอร์มีผลกระทบอย่างมากต่อทฤษฎีตัวเลข รวมถึงจำนวนเฉพาะด้วย เขาขยายทฤษฎีบทลิตเติ้ลของแฟร์มาต์และแนะนำฟังก์ชัน φ แยกตัวประกอบของแฟร์มาต์หมายเลขที่ 5 2 32 +1 หาจำนวนที่เป็นมิตรได้ 60 คู่ และตั้งกฎการตอบแทนซึ่งกันและกันกำลังสอง (แต่พิสูจน์ไม่ได้)

เขาเป็นคนแรกที่แนะนำวิธีการวิเคราะห์ทางคณิตศาสตร์และพัฒนาทฤษฎีจำนวนวิเคราะห์ เขาพิสูจน์ว่าไม่เพียงแต่อนุกรมฮาร์มอนิก ∑ (1/n) เท่านั้น แต่ยังรวมถึงอนุกรมของรูปแบบด้วย

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

ผลลัพธ์ที่ได้จากผลรวมของส่วนกลับของจำนวนเฉพาะก็จะต่างกันออกไปเช่นกัน ผลรวมของพจน์ n ของอนุกรมฮาร์มอนิกจะเพิ่มขึ้นโดยประมาณเป็น log(n) และอนุกรมที่สองจะแยกออกช้ากว่าเมื่อเป็น log[ log(n) ] ซึ่งหมายความว่า ตัวอย่างเช่น ผลรวมของส่วนกลับของจำนวนเฉพาะทั้งหมดที่พบจนถึงปัจจุบันจะให้เพียง 4 แม้ว่าอนุกรมจะยังคงแยกจากกันก็ตาม

เมื่อดูเผินๆ ดูเหมือนว่าจำนวนเฉพาะจะกระจายแบบสุ่มไปตามจำนวนเต็ม ตัวอย่างเช่น ในบรรดาตัวเลข 100 ตัวที่อยู่ก่อน 10000000 จะมีจำนวนเฉพาะ 9 ตัว และในจำนวน 100 ตัวที่อยู่หลังค่านี้มีเพียง 2 ตัวเท่านั้น แต่สำหรับกลุ่มขนาดใหญ่ จำนวนเฉพาะจะถูกกระจายอย่างเท่าเทียมกัน Legendre และ Gauss จัดการกับปัญหาเรื่องการจำหน่าย เกาส์เคยบอกเพื่อนว่าในช่วง 15 นาทีฟรีๆ เขาจะนับจำนวนเฉพาะใน 1,000 ตัวถัดไปเสมอ เมื่อบั้นปลายชีวิต เขาได้นับจำนวนเฉพาะทั้งหมดได้ถึง 3 ล้าน ลีเจนเดรและเกาส์คำนวณเท่ากันว่าสำหรับ n ขนาดใหญ่ ความหนาแน่นเฉพาะคือ 1/log(n) Legendre ประมาณจำนวนจำนวนเฉพาะในช่วงตั้งแต่ 1 ถึง n เช่น

π(n) = n/(บันทึก(n) - 1.08366)

และเกาส์ก็เหมือนกับอินทิกรัลลอการิทึม

π(n) = ∫ 1/log(t) dt

โดยมีช่วงการรวมตั้งแต่ 2 ถึง n

ข้อความเกี่ยวกับความหนาแน่นเฉพาะ 1/log(n) เรียกว่าทฤษฎีบทการกระจายตัวเฉพาะ พวกเขาพยายามพิสูจน์มันตลอดศตวรรษที่ 19 และ Chebyshev และ Riemann ก็ประสบความสำเร็จ พวกเขาเชื่อมโยงมันกับสมมติฐานรีมันน์ ซึ่งเป็นสมมติฐานที่ยังไม่ได้รับการพิสูจน์เกี่ยวกับการแจกแจงของศูนย์ของฟังก์ชันซีตาของรีมันน์ ความหนาแน่นของจำนวนเฉพาะได้รับการพิสูจน์พร้อมกันโดยฮาดามาร์ดและวัลเล-ปูแซ็งในปี พ.ศ. 2439

ยังมีคำถามที่ยังไม่ได้แก้อีกมากมายในทฤษฎีจำนวนเฉพาะ บางคำถามมีอายุหลายร้อยปี:

• สมมติฐานจำนวนเฉพาะคู่นั้นเกี่ยวกับจำนวนคู่ของจำนวนเฉพาะที่มีค่าไม่สิ้นสุดซึ่งต่างกันด้วย 2
• การคาดเดาของโกลด์บัค: จำนวนคู่ใดๆ ที่เริ่มต้นด้วย 4 สามารถแสดงเป็นผลรวมของจำนวนเฉพาะสองตัวได้
• จำนวนเฉพาะในรูปแบบ n 2 + 1 มีจำนวนอนันต์หรือไม่?
• เป็นไปได้ไหมที่จะหาจำนวนเฉพาะระหว่าง n 2 ถึง (n + 1) 2? (ข้อเท็จจริงที่ว่ามีจำนวนเฉพาะระหว่าง n ถึง 2n เสมอ ได้รับการพิสูจน์โดย Chebyshev)
• จำนวนเฉพาะของแฟร์มาต์เป็นจำนวนอนันต์ใช่หรือไม่? มีจำนวนเฉพาะแฟร์มาต์หลัง 4 หรือไม่?
• มีความก้าวหน้าทางคณิตศาสตร์ของจำนวนเฉพาะที่ต่อเนื่องกันตามความยาวที่กำหนดหรือไม่? ตัวอย่างเช่น สำหรับความยาว 4: 251, 257, 263, 269 ความยาวสูงสุดที่พบคือ 26
• มีจำนวนเฉพาะสามตัวติดต่อกันเป็นจำนวนอนันต์ในการก้าวหน้าทางคณิตศาสตร์หรือไม่?
• n 2 - n + 41 เป็นจำนวนเฉพาะสำหรับ 0 ≤ n ≤ 40 จำนวนเฉพาะดังกล่าวมีจำนวนอนันต์หรือไม่? คำถามเดียวกันสำหรับสูตร n 2 - 79 n + 1601 ตัวเลขเหล่านี้เป็นจำนวนเฉพาะสำหรับ 0 ≤ n ≤ 79
• จำนวนเฉพาะในรูปแบบ n# + 1 มีจำนวนอนันต์หรือไม่? (n# คือผลลัพธ์ของการคูณจำนวนเฉพาะทั้งหมดที่น้อยกว่า n)
• จำนวนเฉพาะในรูปแบบ n# -1 มีจำนวนอนันต์หรือไม่?
• จำนวนเฉพาะในรูป n มีจำนวนอนันต์หรือไม่? +1?
• จำนวนเฉพาะในรูป n มีจำนวนอนันต์หรือไม่? – 1?
• ถ้า p เป็นจำนวนเฉพาะ 2 p -1 จะไม่มีกำลังสองจำนวนเฉพาะอยู่ท่ามกลางปัจจัยของมันเสมอไปใช่หรือไม่
• ลำดับฟีโบนัชชีมีจำนวนเฉพาะจำนวนอนันต์หรือไม่?

จำนวนเฉพาะคู่ที่ใหญ่ที่สุดคือ 2003663613 × 2 195000 ± 1 ประกอบด้วย 58711 หลัก และถูกค้นพบในปี พ.ศ. 2550

จำนวนเฉพาะแฟคทอเรียลที่ใหญ่ที่สุด (ประเภท n! ± 1) คือ 147855! - 1. ประกอบด้วยตัวเลข 142891 หลัก พบเมื่อปี พ.ศ. 2545.

จำนวนเฉพาะปฐมภูมิที่ใหญ่ที่สุด (ตัวเลขในรูปแบบ n# ± 1) คือ 1098133# + 1

แท็ก: เพิ่มแท็ก

การแจงนับตัวหารตามคำนิยามจำนวน nเป็นจำนวนเฉพาะก็ต่อเมื่อหารด้วย 2 และจำนวนเต็มอื่นๆ ไม่ลงตัว ยกเว้น 1 และตัวมันเอง สูตรข้างต้นจะขจัดขั้นตอนที่ไม่จำเป็นและประหยัดเวลา เช่น หลังจากตรวจสอบว่าตัวเลขหารด้วย 3 ลงตัวหรือไม่ ก็ไม่จำเป็นต้องตรวจสอบว่าตัวเลขหารด้วย 9 ลงตัวหรือไม่

• ฟังก์ชัน floor(x) ปัดเศษ x เป็นจำนวนเต็มที่ใกล้ที่สุดซึ่งน้อยกว่าหรือเท่ากับ x

เรียนรู้เกี่ยวกับเลขคณิตแบบโมดูลาร์การดำเนินการ "x mod y" (mod เป็นตัวย่อของคำภาษาละติน "modulo" นั่นคือ "โมดูล") หมายถึง "หาร x ด้วย y และค้นหาส่วนที่เหลือ" กล่าวอีกนัยหนึ่งในเลขคณิตแบบแยกส่วนเมื่อถึงค่าที่แน่นอนซึ่งเรียกว่า โมดูลตัวเลขจะ "เปลี่ยน" ให้เป็นศูนย์อีกครั้ง ตัวอย่างเช่น นาฬิการักษาเวลาด้วยโมดูลัส 12 โดยจะแสดงที่ 10, 11 และ 12 นาฬิกา จากนั้นจึงกลับไปเป็น 1

• เครื่องคิดเลขหลายเครื่องมีปุ่มดัดแปลง ส่วนท้ายของส่วนนี้จะแสดงวิธีประเมินฟังก์ชันนี้ด้วยตนเองสำหรับตัวเลขจำนวนมาก