Fogalma
A természetes számokat a pozitív osztóik száma szerint csoportosíthatjuk. De pontosan hogyan? A prímszámok kívül három másik csoport létezik:
- A 0-nak az összes természetes szám osztója, így végtelen sok pozitív osztója van.
- Az 1-nek egy pozitív osztója van, és ez önmaga, az 1.
- Az olyan pozitív egész számokat, melyeknek kettőnél több osztója van, összetett számoknak nevezzük.
A megmaradó számok a prímszámok. Az olyan pozitív egész számokat, melyeknek pontosan két pozitív osztója van, prímeknek nevezzük. Ez a két osztó 1 és önmaga. A prímszámok mindig egész számok. Az 1 nem prímszám.
Mi az az Erasztothenészi szita?
Létezik egy neves módszer, mellyel könnyedén meghatározhatjuk a prímszámokat N-ig. A módszer bemutatásához 25-ig fogjuk meghatározni a prímszámokat.
1, Vegyünk fel egy NxN-es négyzetrácsot, melybe írjuk ki 1 a számokat.
2, Vegyük a kettőt először. A kettő összes többszörösét húzzuk ki a rácsban. Ezek a számok nem lehetnek prímek, hiszen oszthatók kettővel.
3, Vegyük a hármat. Húzzuk ki a három összes többszörösét a rácsban. Ezek a számok nem lehetnek prímek, hiszen oszthatók hárommal.
4, Vegyük mindig a legkisebb nem kihúzott számot, amit eddig nem vettünk. Húzzuk ki ennek többszöröseit.
5, Az algoritmust akkor állítsuk meg, amikor az éppen vizsgált n szám négyzete már nagyobb mint N.
Így egy N=5-re az alábbi ábrát kapjuk majd – a megmaradt számok a prímek.
A prímszám táblázat 100-ig
Összesen 26 prímszám van az első 100 pozitív egész számban. Szemléljük az alábbi prímszám táblázatot. A prímek 1-től 100-ig: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97.
Hogyan igazolható, hogy végtelen sok prímszám létezik?
Tételezzük fel, hogy a prímek száma véges. Vegyük az összes prímet, jelöljük ezeket rendre
Jelöljük K-val ezen számok szorzatát, és ehhez adjunk hozzá egyet! Ekkor az alábbi egyenlőséghez jutunk:
Ez a K szám nem osztható a létező prímek egyikével sem, holott K nyilvánvalóan nagyobb mint bármelyik eddig feltételezett prímszám. Ellentmondásba ütköztünk, a kezdeti feltevésünk hamis volt.
Mik azok az ikerprímek és létezik-e végtelen számú ikerprím?
Az ikerprímek olyan prímszám párok, melyeknek a különbsége kettő. Például a {3, 5}, {5, 7}, {11, 13}, {17, 19}, {29, 31} számpárok ikerprímek.
Annál is érdekesebb témakör, hiszen a mai matematikában máig megoldatlan kérdés, hogy vajon létezik-e végtelen számú ikerprím.
Létezik-e olyan képlet a matematikában, ami mindig prímszámot ad vissza?
Ez szintén megoldatlan probléma a matematikában mind a mai napig. A matematikusok úgy vélik, hogy jó eséllyel nem létezik ilyen képlet.
Mire használják ezeket a számokat az informatikusok?
A prímszámok – sok diák számára, és nem is véletlenül – egy olyan iskolai fogalomnak tűnnek, melynek nincs semmilyen gyakorlati haszna. Több olyan állítást és sejtést is megfogalmaztunk, aminek úgy tűnik, hogy nincs semmilyen gyakorlati haszna.
Mindennek ellenére a prímszámoknak van egy nagyon gyakorlatias és fontos alkalmazása a mindennapjainkban. Ez pedig a titkosítás. Ennek az az oka, hogy a nagy összetett számok faktorizációja nehezen megoldható, és nagyon számításigényes. Ha összeszorzunk két hatalmas prímszámot, akkor egy olyan összetett számhoz jutunk, melynek csak két prímosztója van. Ezeket pedig nagyon nehéz megtalálni.
Gyakorló feladatok
Íme, lássunk néhány gyakorló feladatot, olyanokat, melyek könnyedén előjöhetnek egy témazáró dolgozaton, vagy pedig egy érettségi vizsgán.
I. feladat
Adjuk meg az első 10 prímszám összegét!
Megoldás.
A megoldáshoz természetesen meg kell határoznunk az első 10 prímszámot. Erre használhatjuk akár az Erasztothenészi szitát is. Az első 10 prímszám: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29
Ezeknek az összege: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 = 129
II. feladat
Az első 15 prímszám összege és szorzata páros, vagy páratlan szám?
Megoldás.
Természetesen úgy is nekiállhatunk a feladat megoldásának, hogy összeadjuk a prímszámokat egyesével, illetve összeszorozzuk. Ez azonban időigényes feladat. Helyette próbáljuk meg a számok paritását vizsgálni.
Mivel a 2 prímszám, ezért a szorzat tartalmaz páros számot, így az első 15 prímszám szorzata is páros szám.
Az első 15 prímszám egy páros számból, és 14 páratlan számból áll. A 14 páratlan szám összege mindig páros lesz, amihez kettőt kell adnunk, így az első 15 prímszám összege is páros.
III. feladat
Három prímszám szorzata 3970. Melyek ezek a számok?
Megoldás.
Mivel a szorzatuk páros, így van olyan tényezője a szorzatnak, ami kettővel osztható. Mivel az összes prímszám közül az egyetlen a kettő maga, ami osztható kettővel, ezért az egyik szám a kettő. Ha jobban megfigyeljük, akkor látható, hogy a szorzat öttel is osztható. Tehát, az egyik prímszám öttel osztható, és az egyetlen prím, amire ez igaz, az öt. Így a három szám a következő lesz:
- 2
- 5
- 397