ตัวอย่างจำนวนเฉพาะหลักเดียว จำนวนเฉพาะ

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

ยานเดกซ์ RTB R-A-339285-1

จำนวนเฉพาะและจำนวนประกอบ - คำจำกัดความและตัวอย่าง

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

คำจำกัดความ 1

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

คำจำกัดความ 2

จำนวนประกอบคือจำนวนเต็มที่มากกว่าหนึ่งและมีตัวหารบวกอย่างน้อยสามตัว

หนึ่งไม่ใช่จำนวนเฉพาะหรือจำนวนประกอบ มีตัวหารบวกเพียงตัวเดียว จึงแตกต่างจากจำนวนบวกอื่นๆ ทั้งหมด จำนวนเต็มบวกทั้งหมดเรียกว่าจำนวนธรรมชาติ ซึ่งใช้ในการนับ

คำจำกัดความ 3

จำนวนเฉพาะเป็นจำนวนธรรมชาติที่มีตัวหารบวกเพียงสองตัว

คำจำกัดความที่ 4

หมายเลขประกอบเป็นจำนวนธรรมชาติที่มีตัวหารบวกมากกว่าสองตัว

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

คำจำกัดความที่ 5

จำนวนธรรมชาติที่ไม่ใช่จำนวนเฉพาะเรียกว่าจำนวนประกอบ

จำนวนเฉพาะ: 2, 3, 11, 17, 131, 523 พวกมันหารด้วยตัวมันเองและ 1 ลงตัวเท่านั้น. หมายเลขผสม: 6, 63, 121, 6697 นั่นคือเลข 6 สามารถแบ่งออกเป็น 2 และ 3 และ 63 เป็น 1, 3, 7, 9, 21, 63 และ 121 เป็น 11, 11 นั่นคือตัวหารจะเป็น 1, 11, 121 หมายเลข 6697 แบ่งออกเป็น 37 และ 181 โปรดทราบว่าแนวคิดเรื่องจำนวนเฉพาะและจำนวนเฉพาะเป็นแนวคิดที่แตกต่างกัน

เพื่อให้ง่ายต่อการใช้จำนวนเฉพาะ คุณต้องใช้ตาราง:

ตารางสำหรับจำนวนธรรมชาติที่มีอยู่ทั้งหมดนั้นไม่สมจริง เนื่องจากมีจำนวนอนันต์ เมื่อตัวเลขมีขนาดถึง 10,000 หรือ 1000000000 คุณควรพิจารณาใช้ตะแกรงเอราทอสเทนีส

ลองพิจารณาทฤษฎีบทที่อธิบายข้อความสุดท้าย

ทฤษฎีบท 1

ตัวหารบวกที่น้อยที่สุดที่ไม่ใช่ 1 ของจำนวนธรรมชาติที่มากกว่า 1 จะเป็นจำนวนเฉพาะ

หลักฐานที่ 1

สมมติว่า a เป็นจำนวนธรรมชาติที่มากกว่า 1 โดย b เป็นตัวหารที่ไม่ใช่ 1 ที่เล็กที่สุดของ a จำเป็นต้องพิสูจน์ว่า b เป็นจำนวนเฉพาะโดยใช้วิธีขัดแย้ง

สมมติว่า b เป็นจำนวนประกอบ จากตรงนี้ เราพบว่ามีตัวหารของ b ซึ่งต่างจาก 1 และจาก b ตัวหารดังกล่าวเขียนแทนด้วย b 1 จำเป็นต้องมีเงื่อนไขที่ 1< b 1 < b เป็นที่เรียบร้อยแล้ว.

จากเงื่อนไขเป็นที่ชัดเจนว่า a หารด้วย b, b หารด้วย b 1 ซึ่งหมายความว่าแนวคิดเรื่องการหารลงตัวแสดงได้ดังนี้: ก = ข คิวและ b = b 1 · q 1 จากที่ไหน a = b 1 · (q 1 · q) โดยที่ q และ คำถามที่ 1เป็นจำนวนเต็ม ตามกฎการคูณจำนวนเต็ม เราได้ผลลัพธ์ของจำนวนเต็มเป็นจำนวนเต็มที่มีความเท่ากันในรูปแบบ a = b 1 · (q 1 · q) จะเห็นได้ว่า b1 เป็นตัวหารของจำนวน a ความไม่เท่าเทียมกัน 1< b 1 < b ไม่สอดคล้องกัน เพราะเราพบว่า b เป็นตัวหารบวกที่น้อยที่สุดและไม่ใช่ 1 ของ a

