Hány prímszám van?
2014/07/18 08:00
7595 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.

Számolni már a gyerekek is tudnak. Egy után jön a kettő, majd a három, és minden soron következő szám eggyel nagyobb, mint az őt megelőző. A számokat azonos módon képezzük, az eredményül kapott értékek mégis különböző tulajdonságokkal bírnak.

Egyik szám sem ugyanolyan, mint a másik. Nézzünk egy példát. Van olyan szám, amely felbontható kisebb számok (tényezők) szorzatára. Pl. 12=2*2*3=2*6=3*4. Más számokkal ezt nem tudjuk megtenni, ilyen pl. a 7, amely csak a következő formában állítható elő: 7=1*7, vagyis csak az 1 és önmaga szorzataként. Az ilyen számokat prímszámoknak nevezzük. Szokás a prímszámokat törzsszámoknak vagy röviden prímeknek nevezni.

Azokat a számokat, amelyek felbonthatóak kisebb tényezők szorzatára, összetett számoknak nevezzük. Minden összetett szám felépíthető csak prímszámokból, lásd:

12=2*2*3, vagy 45=3*3*5.

Az 1-et mint tényezőt ilyenkor nem írjuk le. A prímszámokat tekinthetjük az összetett számok Lego kockáinak. A legkisebb prímszám - és így a legkisebb „Lego kocka” - a 2, amely az egyetlen páros prím.

Hány prímszám létezik?

A következő táblázatban láthatjuk a prímszámok számát:

100 alatt1 000 alatt10 000 alatt100 000 000 alatt
2426812295 761 455

Ha a prímszámokból táblázatot készítünk, akkor ennek segítségével össze is tudjuk számolni őket. A módszer elnevezése az Eratoszthenészi-szita. Ezt az algoritmust szemlélteti a következő ábra:

shutterstock_136384187

A számok listájából kihúzzuk a 2 többszöröseit, azaz minden páros számot. A 2-t azonban meghagyjuk! Ezután a 3, 5, 7 stb. többszöröseit húzzuk ki, és az eljárás így folytatható.

Ha a szitálást befejeztünk, akkor mindig az első megmaradt jobboldali szomszéd többszöröseit húzzuk ki, például, ha 5-tel szitáltunk, akkor a 7-tel kezdünk, majd a 11-gyel és a 13-mal folytatjuk stb.

A szita tehát minden lépés után előállítja a következő prímszámot, és így az eljárás végére a szitában a prímszámok sorozata marad. Könnyű dolog a szitázás, de meddig csináljuk? Ezzel az eljárással nem tudjuk meg, hogy vajon véges sok vagy végtelen sok prímszám van-e?

Végtelen sok prímszám létezik!

Az állítás nagyon merész, hiszen nem ismerjük az összes prímszámot, mégis azt állítjuk, hogy végtelen sok van belőlük. Hogyan lehet ilyen állítást tenni, ha megszámolni csak véges sokat tudunk?

Több mint 2000 évvel ezelőtt a szintén görög Eukleidész egy nagyon frappáns és szellemes bizonyítást adott, amelyet megértve megtapasztalható a matematikai bizonyítások szépsége és ereje!

Nézzünk egy egyszerű tényt először. A 45=3*3*5, a tényezők közül minden prímszámmal osztható. Ha hozzáadunk 1-et, akkor a kapott szám már nem osztható a prímtényezőkkel.

No, lássuk a bizonyítást!

Azt fogjuk belátni, hogy minden p prímszám esetén létezik olyan p’ prím, amelyik nagyobb nála.

Lássuk az eredeti bizonyítást az Elemek című műből: "Prímszámból prímszámok bármely sokaságánál több van. Legyenek az adott prímszámok a, b és c. Azt állítom, hogy több prímszám van, mint a, b és c. Vegyük ugyanis a, b és c legkisebb közös többszörösét, legyen ez DE, és adjuk hozzá DE-hez a DF egységet. Ekkor EF vagy prím, vagy nem. Legyen először prím. Találtunk tehát az a, b és c számoknál több prímet, a-t, b-t, c-t és EF-t. Ne legyen most EF prím. Ekkor osztja valamelyik prímszám. Osztja a g prím. Azt állítom, hogy g az a, b és c egyikével sem azonos. Tegyük föl ugyanis, hogy az a, b és c osztják DE-t, tehát g is osztja DE-t. Viszont EF-t is osztja, tehát a maradék DF egységet is osztja g, noha szám, ami ellentmondás. A g tehát nem azonos az a, b, c számok egyikével sem. S feltétel szerint prím, tehát találtunk az adott a, b, c prímeknél több prímet, a-t, b-t, c-t, g-t. Éppen ezt kellett megmutatni."

Napjainkban az iskolai tankönyvekben szereplő bizonyítás:

Tétel: Végtelen sok prímszám van.

Bizonyítás: Tételezzük fel a fenti állítás ellentétét, azaz a prímszámok száma véges. Legyenek ezek a számok: p1, p2, p3, …pn!

Képezzük a következő számot: Z= p1* p2* p3* …*pn+1

Az így kapott Z számnak nem osztója a felsorolt prímek egyike sem. Ebből az következik, hogy vagy Z prím, vagy van egy olyan prím osztója, amely nem szerepelt a fentiek között. Mivel mindkét eset egy új prímszámot eredményezett, így nem lehet igaz az első állítás, hogy véges sok prímszám létezik. Ha pedig ez nem igaz, akkor végtelen sok prímszám van!

Az ilyen bizonyítási eljárást indirekt bizonyításnak nevezik!

A ma ismert legnagyobb prímszám (2014 január): 2 57885161 – 1. Ez a szám több mint 17 millió számjegyből áll!

További érdekes oldalak:

Zsigó Zsolt cikke

Csoportot ajánlunk

Kapcsolódó oldalak

Scientix A természettudományos oktatás közössége
All you need is code Minden a kódolás tanulásáról
A National Geographic A National Geographic honlapja.
Interpress Magazin Az IPM honlapja archívummal
Világtudomány.hu A magyar és nemzetközi tudományos élet hírei
Űr világ Asztronautikai hírportál