Анхны тоо гэж юу вэ? Энэ тоо анхны уу эсвэл нийлмэл тоо юу? Анхны тооны шинж чанарууд

Теорем.

Хязгааргүй тооны анхны тоо байдаг.

Баталгаа.

Энэ нь тийм биш гэж бодъё. Өөрөөр хэлбэл, зөвхөн 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 нь энэ нийлбэрийн хоёр дахь гишүүнийг хуваах ёстой бөгөөд энэ нь нэгтэй тэнцүү боловч энэ нь боломжгүй юм.

Иймээс урьдчилж тогтоосон анхны тоонуудын тоонд ороогүй шинэ анхны тоо үргэлж олддог нь батлагдсан. Тиймээс хязгааргүй олон анхны тоо байдаг.

Тиймээс, анхны тоо нь хязгааргүй байдаг тул анхны тооны хүснэгтийг эмхэтгэхдээ та үргэлж дээрээс ямар нэг тоогоор, ихэвчлэн 100, 1,000, 10,000 гэх мэтийг хязгаарладаг.

Eratosthenes шигшүүр

Одоо бид анхны тоонуудын хүснэгт үүсгэх аргуудын талаар ярилцах болно. Бид 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 хүртэлх тоонууд руу шилжинэ.

Анхны тооны хүснэгтийг эмхэтгэх энэ арга нь тийм ч тохиромжтой биш юм. Ямар ч байсан тэр оршин тогтнох эрхтэй. Бүхэл тоонуудын хүснэгтийг байгуулах энэ аргын тусламжтайгаар та хуваагдах шалгуурыг ашиглаж болох бөгөөд энэ нь хуваагчийг олох үйл явцыг бага зэрэг хурдасгах болно гэдгийг анхаарна уу.

Энгийн тоонуудын хүснэгтийг үүсгэх илүү тохиромжтой арга бий. Нэрэнд байгаа "шигшүүр" гэсэн үг нь санамсаргүй биш юм, учир нь энэ аргын үйлдэл нь энгийн тоонуудыг нийлмэлээс салгахын тулд бүхэл тоо, том нэгжийг Эратосфен шигшүүрээр "шилж" хийхэд тусалдаг.

50 хүртэлх анхны тоонуудын хүснэгтийг эмхэтгэхдээ Эратосфен шигшүүр ажиллаж байгааг харуулъя.

Эхлээд 2, 3, 4, ..., 50 гэсэн тоонуудыг дарааллаар нь бич.

Эхний бичигдсэн 2 тоо нь анхны тоо юм. Одоо 2-р тооноос эхлэн бид дараалсан хоёр тоогоор баруун тийш шилжиж, эмхэтгэж буй тооны хүснэгтийн төгсгөлд хүрэх хүртлээ эдгээр тоонуудыг таслав. Энэ нь хоёрын үржвэр бүхий бүх тоог хасах болно.

2-ын дараах эхний зураасгүй тоо нь 3 байна. Энэ тоо нь анхны тоо юм. Одоо 3-р тооноос эхлэн бид баруун тийш гурван тоогоор (аль хэдийн таслагдсан тоонуудыг харгалзан) дараалан зурж, тэдгээрийг хасна. Энэ нь гурвын үржвэр бүхий бүх тоог хасах болно.

3-ын дараах эхний зураасгүй тоо нь 5 байна. Энэ тоо нь анхны тоо юм. Одоо 5-ын тооноос бид баруун тийш 5 тоогоор тогтмол шилжиж (бид өмнө нь зурсан тоонуудыг харгалзан үздэг) тэдгээрийг хасдаг. Энэ нь тавын үржвэр бүхий бүх тоог хасах болно.

Дараа нь бид 7-ын үржвэр, дараа нь 11-ийн үржвэр гэх мэт тоонуудыг таслана. Гаргах тоо байхгүй бол процесс дуусна. Эратосфен шигшүүрээр олж авсан 50 хүртэлх анхны тоонуудын хүснэгтийг доор харуулав. Бүх хөндлөн огтлолцоогүй тоонууд анхны тоонууд, бүх зураастай тоонууд нь нийлмэл тоо юм.

Мөн Эратосфен шигшүүрээр анхны тоонуудын хүснэгтийг эмхэтгэх үйл явцыг хурдасгах теоремыг томъёолж, баталъя.