ทฤษฎีบท 2

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

หลักฐานที่ 2

สมมุติว่าเราเอาจำนวนธรรมชาติจำนวนจำกัด 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 , เราพบว่ามันจะหารด้วย pn + 1 ลงตัว โปรดทราบว่านิพจน์ p n + 1 การหารจำนวน p เท่ากับผลรวม p 1, p 2, ..., p n + 1 เราพบว่านิพจน์ p n + 1 ต้องหารเทอมที่สองของผลรวมนี้ซึ่งเท่ากับ 1 แต่เป็นไปไม่ได้

จะเห็นได้ว่าสามารถหาจำนวนเฉพาะใดๆ ได้จากจำนวนเฉพาะใดๆ ก็ตามของจำนวนเฉพาะที่กำหนด ตามมาด้วยจำนวนเฉพาะจำนวนนับไม่ถ้วน

เนื่องจากมีจำนวนเฉพาะจำนวนมาก ตารางจึงจำกัดอยู่ที่ตัวเลข 100, 1,000, 10,000 และอื่นๆ

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

ลองดูทีละขั้นตอน

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

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

วิธีใช้ตะแกรง Eratosthenes ถือว่าสะดวกที่สุด ลองดูตารางด้านล่างนี้เป็นตัวอย่าง เริ่มต้นด้วยการเขียนตัวเลข 2, 3, 4, ... , 50

ตอนนี้คุณต้องขีดฆ่าตัวเลขทั้งหมดที่เป็นผลคูณของ 2 ออก ดำเนินการขีดฆ่าตามลำดับ เราได้รับตารางดังนี้:

เราไปขีดฆ่าตัวเลขที่เป็นทวีคูณของ 5. เราได้รับ:

ขีดฆ่าตัวเลขที่เป็นทวีคูณของ 7, 11 ในที่สุดโต๊ะก็ดูเหมือน

เรามาดูการกำหนดทฤษฎีบทกันดีกว่า

ทฤษฎีบท 3

ตัวหารบวกและไม่ใช่ 1 ที่น้อยที่สุดของจำนวนฐาน a จะไม่เกิน a โดยที่ a คือรากเลขคณิตของจำนวนที่กำหนด

หลักฐานที่ 3

จำเป็นต้องแสดง b ตัวหารที่เล็กที่สุดของจำนวนประกอบ a มีจำนวนเต็ม q โดยที่ a = b · q และเรามี b ≤ q นั้น ความไม่เท่าเทียมกันของแบบฟอร์มเป็นสิ่งที่ยอมรับไม่ได้ ข > คิว,เพราะสภาพถูกละเมิด ทั้งสองด้านของอสมการ b ≤ q ควรคูณด้วยจำนวนบวกใดๆ b ที่ไม่เท่ากับ 1 เราจะได้ว่า b · b ≤ b · q โดยที่ b 2 ≤ a และ b ≤ a

จากทฤษฎีบทที่พิสูจน์แล้วเป็นที่ชัดเจนว่าการขีดฆ่าตัวเลขในตารางนำไปสู่ความจริงที่ว่าจำเป็นต้องเริ่มต้นด้วยตัวเลขที่เท่ากับ b 2 และเป็นไปตามความไม่เท่าเทียมกัน b 2 ≤ a นั่นคือ หากคุณขีดฆ่าตัวเลขที่เป็นทวีคูณของ 2 กระบวนการจะเริ่มต้นด้วย 4 และทวีคูณของ 3 ด้วย 9 และต่อไปเรื่อยๆ จนถึง 100

