Hogyan szerezzünk prímszámot. "Prómszámok" könyv

Tétel.

Végtelen számú prímszám létezik.

Bizonyíték.

Tegyük fel, hogy ez nem így van. Vagyis tegyük fel, hogy csak n prímszám van, és ezek a prímszámok p 1, p 2, ..., p n. Mutassuk meg, hogy mindig találhatunk a feltüntetettektől eltérő prímszámot.

Tekintsük a p számot p 1 ·p 2 ·…·p n +1 értékkel. Nyilvánvaló, hogy ez a szám különbözik a p 1, p 2, ..., p n prímszámoktól. Ha a p szám prím, akkor a tétel bizonyított. Ha ez a szám összetett, akkor az előző tétel alapján ennek a számnak van egy prímosztója (p n+1-nek jelöljük). Mutassuk meg, hogy ez az osztó nem esik egybe a p 1, p 2, ..., p n számok egyikével sem.

Ha ez nem így lenne, akkor az oszthatósági tulajdonságok szerint a p 1 ·p 2 ·…·p n szorzatot p n+1-gyel osztanák. De a p szám is osztható p n+1-gyel, egyenlő a p 1 ·p 2 ·…·p n +1 összeggel. Ebből következik, hogy p n+1-nek el kell osztania ennek az összegnek a második tagját, amely egyenlő eggyel, de ez lehetetlen.

Így bebizonyosodott, hogy mindig lehet olyan új prímszámot találni, amely nem szerepel az előre meghatározott prímszámok között. Ezért végtelenül sok prímszám van.

Tehát abból a tényből adódóan, hogy végtelen számú prímszám van, a prímszámtáblázatok összeállításakor mindig felülről korlátozzuk magunkat valamilyen számra, általában 100, 1000, 10 000 stb.

Eratoszthenész szita

Most megvitatjuk a prímszámtáblázatok létrehozásának módjait. Tegyük fel, hogy egy táblázatot kell készítenünk prímszámokból 100-ig.

A probléma megoldásának legkézenfekvőbb módja a pozitív egész számok 2-től 100-ig terjedő szekvenciális ellenőrzése, hogy van-e olyan pozitív osztó, amely nagyobb 1-nél és kisebb, mint a vizsgált szám (az oszthatóság tulajdonságaiból tudjuk hogy az osztó abszolút értéke ne haladja meg az osztalék abszolút értékét, nem nulla). Ha ilyen osztó nem található, akkor a vizsgált szám prímszám, és bekerül a prímszámtáblázatba. Ha ilyen osztó található, akkor a vizsgált szám összetett, NEM kerül be a prímszámok táblázatába. Ezt követően történik az átmenet a következő számra, amelyhez hasonlóan ellenőrzik az osztó meglétét.

Ismertesse az első néhány lépést.

A 2-es számmal kezdjük. A 2-es számnak nincs más pozitív osztója, mint 1 és 2. Ezért egyszerű, ezért beírjuk a prímszámok táblázatába. Itt azt kell mondani, hogy a 2 a legkisebb prímszám. Térjünk át a 3. számra. Az 1-től és 3-tól eltérő lehetséges pozitív osztója a 2. De a 3 nem osztható 2-vel, ezért a 3 prímszám, és a prímszámok táblázatában is szerepelnie kell. Térjünk át a 4-es számra. Pozitív osztói az 1-től és a 4-től eltérőek lehetnek a 2-es és a 3-as számok, ezeket ellenőrizzük. A 4 osztható 2-vel, ezért a 4 összetett szám, és nem kell szerepelni a prímszámok táblázatában. Kérjük, vegye figyelembe, hogy a 4 a legkisebb összetett szám. Térjünk át az 5-ös számra. Ellenőrizzük, hogy a 2, 3, 4 számok közül legalább az egyik osztója-e. Mivel az 5 nem osztható 2-vel, 3-mal vagy 4-gyel, ezért prímszám, és fel kell írni a prímszámok táblázatába. Ezután következik az átmenet a 6-os, 7-es számokra és így tovább 100-ig.

A prímszámtáblázat összeállításának ez a megközelítése messze nem ideális. Így vagy úgy, létjogosultsága van. Vegye figyelembe, hogy az egész számok táblázatának ezzel a módszerével oszthatósági kritériumokat használhat, ami kissé felgyorsítja az osztók keresésének folyamatát.

Van egy kényelmesebb módja prímszámtáblázat létrehozásának, az ún. A névben előforduló „szita” szó nem véletlen, mivel ennek a módszernek a hatásai mintegy segítik az egész számokat és a nagy egységeket Eratoszthenész szitáján keresztül „átszitálni”, hogy az egyszerűket elválasztsák az összetettektől.

Mutassuk meg Eratoszthenész szitáját működés közben, amikor prímszámokat tartalmazó táblázatot állítunk össze 50-ig.

Először írja le sorrendben a 2, 3, 4, ..., 50 számokat.

Az első írt szám, a 2, prím. Most a 2-es számtól sorban jobbra lépünk két számmal, és kihúzzuk ezeket a számokat, amíg el nem érjük az összeállítandó számtáblázat végét. Ezzel áthúz minden olyan számot, amely kettő többszöröse.