Теорем.

Нэгээс өөр a нийлмэл тооны хамгийн бага эерэг хуваагч нь -ээс хэтрэхгүй, хаана нь a -аас байна.

Баталгаа.

Нэгээс ялгаатай нийлмэл a тооны хамгийн бага хуваагчийг b үсгээр тэмдэглэе (б тоо нь анхны догол мөрийн эхэнд батлагдсан теоремоос дараах байдлаар). Дараа нь a=b·q (энд q нь бүхэл тоог үржүүлэх дүрмээс үүсэлтэй эерэг бүхэл тоо), (b>q-ийн хувьд b нь a-ийн хамгийн бага хуваагч байх нөхцөл зөрчигдсөн) бүхэл q байна. , a=q·b ) тэгшитгэлийн улмаас q нь мөн a тооны хуваагч учраас ). Тэгш бус байдлын хоёр талыг эерэг ба нэгээс их бүхэл тоогоор үржүүлснээр (бидэнд үүнийг хийхийг зөвшөөрдөг) бид , аль нь болон .

Эратосфен шигшүүрийн талаар батлагдсан теорем бидэнд юу өгдөг вэ?

Нэгдүгээрт, анхны b-ийн үржвэр болох нийлмэл тоонуудыг хасахдаа тэнцүү тоогоор эхлэх ёстой (энэ нь тэгш бус байдлаас үүдэлтэй). Жишээлбэл, хоёрын үржвэртэй тоог 4-ийн тоогоор, гурвын үржвэрийг 9-ээр, тавын үржвэрийг 25-ын тоогоор гэх мэтээр таслах хэрэгтэй.

Хоёрдугаарт, анхны тоонуудын үржвэр болох бүх нийлмэл тоо нь -ээс хэтрэхгүй байх үед Эратосфен шигшүүрээр n хүртэлх анхны тоонуудын хүснэгтийг эмхэтгэсэн гэж үзэж болно. Бидний жишээнд n=50 (бид 50 хүртэлх анхны тоонуудын хүснэгтийг хийж байгаа тул) Эратосфен шигшүүр нь 2, 3, 5, 7 анхны тоонуудын үржвэр бүхий бүх нийлмэл тоог хасах ёстой. арифметик квадрат язгуураас 50-аас хэтрэхгүй. Өөрөөр хэлбэл, 11, 13, 17, 19, 23 гэх мэт 47 хүртэлх анхны анхны тоонуудын үржвэр болох тоонуудыг хайж олох шаардлагагүй, учир нь тэдгээрийг аль хэдийн жижиг анхны тоо 2-ын үржвэр болгон таслах болно. , 3, 5 ба 7.

Энэ тоо анхны уу эсвэл нийлмэл тоо юу?

Зарим даалгаварт өгөгдсөн тоо анхны эсвэл нийлмэл тоо эсэхийг олж мэдэх шаардлагатай. Ерөнхийдөө энэ даалгавар нь энгийн зүйлээс хол байна, ялангуяа бичвэр нь нэлээд олон тэмдэгтээс бүрддэг тоонуудын хувьд. Ихэнх тохиолдолд та үүнийг шийдвэрлэх тодорхой арга замыг хайх хэрэгтэй. Гэсэн хэдий ч бид энгийн тохиолдлуудад сэтгэлгээний галт тэрэг рүү чиглүүлэхийг хичээх болно.

Мэдээжийн хэрэг, та өгөгдсөн тоог нийлмэл гэдгийг батлахын тулд хуваагдах тестийг ашиглаж болно. Жишээлбэл, хуваагдах чадварыг шалгах тест нь тухайн тоо нэгээс их эерэг бүхэл тоонд хуваагддаг болохыг харуулсан бол анхны тоо нь нийлмэл тоо юм.

Жишээ.

898,989,898,989,898,989 нь нийлмэл тоо гэдгийг батал.

Шийдэл.

Энэ тооны цифрүүдийн нийлбэр нь 9·8+9·9=9·17. 9·17-той тэнцэх тоо 9-д хуваагддаг тул 9-д хуваагдах замаар анхны тоо нь мөн 9-д хуваагддаг гэж хэлж болно. Тиймээс энэ нь нийлмэл юм.

