เช็คเลขเด่นหรือ. วิธีค้นหาจำนวนเฉพาะ

ทฤษฎีบท.

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

การพิสูจน์.

สมมติว่านี่ไม่ใช่กรณี นั่นคือ สมมติว่ามีจำนวนเฉพาะ 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 เพื่อแยกอันธรรมดาออกจากอันประกอบ

เรามาแสดงการทำงานของตะแกรงเอราทอสเทนีสเมื่อรวบรวมตารางจำนวนเฉพาะมากถึง 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, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

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

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

จำนวนเฉพาะเป็นไปตามกฎใดๆ หรือไม่? ใช่แล้ว และพวกเขาค่อนข้างอยากรู้อยากเห็นด้วย

เช่น นักคณิตศาสตร์ชาวฝรั่งเศส เมอร์เซนย้อนกลับไปในศตวรรษที่ 16 เขาค้นพบว่าจำนวนเฉพาะจำนวนมากมีรูปแบบ 2^N - 1 ตัวเลขเหล่านี้เรียกว่าตัวเลขเมอร์เซน ไม่นานก่อนหน้านี้ ในปี ค.ศ. 1588 นักคณิตศาสตร์ชาวอิตาลี คาตัลดีค้นพบจำนวนเฉพาะ 2 19 - 1 = 524287 (ตามการจัดหมวดหมู่ของ Mersen เรียกว่า M19) ปัจจุบันตัวเลขนี้ดูค่อนข้างสั้น แต่ถึงแม้ตอนนี้เมื่อใช้เครื่องคิดเลข ก็อาจต้องใช้เวลาหลายวันในการตรวจสอบความเรียบง่าย แต่สำหรับศตวรรษที่ 16 มันเป็นงานที่ยิ่งใหญ่จริงๆ

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

ตัวอย่างเช่น คุณสามารถใช้เลขคู่ 2 ตัวก็ได้: 123456 และ 888777888

เมื่อใช้คอมพิวเตอร์ คุณจะพบผลรวมในรูปของจำนวนเฉพาะสองตัว: 123456 = 61813 + 61643 และ 888777888 = 444388979 + 444388909 สิ่งที่น่าสนใจในที่นี้คือ ยังไม่พบข้อพิสูจน์ที่แน่นอนของทฤษฎีบทนี้ แม้ว่าจะมี ความช่วยเหลือของคอมพิวเตอร์ได้รับการตรวจสอบเป็นตัวเลขที่มีศูนย์ 18 ตัว

มีทฤษฎีบทของนักคณิตศาสตร์อีกคนหนึ่ง ปิแอร์ แฟร์มาต์ค้นพบในปี 1640 ซึ่งบอกว่าหากจำนวนเฉพาะอยู่ในรูปแบบ 4*k+1 ก็จะสามารถแสดงเป็นผลบวกของกำลังสองของจำนวนอื่นๆ ได้ ตัวอย่างเช่น ในตัวอย่างของเรา จำนวนเฉพาะ 444388909 = 4*111097227 + 1 และจริงๆ แล้ว เมื่อใช้คอมพิวเตอร์คุณจะพบว่า 444388909 = 19197*19197 + 8710*8710

ทฤษฎีบทนี้ได้รับการพิสูจน์โดยออยเลอร์เพียง 100 ปีต่อมา

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

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

ความทันสมัย

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

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

ตัวอย่างเช่น หากเราใช้หมายเลขเฉพาะสองตัวคือ 444388979 และ 444388909 “คีย์ส่วนตัว” จะเป็น 444388979 และผลิตภัณฑ์ 197481533549433911 (444388979*444388909) จะถูกส่งต่อสาธารณะ เพียงรู้อีกครึ่งหนึ่งของคุณ คุณก็สามารถคำนวณตัวเลขที่หายไปและถอดรหัสข้อความด้วยตัวเลขนั้นได้

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

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

จำนวนเฉพาะจึงกลายเป็นว่าไม่ง่ายเลย และเรื่องราวของพวกมันไม่ได้จบเพียงแค่นั้นอย่างชัดเจน

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

ยานเดกซ์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