A 2-t követő első, át nem húzott szám a 3. Ez a szám prímszám. Most a 3-as számtól sorban három számmal haladunk jobbra (figyelembe véve a már áthúzott számokat), és áthúzzuk őket. Ez áthúzza az összes olyan számot, amely három többszöröse.

A 3-at követő első, át nem húzott szám az 5. Ez a szám prímszám. Most az 5-ös számtól következetesen 5 számmal haladunk jobbra (a korábban áthúzott számokat is figyelembe vesszük), és áthúzzuk őket. Ez áthúzza az összes számot, amely öt többszöröse.

Ezután kihúzzuk azokat a számokat, amelyek 7 többszörösei, majd 11 többszörösei, és így tovább. A folyamat akkor ér véget, amikor nincs több áthúzható szám. Az alábbiakban látható a prímszámok 50-ig terjedő táblázata, amelyet Eratosthenes szitája segítségével kaptunk. Minden át nem húzott szám prímszám, és minden áthúzott szám összetett.

Fogalmazjunk meg és bizonyítsunk be egy tételt is, amely felgyorsítja a prímszámtáblázat összeállítását Eratoszthenész szitája segítségével.

Tétel.

Az a összetett szám legkisebb pozitív osztója, amely különbözik egytől, nem haladja meg a -t, ahol a -ból van.

Bizonyíték.

Jelöljük b betűvel egy összetett a szám legkisebb osztóját, amely különbözik egytől (a b szám prím, ahogy az előző bekezdés legelején bizonyított tételből következik). Ekkor van olyan q egész szám, hogy a=b·q (itt q pozitív egész szám, ami az egész számok szorzásának szabályaiból következik), és (b>q esetén megsérül az a feltétel, hogy b a legkisebb osztója , mivel q is osztója az a számnak az a=q·b egyenlőség miatt). Ha az egyenlőtlenség mindkét oldalát megszorozzuk egy pozitív és egynél nagyobb egész számmal (ezt megtehetjük), megkapjuk , amelyből és .

Mit ad nekünk a bizonyított tétel Eratoszthenész szitájáról?

Először is, a b prímszám többszörösei összetett számok áthúzását a következővel egyenlő számmal kell kezdeni (ez az egyenlőtlenségből következik). Például a kettő többszöröseinek áthúzását a 4-gyel, a három többszörösét a 9-cel, az ötös többszörösét a 25-tel és így tovább.

Másodszor, a prímszámok táblázatának összeállítása n számig Eratosthenes szitája segítségével akkor tekinthető befejezettnek, ha minden olyan összetett szám, amely prímszámok többszöröse, nem haladja meg a -t. Példánkban n=50 (mivel egy prímszámtáblázatot készítünk 50-ig), és ezért Eratoszthenész szitájának el kell távolítania minden olyan összetett számot, amely többszöröse a 2, 3, 5 és 7 prímszámoknak. nem haladhatja meg az 50 számtani négyzetgyökét. Ez azt jelenti, hogy többé nem kell olyan számokat keresnünk és kihúznunk, amelyek a 11, 13, 17, 19, 23 és így tovább 47-ig többszörösei, mivel ezek már kisebb 2 prímszámok többszöröseiként lesznek áthúzva. , 3, 5 és 7 .

Ez a szám prím vagy összetett?

Egyes feladatokhoz ki kell deríteni, hogy egy adott szám prím-e vagy összetett-e. Általános esetben ez a feladat korántsem egyszerű, különösen olyan számoknál, amelyek írása jelentős számú karakterből áll. A legtöbb esetben valamilyen konkrét megoldást kell keresni. Igyekszünk azonban az egyszerű esetekre irányt adni a gondolatmenetnek.

Természetesen megpróbálkozhatunk oszthatósági tesztekkel annak bizonyítására, hogy egy adott szám összetett. Ha például valamely oszthatósági teszt azt mutatja, hogy egy adott szám osztható egynél nagyobb pozitív egész számmal, akkor az eredeti szám összetett.

Példa.

Bizonyítsuk be, hogy a 898,989,898,989,898,989 összetett szám.

Megoldás.

Ennek a számnak a számjegyeinek összege 9·8+9·9=9·17. Mivel a 9·17-tel egyenlő szám osztható 9-cel, ezért a 9-cel való oszthatóság ismérve alapján az eredeti szám osztható 9-cel is. Ezért összetett.

Ennek a megközelítésnek jelentős hátránya, hogy az oszthatósági kritériumok nem teszik lehetővé egy szám prímságának bizonyítását. Ezért ha egy számot ellenőriz, hogy prím-e vagy összetett-e, másképp kell eljárnia.

A leglogikusabb megközelítés egy adott szám összes lehetséges osztójának kipróbálása. Ha a lehetséges osztók egyike sem igazi osztója egy adott számnak, akkor ez a szám prím lesz, ellenkező esetben összetett lesz. Az előző bekezdésben bizonyított tételekből az következik, hogy adott a szám osztóit kell keresni a -t meg nem haladó prímszámok között. Így egy adott a szám szekvenciálisan osztható prímszámokkal (amelyeket kényelmesen a prímszámtáblázatból vehetünk ki), megpróbálva megtalálni az a szám osztóját. Ha találtunk osztót, akkor az a szám összetett. Ha a -t meg nem haladó prímszámok között nincs osztója az a számnak, akkor az a szám prím.