การคอมไพล์ตารางดังกล่าวโดยใช้ทฤษฎีบทของเอราทอสเธนีส เสนอว่าเมื่อจำนวนประกอบทั้งหมดถูกขีดฆ่าออก จำนวนเฉพาะจะยังคงอยู่ที่ไม่เกิน n ในตัวอย่างโดยที่ n = 50 เราจะได้ n = 50 จากนี้เราจะได้ว่าตะแกรงของเอราทอสเทนีสจะกรองจำนวนประกอบทั้งหมดที่มีค่าไม่เกินค่ารากของ 50 ออกไป การค้นหาตัวเลขทำได้โดยการขีดฆ่า

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

ตัวอย่างที่ 1

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

สารละลาย

ผลรวมของตัวเลขที่กำหนดคือ 9 8 + 9 9 = 9 17 ซึ่งหมายความว่าตัวเลข 9 · 17 หารด้วย 9 ลงตัว โดยอาศัยการทดสอบการหารด้วย 9 ลงตัว ตามมาว่าเป็นคอมโพสิต

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

ตัวอย่างที่ 2

กำหนดจำนวนประกอบหรือจำนวนเฉพาะ 11723

สารละลาย

ตอนนี้คุณต้องค้นหาตัวหารทั้งหมดของหมายเลข 11723 ต้องประเมิน 11723

จากตรงนี้เราจะเห็นว่า 11723< 200 , то 200 2 = 40 000 และ 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

เพื่อการประมาณตัวเลข 11723 ที่แม่นยำยิ่งขึ้น คุณต้องเขียนนิพจน์ 108 2 = 11 664 และ 109 2 = 11 881 , ที่ 108 2 < 11 723 < 109 2 - ตามมาด้วยหมายเลข 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

เมื่อขยายออกเราจะพบว่า 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 เป็นจำนวนเฉพาะทั้งหมด กระบวนการทั้งหมดนี้สามารถแสดงเป็นการหารด้วยคอลัมน์ นั่นคือหาร 11723 ด้วย 19 เลข 19 เป็นปัจจัยหนึ่ง เนื่องจากเราหารได้โดยไม่มีเศษ. เรามาแสดงการแบ่งเป็นคอลัมน์:

ตามมาด้วยว่า 11723 เป็นจำนวนประกอบ เพราะนอกจากตัวมันเองและ 1 แล้ว ยังมีตัวหารด้วย 19 ด้วย

คำตอบ: 11723 เป็นจำนวนประกอบ

หากคุณสังเกตเห็นข้อผิดพลาดในข้อความ โปรดไฮไลต์แล้วกด Ctrl+Enter

จำนวนเฉพาะเป็นจำนวนธรรมชาติ (จำนวนเต็มบวก) ที่สามารถหารด้วยจำนวนธรรมชาติเพียงสองตัวเท่านั้นโดยไม่มีเศษเหลือ คือ ทีละตัวและตัวมันเอง กล่าวอีกนัยหนึ่ง จำนวนเฉพาะจะต้องมีตัวหารธรรมชาติสองตัวพอดี: และตัวมันเองด้วย

ตามคำนิยาม เซตของตัวหารทั้งหมดของจำนวนเฉพาะคือสององค์ประกอบ กล่าวคือ แสดงถึงชุด

เซตของจำนวนเฉพาะทั้งหมดจะแสดงด้วยสัญลักษณ์ ดังนั้น เนื่องจากนิยามของเซตของจำนวนเฉพาะ เราสามารถเขียนได้:

ลำดับของจำนวนเฉพาะมีลักษณะดังนี้:

ทฤษฎีบทพื้นฐานของเลขคณิต

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

การขยายจำนวนธรรมชาติ title="Rendered by QuickLaTeX.com" height="13" width="42" style="vertical-align: -1px;"> в произведение простых чисел называют !} ตามบัญญัติ:

จำนวนเฉพาะอยู่ที่ไหน และ . ตัวอย่างเช่น การขยายตามรูปแบบบัญญัติของจำนวนธรรมชาติจะมีลักษณะดังนี้:

การแทนจำนวนธรรมชาติเป็นผลคูณของจำนวนเฉพาะก็เรียกอีกอย่างหนึ่งว่า การแยกตัวประกอบของจำนวน.

คุณสมบัติของจำนวนเฉพาะ

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