Энэ аргын мэдэгдэхүйц сул тал бол хуваагдах шалгуур нь тооны анхны байдлыг батлах боломжийг олгодоггүй явдал юм. Тиймээс, тоо нь анхны эсвэл нийлмэл эсэхийг шалгахдаа аливаа зүйлийг өөрөөр хийх хэрэгтэй.

Хамгийн логик арга бол өгөгдсөн тооны бүх хуваагчийг оролдох явдал юм. Хэрэв боломжит хуваагчдын аль нь ч өгөгдсөн тооны жинхэнэ хуваагч биш бол энэ тоо анхны тоо байх болно, үгүй ​​бол нийлмэл болно. Өмнөх догол мөрөнд нотлогдсон теоремуудаас үзэхэд өгөгдсөн a тооны хуваагчийг -аас хэтрэхгүй анхны тоонуудаас хайх ёстой. Тиймээс, өгөгдсөн a тоог анхны тоонд (анхны тоон хүснэгтээс авах боломжтой) дараалан хувааж, а тооны хуваагчийг олохыг оролдож болно. Хэрэв хуваагч олдвол а тоо нийлмэл байна. -ээс хэтрэхгүй анхны тоонуудын дунд а тоог хуваагч байхгүй бол а тоо анхны байна.

Жишээ.

Тоо 11 723 энгийн эсвэл нийлмэл үү?

Шийдэл.

11723-ын хуваагч ямар анхны тоо хүртэл байж болохыг олж мэдье. Үүнийг хийхийн тулд үнэлж үзье.

Энэ нь маш ойлгомжтой , 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 тоог бичигдсэн анхны тоонуудын аль нэгэнд хуваавал нийлмэл тоо болно. Хэрэв энэ нь бичигдсэн анхны тоонуудын аль нэгэнд хуваагдахгүй бол анхны тоо нь анхны тоо болно.

Бид энэ бүхэл бүтэн, нэгэн хэвийн хуваагдах үйл явцыг дүрслэхгүй. 11723 гэж шууд хэлье

• Орчуулга

Анхны тоонуудын шинж чанарыг эртний Грекийн математикчид анх судалж байжээ. Пифагорын сургуулийн математикчид (МЭӨ 500-300 он) анхны тооны ид шидийн болон тоон шинж чанарыг сонирхож байв. Тэд төгс, найрсаг тооны тухай санааг анх гаргаж ирсэн.

Төгс тоо нь өөртэй нь тэнцүү хуваагчдын нийлбэртэй байдаг. Жишээлбэл, 6 тооны хуваагч нь 1, 2, 3. 1 + 2 + 3 = 6. 28 тооны хуваагч нь 1, 2, 4, 7, 14. Мөн 1 + 2 + 4 + 7 + 14 = 28.

Хэрэв нэг тооны зохих хуваагчдын нийлбэр нь нөгөө тоотой тэнцүү бол тоонуудыг нөхөрсөг гэж нэрлэдэг ба эсрэгээр - жишээлбэл, 220 ба 284. Төгс тоо нь өөртөө ээлтэй гэж хэлж болно.

МЭӨ 300 онд Евклидийн элементүүдийн үед. Анхны тооны тухай хэд хэдэн чухал баримтууд аль хэдийн батлагдсан. Эвклид "Элементүүдийн IX" номонд хязгааргүй олон тооны анхны тоо байдгийг нотолсон. Дашрамд хэлэхэд энэ нь зөрчилдөөнөөр нотлох баримтыг ашиглах анхны жишээнүүдийн нэг юм. Тэрээр мөн арифметикийн үндсэн теоремыг нотолж байна - бүхэл тоо бүрийг анхны тоонуудын үржвэр хэлбэрээр өвөрмөц байдлаар илэрхийлж болно.

Мөн тэрээр хэрэв 2n-1 тоо анхны бол 2n-1 * (2n-1) тоо төгс болно гэдгийг харуулсан. Өөр нэг математикч Эйлер 1747 онд бүх тэгш төгс тоог ийм хэлбэрээр бичиж болно гэдгийг харуулж чадсан. Өнөөдрийг хүртэл сондгой төгс тоо байгаа эсэх нь тодорхойгүй байна.