Példa.

Szám 11 723 egyszerű vagy összetett?

Megoldás.

Nézzük meg, milyen prímszámig lehetnek a 11 723 szám osztói. Ehhez értékeljük.

Ez elég nyilvánvaló , 200 óta 2 = 40 000 és 11 723<40 000 (при необходимости смотрите статью számok összehasonlítása). Így a 11 723 lehetséges prímtényezői kisebbek, mint 200. Ez már nagyban megkönnyíti a dolgunkat. Ha ezt nem tudnánk, akkor nem 200-ig, hanem 11 723-ig kellene végigmenni az összes prímszámon.

Ha szükséges, pontosabban is értékelheti. Mivel 108 2 = 11 664, és 109 2 = 11 881, akkor 108 2<11 723<109 2 , следовательно, . Így a 109-nél kisebb prímszámok bármelyike ​​potenciálisan az adott 11 723 szám prímtényezője.

Most egymás után felosztjuk a 11 723 számot 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 prímszámokra. , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 . Ha a 11 723-as számot elosztjuk valamelyik írott prímszámmal, akkor az összetett lesz. Ha nem osztható egyik felírt prímszámmal sem, akkor az eredeti szám prímszám.

Nem fogjuk leírni ezt az egész monoton és monoton osztódási folyamatot. Mondjuk rögtön, hogy 11.723

• Fordítás

A prímszámok tulajdonságait először az ókori görög matematikusok tanulmányozták. A Pythagoreanus iskola matematikusait (i.e. 500-300) elsősorban a prímszámok misztikus és numerológiai tulajdonságai érdekelték. Ők voltak az elsők, akik ötleteket adtak a tökéletes és barátságos számokról.

Egy tökéletes számnak saját osztóinak összege egyenlő önmagával. Például a 6-os szám megfelelő osztói 1, 2 és 3. 1 + 2 + 3 = 6. A 28 szám osztói: 1, 2, 4, 7 és 14. Ráadásul 1 + 2 + 4 + 7 + 14 = 28.

A számokat barátságosnak nevezzük, ha az egyik szám megfelelő osztóinak összege egyenlő a másikkal, és fordítva - például 220 és 284. Azt mondhatjuk, hogy a tökéletes szám barátságos önmagával.

Euklidész elemeinek idejére, ie 300-ban. A prímszámokkal kapcsolatban több fontos tényt már bebizonyítottak. Az Elemek IX. könyvében Eukleidész bebizonyította, hogy végtelen számú prímszám létezik. Ez egyébként az egyik első példa az ellentmondásos bizonyításra. Bebizonyítja az aritmetika alaptételét is – minden egész szám egyedileg ábrázolható prímszámok szorzataként.

Azt is megmutatta, hogy ha a 2n-1 szám prím, akkor a 2n-1 * (2n-1) szám lesz tökéletes. Egy másik matematikus, Euler 1747-ben be tudta mutatni, hogy minden tökéletes szám felírható ebben a formában. A mai napig nem ismert, hogy léteznek-e páratlan tökéletes számok.

Kr.e. 200. évben. A görög Eratoszthenész kitalált egy algoritmust a prímszámok keresésére, az úgynevezett „Eratoszthenész szitáját”.

És ekkor nagy törés következett be a középkorhoz kötődő prímszámok tanulmányozásának történetében.

A következő felfedezéseket már a 17. század elején tette Fermat matematikus. Bebizonyította Albert Girard sejtését, miszerint bármely 4n+1 alakú prímszám egyértelműen felírható két négyzet összegeként, és megfogalmazta azt a tételt is, hogy bármely szám felírható négy négyzet összegeként.

Új módszert dolgozott ki nagy számok faktorálására, és bemutatta a 2027651281 = 44021 × 46061 számon. Bebizonyította a Fermat-féle kis tételt is: ha p prímszám, akkor bármely a egész számra igaz lesz, hogy a p = modulo p.

Ez az állítás a felét bizonyítja annak, amit "kínai sejtésnek" neveztek, és 2000 éves múltra tekint vissza: egy n egész akkor és csak akkor prím, ha 2 n -2 osztható n-nel. A hipotézis második része hamisnak bizonyult - például a 2341 - 2 osztható 341-gyel, bár a 341-es szám összetett: 341 = 31 × 11.

Fermat kis tétele sok más számelméleti eredmény alapjául szolgált, valamint a számok prímszám-szerűségének vizsgálatára szolgáló módszerek – amelyek közül sokat még ma is használnak.

Fermat sokat levelezett kortársaival, különösen egy Maren Mersenne nevű szerzetessel. Egyik levelében azt feltételezte, hogy a 2 n +1 alakú számok mindig prímek lesznek, ha n kettő hatványa. Ezt n = 1, 2, 4, 8 és 16-ra tesztelte, és biztos volt benne, hogy abban az esetben, ha n nem kettő hatványa, a szám nem feltétlenül prím. Ezeket a számokat Fermat-számoknak nevezik, és csak 100 évvel később Euler kimutatta, hogy a következő szám, a 2 32 + 1 = 4294967297, osztható 641-gyel, ezért nem prímszám.