อัลกอริธึมที่มีชื่อเสียงที่สุดอย่างหนึ่งในการค้นหาและจดจำจำนวนเฉพาะคือ ตะแกรงเอราทอสเธเนส- ดังนั้นอัลกอริทึมนี้จึงตั้งชื่อตามนักคณิตศาสตร์ชาวกรีก Eratosthenes แห่ง Cyrene ซึ่งถือเป็นผู้เขียนอัลกอริทึมนี้

หากต้องการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าจำนวนที่ระบุ ให้ทำตามวิธีของเอราทอสเธนีส ให้ทำตามขั้นตอนต่อไปนี้:

ขั้นตอนที่ 1.เขียนจำนวนธรรมชาติทั้งหมดตั้งแต่ 2 ถึง เช่น -
ขั้นตอนที่ 2.กำหนดค่าให้กับตัวแปร ซึ่งก็คือค่าเท่ากับจำนวนเฉพาะที่น้อยที่สุด
ขั้นตอนที่ 3ขีดฆ่าตัวเลขทั้งหมดตั้งแต่ ถึง ที่เป็นจำนวนทวีคูณของ ในรายการ นั่นคือ ตัวเลข:
ขั้นตอนที่ 4ค้นหาตัวเลขแรกที่ยังไม่ได้ข้ามในรายการที่มากกว่า และกำหนดค่าของตัวเลขนี้ให้กับตัวแปร
ขั้นตอนที่ 5ทำซ้ำขั้นตอนที่ 3 และ 4 จนกว่าจะถึงหมายเลข

กระบวนการใช้อัลกอริทึมจะมีลักษณะดังนี้:

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

การคาดเดาของโกลด์บัค

ปกหนังสือ “ลุงเปโตรสกับสมมติฐานโกลด์บัค”

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

• จริงหรือไม่ที่จำนวนคู่ทุกจำนวนที่มากกว่าสองสามารถแสดงเป็นผลรวมของจำนวนเฉพาะสองตัวได้ (สมมติฐานไบนารีโกลด์แบช)
• เป็นความจริงหรือไม่ที่จำนวนคี่ทุกจำนวนที่มากกว่า 5 สามารถแสดงเป็นผลรวมของจำนวนเฉพาะสามจำนวนได้ (สมมติฐานแบบไตรภาคของ Goldbach)

ควรจะกล่าวว่าสมมติฐานของ Goldbach แบบไตรภาคเป็นกรณีพิเศษของสมมติฐาน Goldbach แบบไบนารีหรือตามที่นักคณิตศาสตร์กล่าวว่าสมมติฐานของ Goldbach แบบไตรภาคนั้นอ่อนแอกว่าสมมติฐานของ Goldbach แบบไบนารี

การคาดเดาของ Goldbach เป็นที่รู้จักอย่างกว้างขวางนอกชุมชนคณิตศาสตร์ในปี 2000 เนื่องจากมีการโฆษณาส่งเสริมการขายโดยบริษัทสำนักพิมพ์ Bloomsbury USA (USA) และ Faber and Faber (UK) สำนักพิมพ์เหล่านี้ได้ออกหนังสือ "Uncle Petros and Goldbach's Conjecture" โดยสัญญาว่าจะมอบรางวัล 1 ล้านดอลลาร์สหรัฐให้กับใครก็ตามที่พิสูจน์สมมติฐานของ Goldbach ภายใน 2 ปีนับจากวันที่ตีพิมพ์หนังสือเล่มนี้ บางครั้งรางวัลที่กล่าวถึงจากสำนักพิมพ์ก็สับสนกับรางวัลสำหรับการแก้ปัญหารางวัลมิลเลนเนียม อย่าพลาดเลย สมมติฐานของ Goldbach ไม่ได้ถูกจัดประเภทโดย Clay Institute ว่าเป็น "ความท้าทายแห่งสหัสวรรษ" แม้ว่าจะเกี่ยวข้องอย่างใกล้ชิดกับ สมมติฐานรีมันน์- หนึ่งใน "ความท้าทายแห่งสหัสวรรษ"

หนังสือ “เลขเด่น. เส้นทางยาวไกลสู่อนันต์"