МЭӨ 200 онд. Грекийн Эратосфенчууд анхны тоог олох алгоритмыг Эратосфенийн шигшүүр гэж нэрлэжээ.

Дараа нь Дундад зууны үетэй холбоотой анхны тоог судлах түүхэнд томоохон завсарлага гарсан.

Дараах нээлтүүдийг 17-р зууны эхээр математикч Фермат хийсэн. Тэрээр 4n+1 хэлбэрийн аль ч анхны тоог хоёр квадратын нийлбэр байдлаар онцгойлон бичиж болно гэсэн Альберт Жирардын таамаглалыг баталж, мөн дурын тоог дөрвөн квадратын нийлбэр болгон бичиж болно гэсэн теоремыг томьёолжээ.

Тэрээр олон тооны хүчин зүйлүүдийг ялгах шинэ аргыг боловсруулж, 2027651281 = 44021 × 46061 тоон дээр харуулсан. Мөн тэрээр Фермагийн жижиг теоремыг баталсан: хэрвээ p нь анхны тоо бол ямар ч бүхэл тооны хувьд a p = модуль гэдэг нь үнэн байх болно. х.

Энэхүү мэдэгдэл нь "Хятадын таамаглал" гэж нэрлэгддэг байсан зүйлийн тал хувийг нотолж байгаа бөгөөд 2000 жилийн тэртээгээс үүссэн: 2 n -2 нь n-д хуваагдах тохиолдолд л n бүхэл тоо анхны байна. Таамаглалын хоёр дахь хэсэг нь худал болсон - жишээлбэл, 2,341 - 2 нь 341-д хуваагддаг боловч 341 тоо нь нийлмэл байдаг: 341 = 31 × 11.

Фермагийн Бяцхан теорем нь тоон онолын бусад олон үр дүнгийн үндэс суурь болж, тоонууд анхны тоо мөн эсэхийг шалгах аргуудын ихэнх нь өнөөг хүртэл ашиглагдаж байна.

Ферма өөрийн үеийнхэнтэй, ялангуяа Марен Мерсенне хэмээх ламтай их захидал бичдэг байв. Тэрээр нэгэн захидалдаа хэрэв n нь хоёрын зэрэгтэй байвал 2 n +1 хэлбэрийн тоонууд үргэлж анхны байх болно гэсэн таамаглал дэвшүүлжээ. Тэрээр үүнийг n = 1, 2, 4, 8 ба 16-д туршиж үзсэн бөгөөд n нь хоёрын зэрэглэл биш тохиолдолд энэ тоо нь анхны тоо байх албагүй гэдэгт итгэлтэй байв. Эдгээр тоонуудыг Фермагийн тоо гэж нэрлэдэг бөгөөд 100 жилийн дараа л дараагийн тоо болох 2 32 + 1 = 4294967297 нь 641-д хуваагддаг тул анхны тоо биш гэдгийг Эйлер харуулсан.

Хэрэв n нь нийлмэл бол энэ тоо нь өөрөө нийлмэл гэдгийг харуулахад хялбар байдаг тул 2 n - 1 хэлбэрийн тоонууд бас судалгааны сэдэв болсон. Эдгээр тоонуудыг тэрээр маш их судалсан тул Мерсений тоо гэж нэрлэдэг.

Гэхдээ n нь анхны байх 2 n - 1 хэлбэрийн бүх тоо анхных биш. Жишээ нь, 2 11 - 1 = 2047 = 23 * 89. Үүнийг 1536 онд анх илрүүлсэн.

Олон жилийн турш ийм төрлийн тоонууд математикчдад мэдэгдэж байсан хамгийн том анхны тоог өгдөг байв. M 19-ийг 1588 онд Каталди нотолсон бөгөөд Эйлер M 31-ийг мөн анхны анхны тоо гэдгийг батлах хүртэл 200 жилийн турш мэдэгдэж байсан хамгийн том анхны тоо байсан юм. Энэ рекорд дахин нэг зуун жил хадгалагдсан бөгөөд дараа нь Лукас M 127 нь анхны (мөн энэ нь аль хэдийн 39 оронтой тоо) гэдгийг харуулсан бөгөөд үүний дараа компьютер гарч ирснээр судалгаа үргэлжилсэн.