A 2 n - 1 alakú számok is kutatás tárgyát képezték, hiszen könnyen kimutatható, hogy ha n összetett, akkor maga a szám is összetett. Ezeket a számokat Mersenne-számoknak nevezik, mert alaposan tanulmányozta őket.

De nem minden 2 n - 1 alakú szám, ahol n prím, prím. Például 2 11 - 1 = 2047 = 23 * 89. Ezt először 1536-ban fedezték fel.

Sok éven át az ilyen számok biztosították a matematikusok számára a legnagyobb ismert prímszámokat. Azt, hogy az M 19-et Cataldi bizonyította 1588-ban, és 200 évig ez volt a legnagyobb ismert prímszám, amíg Euler be nem bizonyította, hogy az M 31 is prímszám. Ez a rekord még száz évig kitartott, majd Lucas megmutatta, hogy az M 127 prím (és ez már 39 számjegyből áll), majd ezután a számítógépek megjelenésével folytatódott a kutatás.

1952-ben bebizonyosodott az M 521, M 607, M 1279, M 2203 és M 2281 számok elsődlegessége.

2005-ig 42 Mersenne-prímszámot találtak. Közülük a legnagyobb, az M 25964951, 7816230 számjegyből áll.

Euler munkája óriási hatással volt a számelméletre, beleértve a prímszámokat is. Kiterjesztette Fermat kis tételét és bevezette a φ-függvényt. Faktorizálta az 5. Fermat-számot 2 32 +1, talált 60 pár baráti számot, és megfogalmazta (de nem tudta bizonyítani) a másodfokú reciprocitás törvényét.

Ő volt az első, aki bevezette a matematikai elemzés módszereit és kidolgozta az analitikus számelméletet. Bebizonyította, hogy nemcsak a ∑ (1/n) harmonikus sorozat, hanem a forma sorozata is

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

A prímszámok reciprokainak összegével kapott eredmény is divergál. A harmonikus sorozat n tagjának összege megközelítőleg log(n)-ként nő, a második sorozat pedig lassabban tér el log[ log(n) ]-ként. Ez azt jelenti, hogy például az összes eddig talált prímszám reciprokának összege csak 4-et ad, bár a sorozat továbbra is eltér.

Első pillantásra úgy tűnik, hogy a prímszámok egészen véletlenszerűen oszlanak el az egész számok között. Például a 100 szám között közvetlenül az 10000000 előtt 9 prím van, a közvetlenül ez utáni 100 számban pedig csak 2. De nagy szegmenseken a prímszámok meglehetősen egyenletesen oszlanak el. Legendre és Gauss terjesztésük kérdéseivel foglalkozott. Gauss egyszer azt mondta egy barátjának, hogy minden szabad 15 percben mindig megszámolja a következő 1000 szám prímszámait. Élete végére minden prímszámot megszámolt 3 millióig. Legendre és Gauss egyformán kiszámította, hogy nagy n esetén a prímsűrűség 1/log(n). Legendre megbecsülte a prímszámok számát az 1 és n közötti tartományban as

π(n) = n/(log(n) - 1,08366)

Gauss pedig olyan, mint egy logaritmikus integrál

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

2-től n-ig terjedő integrációs intervallummal.

Az 1/log(n) prímsűrűségre vonatkozó állítást Prímeloszlási tételként ismerjük. A 19. század során ezt próbálták bizonyítani, és Csebisev és Riemann előrehaladást értek el. Összekötötték a Riemann-hipotézissel, amely a Riemann-zéta-függvény nulláinak eloszlásáról szóló máig bizonyítatlan hipotézis. A prímszámok sűrűségét Hadamard és Vallée-Poussin egyszerre bizonyította 1896-ban.

A prímszámelméletben még mindig sok megválaszolatlan kérdés van, amelyek közül néhány több száz éves:

• Az ikerprím hipotézis végtelen számú prímszámpárról szól, amelyek 2-vel különböznek egymástól
• Goldbach-sejtés: bármely 4-gyel kezdődő páros szám ábrázolható két prímszám összegeként
• Van-e végtelen számú n 2 + 1 alakú prímszám?
• Mindig találhatunk prímszámot n 2 és (n + 1) 2 között? (azt, hogy n és 2n között mindig van prímszám, Csebisev bizonyította)
• A Fermat-prímek száma végtelen? Vannak Fermat prímszámok 4 után?
• létezik-e egy adott hosszúságú egymást követő prímszámok számtani sorozata? például a 4-es hosszhoz: 251, 257, 263, 269. A maximális talált hossz 26.
• Van-e végtelen számú három egymást követő prímszámból álló halmaz egy aritmetikai sorozatban?
• n 2 - n + 41 prímszám, ha 0 ≤ n ≤ 40. Van végtelen sok ilyen prímszám? Ugyanez a kérdés az n 2 - 79 n + 1601 képletre. Ezek a számok prímszámok 0 ≤ n ≤ 79 esetén.
• Van végtelen számú n# + 1 alakú prímszám? (n# az összes n-nél kisebb prímszám szorzatának eredménye)
• Van végtelen számú n# -1 alakú prímszám?
• Van végtelen számú n alakú prímszám? + 1?
• Van végtelen számú n alakú prímszám? - 1?
• ha p prím, akkor 2 p -1 mindig nem tartalmaz prímnégyzeteket a tényezői között?
• a Fibonacci sorozat végtelen számú prímszámot tartalmaz?