ปกหนังสือ “โลกแห่งคณิตศาสตร์” จำนวนเฉพาะ. เส้นทางยาวไกลสู่อนันต์"

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

นอกจากนี้ ผมจะอ้างอิงตอนต้นของบทที่สองของหนังสือเล่มนี้ว่า “จำนวนเฉพาะเป็นหนึ่งในหัวข้อสำคัญที่นำเราไปสู่ต้นกำเนิดของคณิตศาสตร์ จากนั้น ไปตามเส้นทางของความซับซ้อนที่เพิ่มขึ้น นำเราไปสู่แถวหน้าของ วิทยาศาสตร์สมัยใหม่ ดังนั้น การสืบย้อนประวัติศาสตร์อันน่าทึ่งและซับซ้อนของทฤษฎีจำนวนเฉพาะจะมีประโยชน์มาก ไม่ว่าจะเป็นการพัฒนาทฤษฎีจำนวนเฉพาะได้อย่างไร ข้อเท็จจริงและความจริงที่ปัจจุบันเป็นที่ยอมรับโดยทั่วไปถูกรวบรวมได้อย่างไร ในบทนี้ เราจะดูว่านักคณิตศาสตร์หลายรุ่นศึกษาตัวเลขธรรมชาติอย่างรอบคอบเพื่อค้นหากฎที่ทำนายการปรากฏของจำนวนเฉพาะ ซึ่งเป็นกฎที่เข้าใจยากมากขึ้นเมื่อการค้นหาดำเนินไป นอกจากนี้เรายังจะดูรายละเอียดเกี่ยวกับบริบททางประวัติศาสตร์: เงื่อนไขที่นักคณิตศาสตร์ทำงานและขอบเขตงานของพวกเขาเกี่ยวข้องกับการปฏิบัติลึกลับและกึ่งศาสนาซึ่งค่อนข้างแตกต่างจากวิธีการทางวิทยาศาสตร์ที่ใช้ในยุคของเรา อย่างไรก็ตาม พื้นดินได้รับการจัดเตรียมอย่างช้าๆ และด้วยความยากลำบากสำหรับมุมมองใหม่ๆ ซึ่งเป็นแรงบันดาลใจให้กับแฟร์มาต์และออยเลอร์ในศตวรรษที่ 17 และ 18”

ตัวเลขมีความแตกต่างกัน: ธรรมชาติ ตรรกยะ ตรรกศาสตร์ จำนวนเต็มและเศษส่วน บวกและลบ เชิงซ้อนและจำนวนเฉพาะ คี่และคู่ จริง ฯลฯ จากบทความนี้ คุณจะพบว่าจำนวนเฉพาะคืออะไร

ตัวเลขใดในภาษาอังกฤษเรียกว่า "ง่าย"

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

ตัวเลขประกอบ

สิ่งที่ตรงกันข้ามกับจำนวนเฉพาะคือจำนวนประกอบ พวกมันยังเป็นธรรมชาติเช่นกัน มากกว่า 1 ตัว แต่ไม่มีสองตัว แต่มีตัวหารมากกว่า ตัวอย่างเช่น ตัวเลข 4, 6, 8, 9 ฯลฯ นั้นเป็นจำนวนธรรมชาติ ประกอบ แต่ไม่ใช่จำนวนเฉพาะ อย่างที่คุณเห็น พวกนี้ส่วนใหญ่เป็นเลขคู่ แต่ไม่ใช่ทั้งหมด แต่ “สอง” เป็นจำนวนคู่และเป็น “จำนวนแรก” ในชุดจำนวนเฉพาะ

ลำดับต่อมา