1952 онд M 521, M 607, M 1279, M 2203, M 2281 тоонуудын анхны байдал нь батлагдсан.

2005 он гэхэд 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-ийг өгнө гэсэн үг боловч цуваа зөрүүтэй хэвээр байна.

Өнгөц харахад анхны тоонууд бүхэл тоонуудын дунд нэлээд санамсаргүй байдлаар тархсан юм шиг санагддаг. Жишээлбэл, 10000000-аас өмнөх 100 тоон дотор 9 анхны тоо байдаг бөгөөд энэ утгын дараа шууд 100 тоон дотор ердөө 2 байдаг. Гэхдээ том сегментүүдэд анхны тоонууд нэлээд жигд тархсан байдаг. Лежендре, Гаусс нар тэдгээрийг түгээх асуудлыг авч үзсэн. Гаусс нэг удаа найздаа 15 минутын дараа дараагийн 1000 тооны анхны тоог тоолдог гэж хэлсэн байдаг. Амьдралынхаа төгсгөлд тэрээр 3 сая хүртэлх бүх анхны тоог тоолжээ. Лежендре, Гаусс нар том n-ийн хувьд анхны нягт нь 1/log(n) байна гэж адилхан тооцоолсон. Лежендре 1-ээс n хүртэлх анхны тооны тоог тооцоолсон

π(n) = n/(лог(n) - 1.08366)

Гаусс нь логарифмын интегралтай адил юм

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

2-оос n хүртэлх интеграцийн интервалтай.

Анхны нягтрал 1/log(n)-ийн тухай өгүүлбэрийг Ерөнхий тархалтын теорем гэж нэрлэдэг. Тэд 19-р зууны турш үүнийг батлахыг хичээсэн бөгөөд Чебышев, Риман нар ахиц дэвшилд хүрсэн. Тэд үүнийг Риманы зета функцийн тэгүүдийн тархалтын талаарх батлагдаагүй таамаглал болох Риманы таамаглалтай холбосон. Анхны тоонуудын нягтыг 1896 онд Хадамард, Валле-Пуссин нар нэгэн зэрэг нотолсон.

Анхны тооны онолд шийдэгдээгүй олон асуулт байсаар байгаа бөгөөд тэдгээрийн зарим нь хэдэн зуун жилийн настай.

• Ихэр анхны таамаглал нь бие биенээсээ 2-оор ялгаатай анхны тооны хязгааргүй тооны хосуудын тухай юм.
• Голдбахийн таамаглал: 4-өөс эхэлсэн тэгш тоог хоёр анхны тооны нийлбэрээр илэрхийлж болно.
• n 2 + 1 хэлбэрийн хязгааргүй тооны анхны тоо байдаг уу?
• n 2 ба (n + 1) 2 хооронд анхны тоог олох боломжтой юу? (n ба 2n хооронд үргэлж анхны тоо байдгийг Чебышев нотолсон)
• Фермагийн анхны тоо хязгааргүй гэж үү? 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 цифрээс бүрдэх ба 2007 онд нээгдсэн.

Хамгийн том хүчин зүйлийн анхны тоо (n төрлийн! ± 1) нь 147855! - 1. 142891 цифрээс бүрдэх ба 2002 онд олдсон.