A legnagyobb ikerprímszámok 2003663613 × 2 195000 ± 1. 58711 számjegyből állnak, és 2007-ben fedezték fel.

A legnagyobb (n! ± 1 típusú) faktoriális prímszám 147855! - 1. 142891 számjegyből áll, és 2002-ben találták.

A legnagyobb elsődleges prímszám (n# ± 1 alakú szám) 1098133# + 1.

A cikk a prímszámok és az összetett számok fogalmát tárgyalja. Az ilyen számok definícióit példákkal adjuk meg. Bizonyítjuk, hogy a prímszámok száma korlátlan, és Eratoszthenész módszerével rögzítjük a prímszámok táblázatában. Bizonyítékot kell adni annak meghatározására, hogy egy szám prímszámú vagy összetett.

Yandex.RTB R-A-339285-1

Prím- és összetett számok – meghatározások és példák

A prímszámokat és az összetett számokat pozitív egész számok közé soroljuk. Egynél nagyobbnak kell lenniük. Az osztókat egyszerű és összetett osztályokra is osztják. Az összetett számok fogalmának megértéséhez először tanulmányoznia kell az osztók és a többszörösek fogalmát.

1. definíció

A prímszámok olyan egész számok, amelyek nagyobbak egynél, és két pozitív osztójuk van, azaz önmagukkal és 1-gyel.

2. definíció

Az összetett számok olyan egész számok, amelyek nagyobbak egynél, és legalább három pozitív osztójuk van.

Az egyes nem prímszám és nem is összetett szám. Csak egy pozitív osztója van, ezért különbözik az összes többi pozitív számtól. Minden pozitív egész számot természetes számnak nevezünk, vagyis a számlálás során használjuk.

3. definíció

prímszámok természetes számok, amelyeknek csak két pozitív osztójuk van.

4. definíció

Összetett szám egy természetes szám, amelynek kettőnél több pozitív osztója van.

Minden 1-nél nagyobb szám prím vagy összetett. Az oszthatóságból azt kapjuk, hogy 1 és az a szám mindig osztója lesz bármely a számnak, azaz osztható lesz önmagával és 1-gyel. Adjuk meg az egész számok definícióját.

5. definíció

Azokat a természetes számokat, amelyek nem prímszámok, összetett számoknak nevezzük.

Prímszámok: 2, 3, 11, 17, 131, 523. Csak önmagukkal és 1-gyel oszthatók. Összetett számok: 6, 63, 121, 6697. Vagyis a 6-os szám 2-re és 3-ra, a 63 pedig 1-re, 3-ra, 7-re, 9-re, 21-re, 63-ra, a 121-re bontható 11-re, 11-re, vagyis osztói 1, 11, 121 lesznek. A 6697-es szám 37-re és 181-re bomlik. Vegye figyelembe, hogy a prímszámok és a másodprímszámok fogalma különböző fogalmak.

A prímszámok használatának megkönnyítése érdekében egy táblázatot kell használnia:

Az összes létező természetes szám táblázata irreális, mivel végtelen sok van belőlük. Amikor a számok elérik az 10000-et vagy a 1000000000-et, érdemes megfontolni az Eratosthenes szita használatát.

Tekintsük az utolsó állítást magyarázó tételt.

1. tétel

Egynél nagyobb természetes szám 1-től eltérő legkisebb pozitív osztója prímszám.

Bizonyíték 1

Tegyük fel, hogy a természetes szám, amely nagyobb 1-nél, b pedig a legkisebb nem egy osztója. Az ellentmondás módszerével be kell bizonyítani, hogy b prímszám.

Tegyük fel, hogy b egy összetett szám. Innen azt kapjuk, hogy van b-nek egy osztója, amely különbözik 1-től és b-től. Az ilyen osztó jelölése b 1. Szükséges az 1. feltétel< b 1 < b elkészült.

A feltételből jól látható, hogy a osztva b-vel, b osztva b 1-gyel, ami azt jelenti, hogy az oszthatóság fogalma a következőképpen fejeződik ki: a = b qés b = b 1 · q 1 , ahol a = b 1 · (q 1 · q) , ahol q és q 1 egész számok. Az egész számok szorzásának szabálya szerint az egész számok szorzata egy a = b 1 · (q 1 · q) alakú egyenlőséggel rendelkező egész szám. Látható, hogy b 1 az a szám osztója. Egyenlőtlenség 1< b 1 < b Nem megfelel, mert azt találjuk, hogy b a legkisebb pozitív és nem 1 osztója.

2. tétel

Végtelen számú prímszám létezik.

Bizonyíték 2

Feltehetően veszünk egy véges számú n természetes számot, és jelöljük őket p 1, p 2, …, p n. Tekintsük a jelzettektől eltérő prímszám megtalálásának lehetőségét.

Vegyük figyelembe a p számot, amely egyenlő p 1, p 2, ..., p n + 1-gyel. Nem egyenlő a p 1, p 2, ..., p n alakú prímszámoknak megfelelő számok mindegyikével. A p szám prím. Ekkor a tételt bizonyítottnak tekintjük. Ha összetett, akkor fel kell venni a p n + 1 jelölést és mutassuk meg, hogy az osztó nem esik egybe a p 1, p 2, ..., p n egyikével sem.

Ha ez nem így lenne, akkor a p 1, p 2, ..., p n szorzat oszthatósági tulajdonsága alapján , azt találjuk, hogy osztható lenne pn + 1-gyel. Vegye figyelembe, hogy a p n + 1 kifejezés a p szám elosztása p 1, p 2, ..., p n + 1 összeggel egyenlő. Azt kapjuk, hogy a p n + 1 kifejezés Ennek az összegnek a második tagját, amely 1, el kell osztani, de ez lehetetlen.

Látható, hogy a megadott számú prímszámok között tetszőleges prímszám megtalálható. Ebből következik, hogy végtelen sok prímszám van.

Mivel sok prímszám van, a táblázatok a 100, 1000, 10000 stb. számokra korlátozódnak.

A prímszámok táblázatának összeállításakor figyelembe kell venni, hogy egy ilyen feladat a számok szekvenciális ellenőrzését igényli, 2-től 100-ig. Ha nincs osztó, akkor bekerül a táblázatba, ha összetett, akkor nem kerül be a táblázatba.

Nézzük meg lépésről lépésre.

Ha a 2-es számmal kezded, akkor csak 2 osztója van: 2 és 1, ami azt jelenti, hogy beírható a táblázatba. Ugyanez a 3-as számmal. A 4-es szám összetett, 2-re és 2-re kell bontani. Az 5-ös szám prímszám, ami azt jelenti, hogy rögzíthető a táblázatban. Tedd ezt a 100-as számig.

Ez a módszer kényelmetlen és időigényes. Lehetőség van asztal létrehozására, de sok időt kell töltenie. Szükséges az oszthatósági kritériumok alkalmazása, ami felgyorsítja az osztók megtalálásának folyamatát.

Az Eratosthenes szitáját használó módszert tartják a legkényelmesebbnek. Nézzük az alábbi példatáblázatokat. Először a 2, 3, 4, ..., 50 számokat írjuk le.

Most át kell húznia az összes olyan számot, amely 2 többszöröse. Végezzen szekvenciális áthúzásokat. Ilyen táblázatot kapunk:

Továbblépünk az 5 többszörösei számok áthúzására. Kapunk:

Húzd át azokat a számokat, amelyek 7, 11 többszörösei. Végül úgy néz ki az asztal

Térjünk át a tétel megfogalmazására.

3. tétel

Az a bázisszám legkisebb pozitív és nem 1 osztója nem haladja meg az a-t, ahol a az adott szám számtani gyöke.

Bizonyíték 3

Egy a összetett szám legkisebb osztóját kell b-vel jelölni. Van egy q egész szám, ahol a = b · q, és azt kapjuk, hogy b ≤ q. A formai egyenlőtlenségek elfogadhatatlanok b > q, mert a feltétel sérül. A b ≤ q egyenlőtlenség mindkét oldalát meg kell szorozni bármely b pozitív számmal, amely nem egyenlő 1-gyel. Azt kapjuk, hogy b · b ≤ b · q, ahol b 2 ≤ a és b ≤ a.

A bizonyított tételből világos, hogy a számok áthúzása a táblázatban ahhoz a tényhez vezet, hogy olyan számmal kell kezdeni, amely egyenlő b 2 -vel, és kielégíti a b 2 ≤ a egyenlőtlenséget. Vagyis ha kihúzod azokat a számokat, amelyek 2 többszörösei, akkor a folyamat 4-gyel kezdődik, a 3 többszörösei pedig 9-cel, és így tovább 100-ig.

Egy ilyen táblázat összeállítása Eratoszthenész tételével azt sugallja, hogy ha minden összetett számot áthúzunk, olyan prímszámok maradnak, amelyek nem haladják meg az n-t. Abban a példában, ahol n = 50, akkor n = 50. Innen azt kapjuk, hogy Eratoszthenész szitája kiszűr minden olyan összetett számot, amelynek értéke nem nagyobb, mint az 50-es gyök értéke. A számok keresése áthúzással történik.

A megoldás előtt ki kell deríteni, hogy a szám prím vagy összetett. Gyakran használják az oszthatósági kritériumokat. Nézzük meg ezt az alábbi példában.

1. példa

Bizonyítsuk be, hogy a 898989898989898989 szám összetett.

Megoldás

Egy adott szám számjegyeinek összege 9 8 + 9 9 = 9 17. Ez azt jelenti, hogy a 9 · 17 szám osztható 9-cel, az oszthatósági teszt alapján 9-cel. Ebből következik, hogy összetett.

Az ilyen jelek nem képesek bizonyítani egy szám elsődlegességét. Ha ellenőrzésre van szükség, más lépéseket kell tenni. A legmegfelelőbb módszer a számok felsorolása. A folyamat során prím- és összetett számok találhatók. Vagyis a számok nem haladhatják meg az értéket. Ez azt jelenti, hogy az a számot prímtényezőkbe kell beszámítani. ha ez teljesül, akkor az a szám prímnek tekinthető.

2. példa

Határozzuk meg az 11723 összetett vagy prímszámot!

Megoldás

Most meg kell találnia az 11723 szám összes osztóját. Értékelni kell a 11723-at.

Innen látjuk, hogy 11723< 200 , то 200 2 = 40 000 és 11 723< 40 000 . Получаем, что делители для 11 723 меньше числа 200 .

Az 11723 szám pontosabb becsléséhez fel kell írni a 108 2 = 11 664 kifejezést, és 109 2 = 11 881 , Azt 108 2 < 11 723 < 109 2 . Ebből következik, hogy 11723< 109 . Видно, что любое число, которое меньше 109 считается делителем для заданного числа.

Bővítéskor azt tapasztaljuk, hogy 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, A 83 , 89 , 97 , 101 , 103 , 107 mind prímszámok. Ez az egész folyamat egy oszloppal való osztásként ábrázolható. Vagyis osszuk el az 11723-at 19-cel. A 19-es szám az egyik tényezője, hiszen maradék nélkül kapunk osztást. Az osztást ábrázoljuk oszlopként:

Ebből következik, hogy az 11723 összetett szám, mert önmagán és 1-en kívül még 19 osztója van.

Válasz: Az 11723 egy összetett szám.

Ha hibát észlel a szövegben, jelölje ki, és nyomja meg a Ctrl+Enter billentyűkombinációt

A számok különbözőek: természetes, racionális, racionális, egész és tört, pozitív és negatív, összetett és prím, páratlan és páros, valós stb. Ebből a cikkből megtudhatja, mik a prímszámok.

Milyen számokat neveznek angolul „egyszerűnek”?

Nagyon gyakran az iskolások első pillantásra nem tudják, hogyan válaszoljanak a matematika egyik legegyszerűbb kérdésére, hogy mi a prímszám. Gyakran összekeverik a prímszámokat a természetes számokkal (vagyis azokkal a számokkal, amelyeket az emberek az objektumok számlálásakor használnak, míg egyes forrásokban nullával, másokban eggyel kezdődnek). De ez két teljesen különböző fogalom. A prímszámok természetes számok, vagyis olyan egészek és pozitív számok, amelyek nagyobbak egynél, és csak 2 természetes osztójuk van. Sőt, ezen osztók egyike az adott szám, a második pedig egy. Például a három prímszám, mert nem osztható maradék nélkül más számmal, mint önmagával és eggyel.

Összetett számok

A prímszámok ellentéte az összetett számok. Természetesek is, szintén nagyobbak egynél, de nem kettő, hanem nagyobb számú osztójuk van. Így például a 4, 6, 8, 9 stb. számok természetesek, összetettek, de nem prímszámok. Mint látható, ezek többnyire páros számok, de nem mind. De a „kettő” egy páros szám és az „első szám” a prímszámok sorozatában.

Utóbbi

Egy prímszám-sorozat megalkotásához minden természetes szám közül kell választani, figyelembe véve azok meghatározását, vagyis ellentmondásosan kell cselekedni. Minden pozitív természetes számot meg kell vizsgálni, hogy lássuk, van-e kettőnél több osztója. Próbáljunk meg felépíteni egy sorozatot (sorozatot), amely prímszámokból áll. A lista kettővel kezdődik, majd hárommal kezdődik, mivel csak önmagával és eggyel osztható. Tekintsük a négyes számot. Van-e más osztója a négyen és egyen kívül? Igen, ez a szám 2. Tehát a négy nem prímszám. Az öt is prím (nem osztható más számmal, kivéve 1-et és 5-öt), de a hat osztható. És általában, ha követi az összes páros számot, észre fogja venni, hogy a „kettő” kivételével egyik sem prímszám. Ebből arra következtetünk, hogy a páros számok kettő kivételével nem prímszámok. Egy másik felfedezés: minden hárommal osztható szám, magát a hármat kivéve, akár páros, akár páratlan, szintén nem prímszám (6, 9, 12, 15, 18, 21, 24, 27 stb.). Ugyanez vonatkozik az öttel és héttel osztható számokra is. Az ő sokaságuk sem egyszerű. Foglaljuk össze. Tehát az egyszerű egyjegyű számok minden páratlan számot tartalmaznak, kivéve egyet és kilencet, és még a „kettő” is páros szám. Maguk a tízesek (10, 20,... 40 stb.) nem egyszerűek. Kétjegyű, háromjegyű stb. prímszámok a fenti elvek alapján határozhatók meg: ha önmagukon és egyen kívül nincs más osztójuk.

Elméletek a prímszámok tulajdonságairól

Van egy tudomány, amely az egész számok tulajdonságait vizsgálja, beleértve a prímszámokat is. Ez a matematikának a magasabbnak nevezett ága. Az egész számok tulajdonságain kívül algebrai és transzcendentális számokkal, valamint ezek számtani vonatkozású különböző eredetű függvényeivel is foglalkozik. Ezekben a vizsgálatokban az elemi és algebrai módszerek mellett analitikus és geometriai módszereket is alkalmaznak. Konkrétan a „Számelmélet” a prímszámok tanulmányozásával foglalkozik.

A prímszámok a természetes számok „építőkövei”.

Az aritmetikában van egy alaptételnek nevezett tétel. Eszerint egy kivételével bármely természetes szám ábrázolható szorzatként, amelynek tényezői prímszámok, a tényezők sorrendje pedig egyedi, ami azt jelenti, hogy az ábrázolás módja egyedi. Ezt nevezik természetes szám prímtényezőkké alakításának. Ennek a folyamatnak van egy másik neve is - a számok faktorizálása. Ez alapján a prímszámokat nevezhetjük „építőanyagnak”, természetes számok megalkotására szolgáló „tömböknek”.

Prímszámok keresése. Egyszerűségi tesztek

Sok különböző időkből származó tudós próbált néhány elvet (rendszert) találni a prímszámok listájának megtalálásához. A tudomány ismeri az Atkin-szitának, a Sundartham-szitának és az Eratosthenes-szitának nevezett rendszereket. Ezek azonban nem adnak szignifikáns eredményt, és egy egyszerű tesztet használnak a prímszámok megtalálásához. A matematikusok algoritmusokat is készítettek. Ezeket általában primalitásteszteknek nevezik. Például van egy Rabin és Miller által kifejlesztett teszt. A kriptográfusok használják. Van még a Kayal-Agrawal-Sasquena teszt is. A kellő pontosság ellenére azonban nagyon nehéz kiszámítani, ami csökkenti a gyakorlati jelentőségét.

Van-e határa a prímszámok halmazának?

Az ókori görög tudós, Eukleidész „Elemek” című könyvében azt írta, hogy a prímszámok halmaza a végtelen. Ezt mondta: „Képzeljük el egy pillanatra, hogy a prímszámoknak van határa. Ezután szorozzuk meg őket egymással, és adjunk hozzá egyet a termékhez. Az ilyen egyszerű műveletek eredményeként kapott szám nem osztható a prímszámok egyik sorozatával sem, mert a maradék mindig egy lesz. Ez azt jelenti, hogy van még olyan szám, amely még nem szerepel a prímszámok listáján. Ezért a feltevésünk nem igaz, és ennek a halmaznak nem lehet határa. Euklidész bizonyítása mellett létezik egy modernebb képlet is, amelyet Leonhard Euler 18. századi svájci matematikus adott. Eszerint az első n szám összegének reciprok összege korlátlanul növekszik az n szám növekedésével. És itt van a prímszámok eloszlására vonatkozó tétel képlete: (n) n/ln (n)-nel nő.

Mi a legnagyobb prímszám?

Ugyanaz a Leonard Euler tudta megtalálni ideje legnagyobb prímszámát. Ez 2 31 - 1 = 2147483647. 2013-ra azonban a prímszámok listájának egy másik legpontosabb legnagyobbját számították ki - 2 57885161 - 1. Ezt Mersenne-számnak hívják. Körülbelül 17 millió tizedesjegyet tartalmaz. Amint látja, egy tizennyolcadik századi tudós által talált szám ennek többszöröse. Így is volt, mert ezt a számítást Euler manuálisan végezte el, míg kortársunkat valószínűleg számítógép segítette. Sőt, ezt a számot az egyik amerikai kar matematikai karán szerezték meg. Az erről a tudósról elnevezett számok átmennek a Luc-Lemaire primalitási teszten. A tudomány azonban nem akar itt megállni. Az Electronic Frontier Foundation, amelyet 1990-ben alapítottak az Amerikai Egyesült Államokban (EFF), pénzjutalmat ajánlott fel nagy prímszámok megtalálásáért. És ha 2013-ig azoknak a tudósoknak ítélték oda a díjat, akik 1 és 10 millió tizedes szám közül megtalálták őket, mára ez a szám 100 millióról 1 milliárdra nőtt. A nyeremények 150 és 250 ezer amerikai dollár között mozognak.

Speciális prímszámok nevei

Azokat a számokat, amelyeket bizonyos tudósok által létrehozott algoritmusoknak köszönhetően találtak meg, és átmentek az egyszerűségi teszten, speciálisnak nevezik. Itt van néhány közülük:

1. Merssen.

4. Cullen.

6. Mills et al.

A fenti tudósokról elnevezett számok egyszerűségét a következő tesztekkel állapítjuk meg:

1. Luc-Lemaire.

2. Pepina.

3. Rizel.

4. Billhart - Lemaire - Selfridge és mások.

A modern tudomány nem áll meg itt, és valószínűleg a közeljövőben a világ megtudja azoknak a nevét, akik a legnagyobb prímszám megtalálásával vehették át a 250 000 dolláros díjat.