ในการสร้างชุดของจำนวนเฉพาะ จำเป็นต้องเลือกจากจำนวนธรรมชาติทั้งหมด โดยคำนึงถึงคำจำกัดความของจำนวนนั้น กล่าวคือ คุณต้องกระทำการโดยขัดแย้งกัน จำเป็นต้องตรวจสอบจำนวนธรรมชาติบวกแต่ละตัวเพื่อดูว่ามีตัวหารมากกว่าสองตัวหรือไม่ เรามาลองสร้างอนุกรม (ลำดับ) ที่ประกอบด้วยจำนวนเฉพาะกัน รายการเริ่มต้นด้วยสอง ตามด้วยสาม เนื่องจากรายการจะหารด้วยตัวมันเองและหนึ่งเท่านั้น พิจารณาหมายเลขสี่ มันมีตัวหารนอกเหนือจากสี่กับหนึ่งหรือเปล่า? ใช่ จำนวนนั้นคือ 2 ดังนั้น 4 จึงไม่ใช่จำนวนเฉพาะ ห้ายังเป็นจำนวนเฉพาะ (หารด้วยจำนวนอื่นไม่ลงตัว ยกเว้น 1 และ 5) แต่หกหารลงตัว และโดยทั่วไป หากคุณติดตามเลขคู่ทั้งหมด คุณจะสังเกตได้ว่ายกเว้น "สอง" ไม่มีตัวใดที่เป็นจำนวนเฉพาะ จากนี้ เราสรุปได้ว่าจำนวนคู่ (ยกเว้น 2) ไม่ใช่จำนวนเฉพาะ การค้นพบอีกอย่าง: จำนวนทั้งหมดที่หารด้วยสามลงตัว ยกเว้นสามตัวนั้น ไม่ว่าจะเป็นเลขคู่หรือคี่ ก็ไม่ใช่จำนวนเฉพาะเช่นกัน (6, 9, 12, 15, 18, 21, 24, 27 ฯลฯ) เช่นเดียวกับตัวเลขที่หารด้วยห้าและเจ็ดลงตัว ฝูงชนทั้งหมดของพวกเขาก็ไม่ง่ายเช่นกัน มาสรุปกัน ดังนั้น ตัวเลขหลักเดียวแบบธรรมดาจะรวมเลขคี่ทั้งหมด ยกเว้น 1 และ 9 และแม้แต่ "สอง" ก็เป็นเลขคู่ ตัวหลักสิบ (10, 20,... 40 ฯลฯ) ไม่ใช่เรื่องง่าย จำนวนเฉพาะสองหลัก สามหลัก ฯลฯ สามารถกำหนดได้ตามหลักการข้างต้น: ถ้าไม่มีตัวหารอื่นนอกจากตัวมันเองและหนึ่งตัว

ทฤษฎีเกี่ยวกับคุณสมบัติของจำนวนเฉพาะ

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

จำนวนเฉพาะคือ "ส่วนประกอบ" ของจำนวนธรรมชาติ

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

ค้นหาเลขเด่น การทดสอบความเรียบง่าย

นักวิทยาศาสตร์หลายคนจากยุคต่างๆ พยายามค้นหาหลักการ (ระบบ) บางประการในการค้นหารายการจำนวนเฉพาะ วิทยาศาสตร์รู้จักระบบที่เรียกว่าตะแกรงแอตกิน ตะแกรงซุนดาร์ธรรม และตะแกรงเอราทอสเธเนส อย่างไรก็ตาม ไม่ได้ให้ผลลัพธ์ที่มีนัยสำคัญใดๆ และใช้การทดสอบง่ายๆ เพื่อค้นหาจำนวนเฉพาะ นักคณิตศาสตร์ยังสร้างอัลกอริธึมด้วย มักเรียกว่าการทดสอบปฐมภูมิ ตัวอย่างเช่น มีการทดสอบที่พัฒนาโดย Rabin และ Miller มันถูกใช้โดยนักเข้ารหัส นอกจากนี้ยังมีการทดสอบ Kayal-Agrawal-Sasquena อย่างไรก็ตาม แม้จะมีความแม่นยำเพียงพอ แต่ก็เป็นเรื่องยากมากในการคำนวณ ซึ่งทำให้ความสำคัญในทางปฏิบัติลดลง

เซตของจำนวนเฉพาะมีขีดจำกัดหรือไม่?