Хамгийн том анхны анхны тоо (n# ± 1 хэлбэрийн тоо) нь 1098133# + 1 юм.

Шошго: шошго нэмэх

Хуваагчдыг тоолох.Тодорхойлолтоор тоо n 2 болон 1 ба өөрөөс бусад бүхэл тоонд тэгш хуваагдахгүй тохиолдолд л анхны байна. Дээрх томьёо нь шаардлагагүй алхмуудыг арилгаж, цагийг хэмнэдэг: жишээлбэл, тоо 3-т хуваагдах эсэхийг шалгасны дараа 9-д хуваагдах эсэхийг шалгах шаардлагагүй болно.

• Floor(x) функц нь x-г x-ээс бага буюу тэнцүү бүхэл тоо хүртэл дугуйруулна.

Модульчлагдсан арифметикийн талаар олж мэдэх."x mod y" (mod нь "modulo" буюу "модуль" гэсэн латин үгийн товчлол) үйлдэл нь "х-ийг у-д хувааж, үлдэгдлийг олох" гэсэн утгатай. Өөрөөр хэлбэл, модульчлагдсан арифметикийн хувьд тодорхой утгад хүрсний дараа үүнийг нэрлэдэг модуль, тоонууд дахин тэг болж "эргэдэг". Жишээлбэл, цаг нь 12 модультай цагийг барьдаг: 10, 11, 12 цагийг харуулж, дараа нь 1 рүү буцдаг.

• Олон тооны машинд горимын түлхүүр байдаг. Энэ хэсгийн төгсгөлд энэ функцийг олон тооны хувьд гараар хэрхэн үнэлэхийг харуулав.

Тодорхойлолт 1. анхны тоо− зөвхөн өөртөө болон 1-д хуваагддаг нэгээс их натурал тоо.

Өөрөөр хэлбэл, тоо нь зөвхөн хоёр ялгаатай натурал хуваагчтай бол анхны тоо юм.

Тодорхойлолт 2. Өөрөөсөө өөр нэг хуваагчтай аливаа натурал тоог дуудна нийлмэл тоо.

Өөрөөр хэлбэл анхны тоо биш натурал тоог нийлмэл тоо гэнэ. 1-р тодорхойлолтоос харахад нийлмэл тоо нь хоёроос илүү натурал хүчин зүйлтэй байдаг. Учир нь 1-ийн тоо анхны ч биш, нийлмэл ч биш нь зөвхөн нэг хуваагч 1-тэй бөгөөд үүнээс гадна анхны тоонуудтай холбоотой олон теоремууд нэгдмэл байдалд нийцдэггүй.

1 ба 2-р тодорхойлолтоос 1-ээс их эерэг бүхэл тоо нь анхны тоо эсвэл нийлмэл тоо байна.

Доорх нь 5000 хүртэлх анхны тоог харуулах програм юм. Нүднүүдийг бөглөж, "Create" товчийг дараад хэдэн секунд хүлээнэ үү.

Анхны тооны хүснэгт

Мэдэгдэл 1. Хэрэв х- анхны тоо ба адурын бүхэл тоо, дараа нь аль нэг нь ахуваасан х, эсвэл хТэгээд ахарьцуулах тоо.

Үнэхээр. Хэрэв хАнхны тоо нь зөвхөн өөртөө хуваагдана, хэрэв бол 1 болно а-д хуваагдахгүй х, дараа нь хамгийн том нийтлэг хуваагч аТэгээд х 1-тэй тэнцүү байна. Дараа нь хТэгээд ахарьцуулах тоо.

Мэдэгдэл 2. Хэрэв хэд хэдэн тооны үржвэр бол а 1 , а 2 , а 3, ... анхны тоонд хуваагддаг х, дараа нь ядаж нэг тоо а 1 , а 2 , а 3, ... хуваагддаг х.

Үнэхээр. Хэрэв тоонуудын аль нь ч хуваагдахгүй байсан бол х, дараа нь тоонууд а 1 , а 2 , а 3, ...-д хамаарах анхны тоонууд байх болно х. Гэхдээ үр дүн 3 ()-аас харахад тэдний бүтээгдэхүүн а 1 , а 2 , а 3, ...-ын хувьд мөн харьцангуй анхдагч байна х, энэ нь мэдэгдлийн нөхцөлтэй зөрчилдөж байна. Тиймээс ядаж нэг тоо нь хуваагддаг х.

Теорем 1. Аливаа нийлмэл тоог үргэлж өвөрмөц байдлаар, хязгаарлагдмал тооны анхны тооны үржвэр болгон төлөөлж болно.

Баталгаа. Болъё книйлмэл тоо, ба зөвшөөрөх а 1 нь 1 болон өөрөөсөө ялгаатай хуваагчдын нэг юм. Хэрэв а 1 нь нийлмэл, дараа нь 1-ээс гадна ба байна а 1 ба өөр хуваагч а 2. Хэрэв а 2 нь нийлмэл тоо, тэгвэл 1-ээс гадна ба байна а 2 ба өөр хуваагч а 3. Ингэж дүгнэж, тоонуудыг харгалзан үзэж байна а 1 , а 2 , а 3 , ... буурах ба энэ цуврал нь хязгаарлагдмал тооны гишүүнийг агуулна, бид зарим анхны тоонд хүрэх болно х 1 . Дараа нь кхэлбэрээр төлөөлж болно

Тооны хоёр задрал байна гэж бодъё к:

Учир нь k=p 1 х 2 х 3 ... энгийн тоонд хуваагддаг q 1, дараа нь ядаж нэг хүчин зүйл, жишээлбэл х 1 нь хуваагдана q 1 . Гэхдээ х 1 нь анхны тоо бөгөөд зөвхөн 1-д болон өөртөө хуваагддаг. Тиймээс х 1 =q 1 (учир нь q 1 ≠1)

Дараа нь (2) -аас хасч болно х 1 ба q 1:

Тиймээс, эхний тэлэлтэд нэг буюу хэд хэдэн удаа хүчин зүйл болж гарч буй анхны тоо бүр хоёр дахь тэлэлтэд хамгийн багадаа олон удаа, эсрэгээр хоёр дахь тэлэлтэд хүчин зүйл болж харагдах анхны тоо бүр гарч ирдэг гэдэгт бид итгэлтэй байна. нэг буюу хэд хэдэн удаа эхний өргөтгөлд дор хаяж ижил тооны удаа гарч ирнэ. Иймээс аливаа анхны тоо хоёр тэлэлтэд ижил тооны хүчин зүйл болж гарч ирдэг тул эдгээр хоёр тэлэлт ижил байна.■

Нийлмэл тооны өргөтгөл кдараах хэлбэрээр бичиж болно

Хаана х 1 , х 2, ... төрөл бүрийн анхны тоо, α, β, γ ... эерэг бүхэл тоо.

Өргөтгөл (3) гэж нэрлэдэг каноник тэлэлттоо.

Анхны тоо нь натурал тоонуудын цуваанд жигд бус тохиолддог. Эгнээний зарим хэсэгт тэдгээр нь илүү, заримд нь бага байдаг. Тоон цувралын дагуу цааш явах тусам нийтлэг анхны тоонууд бага байх болно. Асуулт гарч ирнэ, хамгийн том анхны тоо байдаг уу? Хязгааргүй олон анхны тоо байдгийг эртний Грекийн математикч Евклид баталжээ. Бид энэ нотолгоог доор харуулав.

Теорем 2. Анхны тооны тоо хязгааргүй.

Баталгаа. Хязгаарлагдмал тооны анхны тоо байна гэж бодъё, хамгийн том анхны тоо нь байг х. Бүх тоог илүү ихийг авч үзье х. Тайлбарын таамаглалаар эдгээр тоонууд нийлмэл байх ёстой бөгөөд хамгийн багадаа нэг анхны тоонд хуваагдах ёстой. Эдгээр бүх анхны тоог 1 дээр нэмсэн үржвэр болох тоог сонгоцгооё.

Тоо zилүү хучир нь 2халь хэдийн илүү х. хнь эдгээр анхны тоонуудын аль нэгэнд хуваагдахгүй, учир нь тус бүрд нь хуваахад 1-ийн үлдэгдэл гарна.Ингээд бид зөрчилдөж байна. Тиймээс хязгааргүй тооны анхны тоо байдаг.

Энэ теорем нь илүү ерөнхий теоремын онцгой тохиолдол юм:

Теорем 3. Арифметик прогресс өгөгдсөн байг

Дараа нь дурын анхны тоо орно n, багтсан байх ёстой м, тиймээс in nороогүй бусад үндсэн хүчин зүйлүүд ммөн үүнээс гадна эдгээр үндсэн хүчин зүйлүүд n-ээс илүүгүй удаа орно м.

Харин ч эсрэгээрээ. Хэрэв тооны анхны хүчин зүйл бүр nтоонд дор хаяж хэдэн удаа оруулсан байна м, Тэр мхуваасан n.

Мэдэгдэл 3. Болъё а 1 ,а 2 ,а 3,... төрөл бүрийн анхны тоонууд багтсан мТэгэхээр

Хаана би=0,1,...α , j=0,1,...,β , k=0,1,..., γ . анзаараарай, тэр α бихүлээн зөвшөөрдөг α +1 утгууд, β j хүлээн зөвшөөрч байна β +1 утгууд, γ к хүлээн зөвшөөрч байна γ +1 утгууд, ... .