วิธีตรวจสอบเลขเด่น วิธีค้นหาจำนวนเฉพาะ

ทฤษฎีบท.

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

การพิสูจน์.

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

คำตอบของ Ilya นั้นถูกต้อง แต่ไม่ละเอียดมาก อย่างไรก็ตาม ในศตวรรษที่ 18 เลขหนึ่งยังถือว่าเป็นจำนวนเฉพาะ ตัวอย่างเช่น นักคณิตศาสตร์ผู้ยิ่งใหญ่อย่างออยเลอร์และโกลด์บัค Goldbach เป็นผู้เขียนหนึ่งในเจ็ดปัญหาของสหัสวรรษ - สมมติฐานของ Goldbach สูตรดั้งเดิมระบุว่าเลขคู่ทุกจำนวนสามารถแสดงเป็นผลรวมของจำนวนเฉพาะสองตัวได้ ยิ่งไปกว่านั้น ในตอนแรก 1 ถูกนับว่าเป็นจำนวนเฉพาะ และเราจะเห็นว่า 2 = 1+1 นี่คือตัวอย่างที่เล็กที่สุดที่เป็นไปตามสูตรดั้งเดิมของสมมติฐาน ต่อมาได้รับการแก้ไข และสูตรก็ได้รูปแบบสมัยใหม่: “เลขคู่ทุกตัวที่เริ่มต้นด้วย 4 สามารถแสดงเป็นผลรวมของจำนวนเฉพาะสองตัวได้”

เรามาจำคำจำกัดความกัน จำนวนเฉพาะคือจำนวนธรรมชาติ p ที่มีตัวหารตามธรรมชาติเพียง 2 ตัวเท่านั้น คือ p เองและ 1 ข้อพิสูจน์จากคำจำกัดความ: จำนวนเฉพาะ p มีตัวหารเฉพาะเพียงตัวเดียว - ตัว p เอง

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

1 และ 0 ก่อให้เกิดคลาสของตัวเลขอีกประเภทหนึ่ง ซึ่งเป็นคลาสขององค์ประกอบที่เป็นกลางที่เกี่ยวข้องกับการดำเนินการ n-ary ในบางเซตย่อยของสนามพีชคณิต ยิ่งไปกว่านั้น ในส่วนของการดำเนินการบวก 1 ยังเป็นองค์ประกอบสร้างวงแหวนของจำนวนเต็มอีกด้วย

ด้วยการพิจารณานี้ การค้นหาสิ่งที่คล้ายคลึงกันของจำนวนเฉพาะในโครงสร้างพีชคณิตอื่นๆ จึงไม่ใช่เรื่องยาก สมมติว่าเรามีกลุ่มการคูณที่สร้างจากยกกำลัง 2 โดยเริ่มจาก 1: 2, 4, 8, 16, ... เป็นต้น 2 ทำหน้าที่เป็นองค์ประกอบที่สร้างสรรค์ที่นี่ จำนวนเฉพาะในกลุ่มนี้คือจำนวนที่มากกว่าองค์ประกอบที่เล็กที่สุด และหารด้วยตัวมันเองและองค์ประกอบที่เล็กที่สุดเท่านั้น ในกลุ่มของเรามีเพียง 4 คนเท่านั้นที่มีคุณสมบัติดังกล่าว ไม่มีจำนวนเฉพาะในกลุ่มของเราอีกต่อไป

ถ้า 2 เป็นจำนวนเฉพาะในกลุ่มของเราด้วย โปรดดูย่อหน้าแรก - อีกครั้งปรากฎว่ามีเพียง 2 เท่านั้นที่เป็นจำนวนเฉพาะ

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

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