นักวิทยาศาสตร์ชาวกรีกโบราณ Euclid เขียนไว้ในหนังสือ "Elements" ของเขาว่าเซตของจำนวนเฉพาะนั้นไม่มีที่สิ้นสุด เขากล่าวว่า: “ลองจินตนาการดูว่าจำนวนเฉพาะมีขีดจำกัด จากนั้นลองคูณมันเข้าด้วยกัน แล้วบวกหนึ่งเข้าไปในผลคูณ จำนวนที่ได้รับจากการกระทำง่ายๆ เหล่านี้ไม่สามารถหารด้วยชุดจำนวนเฉพาะใดๆ ได้ เพราะส่วนที่เหลือจะเป็นหนึ่งเสมอ ซึ่งหมายความว่ายังมีจำนวนอื่นที่ยังไม่รวมอยู่ในรายการจำนวนเฉพาะ ดังนั้นสมมุติฐานของเราจึงไม่เป็นจริง และเซตนี้ไม่มีขีดจำกัด นอกจากข้อพิสูจน์ของ Euclid แล้ว ยังมีสูตรที่ทันสมัยกว่าซึ่งมอบให้โดย Leonhard Euler นักคณิตศาสตร์ชาวสวิสในศตวรรษที่ 18 จากข้อมูลดังกล่าว ผลรวมส่วนกลับของผลรวมของตัวเลข n ตัวแรกจะเพิ่มขึ้นอย่างไม่จำกัดเมื่อจำนวน n เพิ่มขึ้น และนี่คือสูตรของทฤษฎีบทเกี่ยวกับการแจกแจงของจำนวนเฉพาะ: (n) เพิ่มขึ้นเมื่อ n/ln (n)

จำนวนเฉพาะที่ใหญ่ที่สุดคืออะไร?

ลีโอนาร์ด ออยเลอร์ คนเดียวกันสามารถหาจำนวนเฉพาะที่มีค่ามากที่สุดในช่วงเวลาของเขาได้ นี่คือ 2 31 - 1 = 2147483647 อย่างไรก็ตามภายในปี 2013 มีการคำนวณหมายเลขเฉพาะที่ใหญ่ที่สุดอีกรายการหนึ่งที่แม่นยำที่สุด - 2 57885161 - 1 เรียกว่าหมายเลข Mersenne ประกอบด้วยทศนิยมประมาณ 17 ล้านหลัก อย่างที่คุณเห็น จำนวนที่นักวิทยาศาสตร์ในศตวรรษที่ 18 พบนั้นน้อยกว่าจำนวนนี้หลายเท่า มันควรจะเป็นเช่นนั้น เพราะออยเลอร์ดำเนินการคำนวณนี้ด้วยตนเอง ในขณะที่คอมพิวเตอร์ร่วมสมัยของเราอาจได้รับความช่วยเหลือจากคอมพิวเตอร์ ยิ่งไปกว่านั้น หมายเลขนี้ได้มาจากคณะคณิตศาสตร์ในแผนกหนึ่งของอเมริกา ตัวเลขที่ตั้งชื่อตามนักวิทยาศาสตร์คนนี้ผ่านการทดสอบความเป็นเอกของ Luc-Lemaire อย่างไรก็ตาม วิทยาศาสตร์ไม่ต้องการหยุดอยู่แค่นั้น มูลนิธิ Electronic Frontier Foundation ซึ่งก่อตั้งขึ้นในปี 1990 ในสหรัฐอเมริกา (EFF) ได้เสนอรางวัลเป็นเงินสำหรับการค้นหาจำนวนเฉพาะจำนวนมาก และหากจนถึงปี 2013 รางวัลนี้มอบให้กับนักวิทยาศาสตร์ที่สามารถค้นพบพวกมันได้จากทศนิยม 1 ถึง 10 ล้านทศนิยม ในปัจจุบันตัวเลขนี้ก็สูงถึงจาก 100 ล้านถึง 1 พันล้าน รางวัลมีตั้งแต่ 150 ถึง 250,000 ดอลลาร์สหรัฐ

ชื่อของจำนวนเฉพาะพิเศษ

ตัวเลขเหล่านั้นที่พบเนื่องจากอัลกอริธึมที่สร้างขึ้นโดยนักวิทยาศาสตร์บางคนและผ่านการทดสอบความเรียบง่ายเรียกว่าพิเศษ นี่คือบางส่วนของพวกเขา:

1. เมอร์สเซ่น.

4. คัลเลน.

6. มิลส์ และคณะ

ความเรียบง่ายของตัวเลขเหล่านี้ ซึ่งตั้งชื่อตามนักวิทยาศาสตร์ข้างต้น สร้างขึ้นโดยใช้การทดสอบต่อไปนี้:

1. ลุค-เลอแมร์

2. เปปิน่า.

3. รีเซล.

4. Billhart - Lemaire - เซลฟริดจ์ และคนอื่นๆ

วิทยาศาสตร์สมัยใหม่ไม่ได้หยุดอยู่แค่นั้น และในอนาคตอันใกล้นี้ โลกจะได้เรียนรู้ชื่อของผู้ที่สามารถคว้ารางวัล 250,000 ดอลลาร์สหรัฐฯ ได้โดยการค้นหาจำนวนเฉพาะที่มากที่สุด

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

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

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

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

เรียนรู้เกี่ยวกับหลุมพรางของทฤษฎีบทเล็กๆ ของแฟร์มาต์ตัวเลขทั้งหมดที่ไม่ตรงตามเงื่อนไขการทดสอบจะเป็นตัวเลขประกอบ แต่ตัวเลขที่เหลือเป็นเพียงตัวเลขเท่านั้น อาจจะจัดอยู่ในประเภทง่าย หากคุณต้องการหลีกเลี่ยงผลลัพธ์ที่ไม่ถูกต้อง ให้มองหา nในรายการ "หมายเลขคาร์ไมเคิล" (หมายเลขคอมโพสิตที่ตรงตามการทดสอบนี้) และ "หมายเลขเฟอร์มาต์หลอกไพรม์" (ตัวเลขเหล่านี้ตรงตามเงื่อนไขการทดสอบสำหรับบางค่าเท่านั้น ก).

หากสะดวกให้ใช้การทดสอบ Miller-Rabinแม้ว่าวิธีนี้จะค่อนข้างยุ่งยากในการคำนวณด้วยมือ แต่มักใช้ในโปรแกรมคอมพิวเตอร์ ให้ความเร็วที่ยอมรับได้และก่อให้เกิดข้อผิดพลาดน้อยกว่าวิธีของแฟร์มาต์ จำนวนประกอบจะไม่ได้รับการยอมรับเป็นจำนวนเฉพาะหากมีการคำนวณมากกว่า ¼ ของค่า ก- หากคุณสุ่มเลือกค่าที่แตกต่างกัน กและสำหรับทั้งหมดนั้นการทดสอบจะให้ผลลัพธ์ที่เป็นบวกเราสามารถสรุปได้อย่างมั่นใจว่าค่อนข้างสูง nเป็นจำนวนเฉพาะ

สำหรับจำนวนจำนวนมาก ให้ใช้เลขคณิตแบบโมดูลาร์หากคุณไม่มีเครื่องคิดเลขพร้อม mod หรือเครื่องคิดเลขของคุณไม่ได้ออกแบบมาเพื่อรองรับจำนวนจำนวนมาก ให้ใช้คุณสมบัติของกำลังและเลขคณิตแบบแยกส่วนเพื่อทำให้การคำนวณง่ายขึ้น ด้านล่างนี้เป็นตัวอย่างสำหรับ 3 50 (\รูปแบบการแสดงผล 3^(50))รุ่น 50:

• เขียนนิพจน์ใหม่ในรูปแบบที่สะดวกยิ่งขึ้น: mod 50 เมื่อทำการคำนวณด้วยตนเองอาจจำเป็นต้องทำให้ง่ายขึ้นเพิ่มเติม
• (3 25 ∗ 3 25) (\displaystyle (3^(25)*3^(25))) mod 50 = mod 50 mod 50) mod 50 ที่นี่เราคำนึงถึงคุณสมบัติของการคูณแบบแยกส่วน
• 3 25 (\รูปแบบการแสดงผล 3^(25))ม็อด 50 = 43
• (3 25 (\displaystyle (3^(25))รุ่น 50 ∗ 3 25 (\displaystyle *3^(25))รุ่น 50) รุ่น 50 = (43 ∗ 43) (\displaystyle (43*43))รุ่น 50
• = 1849 (\displaystyle =1849)รุ่น 50
• = 49 (\displaystyle =49).