Prímszámok: definíció, példák, tulajdonságok és híres sejtések
A prímszám olyan természetes szám, amelynek pontosan két pozitív osztója van: 1 és önmaga. Másképp fogalmazva: a prímszám nagyobb, mint 1, és nem írható fel két kisebb természetes szám szorzataként (kivéve az 1·önmaga esetet). Az 1 nem prímszám, mert csak egy pozitív osztója van, az 2 pedig az egyetlen páros prímszám. Példák: 2, 3, 5, 7, 11, 13, stb. Nincs legnagyobb prímszám — végtelen sok prímszám létezik.
Alapvető tulajdonságok
- Oszthatóság: ha egy számnak van 1-nél és önmagánál kisebb pozitív osztója, akkor összetett; különben prímszám.
- Összetett számok felbontása: minden 1-nél nagyobb egész szám egyértelmű módon írható fel prímszámok szorzataként (a prímtényezős felbontás egyértelműsége, kivéve a sorrendet). Ezt a tételt a számelmélet egyik alaptételeként ismerjük.
- Páros és páratlan: 2 az egyetlen páros prímszám; minden más prímszám páratlan.
- Relatív prímek: két szám akkor és csak akkor relatív prím, ha közös pozitív osztójuk 1.
Példák és egyszerű vizsgálatok
- Gyors ellenőrzés kis számokra: próbáljuk meg osztani a vizsgált számot minden 2-től kezdődő prímszámmal legfeljebb a szám négyzetgyökéig. Ha egyik sem osztja, a szám prímszám.
- Sieve (szita): a Szitáron alapuló módszerek (például Eratoszthenész szitája) hatékonyan felsorolják a prímszámokat egy adott határig.
A prímszámok végtelensége
Az egyik klasszikus bizonyítás (Eukleidész) szerint feltételezzük, hogy véges sok prímszám van, megszorozzuk őket és hozzáadunk 1-et; az így kapott számnak nem lehet osztója az eredeti prímszámok között, tehát vagy új prímszám, vagy olyan összetett szám, amelynek prímtényezői nem lehetnek az eredeti halmazból — ellentmondás. Következésképp végtelen sok prímszám létezik.
Eloszlásuk és a prímszámtétel
A prímszámok eloszlása a természetes számokon belül kaotikusnak tűnik, de hosszú távon szabályszerű viselkedést mutat: a prímszámtétel (Prime Number Theorem) szerint az n-nél kisebb prímszámok száma, jelöljük π(n)-nel, közelítőleg n / log n. Ez megadja a prímszámok ritkulásának mértékét nagy számoknál.
Prímtulajdonságok és különleges típusok
- Twin prime (ikrek): olyan prímpárok, amelyek különbsége 2 (például 3 és 5, 11 és 13). Az ikerprím-sejtés szerint végtelen sok ilyen pár létezik; ez a sejtés ma is nyitott.
- Mersenne-prímek: a 2^p − 1 alakú számok közül azok, ahol p prímszám és a kifejezés maga is prímszám. Sok nagy ismert prímszám ilyen formájú, és gyakran közösségi projektek (például GIMPS) találják őket.
- Fermat-prímek, Sophie Germain-prímek és más családok — mindegyiknek saját érdekes tulajdonságai és sejtései vannak.
Primalitásvizsgálat — módszerek
- Próbafelosztás (trial division): egyszerű, de lassú nagy számoknál; alkalmas kis számokra.
- Sziták: Eratoszthenész szitája és fejlettebb sziták tömegesen találják meg a prímszámokat egy határig.
- Próbák és probabilisztikus tesztek: Miller–Rabin és más tesztek gyorsak és nagyon kicsi hibaprobabilitásúak; gyakorlatban nagy számoknál széles körben használják.
- Determinista polinom-idő: az AKS-algoritmus (2002) bizonyítja, hogy van determinisztikus polinom időben működő eljárás a primalitás döntésére, habár gyakorlati szempontból más módszerek hatékonyabbak nagy számok esetén.
- Prímbizonyítók: ha szükséges egy szám tényleges bizonyítása (nem csak valószínűségi eredmény), léteznek certifikátumok és algoritmusok (például ECPP), amelyek igazolják a primalitást.
Híres sejtések és nyitott problémák
- Goldbach-féle sejtés: minden 2-nél nagyobb páros egész szám felírható két prímszám összegeként. Ez a sejtés nagyon régi és máig megoldatlan.
- Ikerprím-sejtés: végtelen sok ikerprím létezése (nyitott).
- Riemann-sejtés: a prímszámok finom eloszlására vonatkozik; megoldása mély következményekkel járna a prímszámok eloszlásának pontos megértésére.
Alkalmazások
A prímszámoknak fontos szerepük van a modern kriptográfiában (például az RSA alapú titkosításban), pseudorandom számgenerálásban, hibajavító kódokban és különböző számelméleti algoritmusokban. Gyakorlati alkalmazásoknál a nagy prímszámok előállítása és gyors ellenőrzése kritikus feladat.
Összefoglalva: a prímszámok egyszerű definíciójuk ellenére mély és gazdag matematikai terület középpontjában állnak; eloszlásuk, szerkezetük és alkalmazásaik számos érdekes és még megoldatlan problémát rejtenek.
Megjegyzés: például az ismert legnagyobb talált prímszám egy Mersenne-prím: 2^82,589,933 − 1, amely 24 862 048 számjegyből áll (megtalálását közösségi projektek segítették).
A prímszámokról másképp is gondolkodhatunk. A 12-es szám nem prímszám, mert egy téglalapot lehet alkotni, amelynek oldalai 4 és 3 hosszúak. Ennek a téglalapnak a területe 12, mert mind a 12 kocka felhasználásra kerül. A 11-gyel ez nem lehetséges. Akárhogy is rendezzük el a téglalapot, mindig maradnak tömbök, kivéve azt a téglalapot, amelynek oldalai 11 és 1 hosszúságúak.
Hogyan találjuk meg a kis prímszámokat
Van egy egyszerű módszer a prímszámok listájának megtalálására. Eratoszthenész alkotta meg. Eratoszthenész szitája a neve. Felfogja a nem prímszámokat (mint egy szita), és átengedi a prímszámokat.
A módszer egy számlistával és egy b nevű speciális számmal dolgozik, amely a módszer során változik. Ahogy végigmész a módszerrel, bekarikázol néhány számot a listán, másokat pedig áthúzol. Minden bekarikázott szám prímszám, és minden áthúzott szám összetett szám. Az elején minden szám egyszerű: nincs bekarikázva és nincs áthúzva.
A módszer mindig ugyanaz:
- Írja fel egy papírlapra az összes egész számot 2-től a vizsgált számig. Az 1-es számot ne írd le. Menjünk a következő lépésre.
- Kezdjük úgy, hogy b egyenlő 2-vel. Menjünk a következő lépésre.
- Karikázza be a b-t a listában. Menjen a következő lépésre.
- A b-től kezdve számolj még b-vel feljebb a listán, és húzd ki ezt a számot. Ismételjük meg a számok számolását és a számok áthúzását a lista végéig. Menjünk a következő lépésre.
- (Például: Ha b 2, akkor bekarikázod a 2-est, és áthúzod a 4-est, 6-ost, 8-ast, és így tovább. Ha b 3, akkor bekarikázod a 3-at, és áthúzod a 6, 9, 12, stb. számokat. A 6 és a 12 már át lett húzva. Húzd át őket újra).
- Növelje a b értéket 1-gyel. Menjen a következő lépésre.
- Ha a b-t áthúzta, térjen vissza az előző lépésre. Ha b egy olyan szám a listán, amelyet nem húztak át, akkor lépjünk a 3. lépésre. Ha b nincs a listán, menjünk az utolsó lépésre.
- (Ez az utolsó lépés.) Kész is van. Az összes prímszámot bekarikáztuk, az összes összetett számot áthúztuk.
Ezt a módszert például a 2-től 10-ig terjedő számok listáján végezhetjük el. A végén a 2, 3, 5 és 7-es számok bekarikázva maradnak. Ezek prímszámok. A 4, 6, 8, 9 és 10 áthúzásra kerül. Ezek összetett számok.
Ez a módszer vagy algoritmus túl sokáig tart a nagyon nagy prímszámok megtalálásához. De kevésbé bonyolult, mint a nagyon nagy prímszámok esetében használt módszerek, például a Fermat-féle prímteszt (egy teszt, amely azt vizsgálja, hogy egy szám prím-e vagy sem) vagy a Miller-Rabin-féle prímteszt.
Mire használják a prímszámokat
A prímszámok nagyon fontosak a matematikában és a számítástechnikában. Az alábbiakban néhány valós felhasználási módot mutatunk be. A nagyon hosszú számokat nehéz megoldani. Nehéz megtalálni a prímtényezőiket, ezért a legtöbbször a valószínűleg prímszámokat használják titkosításra és titkos kódokra.
- A legtöbb embernek van bankkártyája, amellyel ATM segítségével pénzt vehet fel a számlájáról. Ezt a kártyát egy titkos hozzáférési kód védi. Mivel a kódot titokban kell tartani, nem tárolható a kártyán tiszta szövegben. A kód titkos tárolására titkosítást használnak. Ez a titkosítás szorzásokat, osztásokat és nagy prímszámok maradékainak megtalálását használja. A gyakorlatban gyakran használják az RSA nevű algoritmust. Ez a kínai maradéktételt használja.
- Ha valaki digitális aláírással rendelkezik az e-mailjéhez, akkor titkosítást használ. Ez biztosítja, hogy senki ne tudjon hamisítani egy tőlük származó e-mailt. Az aláírás előtt létrehozzák az üzenet hash-értékét. Ezt kombinálják a digitális aláírással, így jön létre az aláírt üzenet. Az alkalmazott módszerek nagyjából ugyanazok, mint a fenti első esetben.
- Az eddig ismert legnagyobb prímszám megtalálása egyfajta sporttá vált. Annak vizsgálata, hogy egy szám prím-e, nehéz lehet, ha a szám nagy. A jelenleg ismert legnagyobb prímszámok általában Mersenne-prímszámok, mivel a prímszámok leggyorsabb ismert tesztje a Lucas-Lehmer-teszt, amely a Mersenne-számok speciális formájára támaszkodik. Egy Mersenne-prímszámokat kereső csoport itt[1] található.
Kérdések és válaszok
K: Mi az a prímszám?
V: A prímszám olyan természetes szám, amely nem osztható más természetes számmal, kivéve az 1-et és önmagát.
K: Mi a legkisebb összetett szám?
V: A legkisebb összetett szám a 4, mert 2 x 2 = 4.
K: Melyek a 2 után következő prímszámok?
V: A 2 után a következő prímszámok a 3, 5, 7, 11 és 13.
K: Van-e legnagyobb prímszám?
V: Nem, nincs legnagyobb prímszám. A prímszámok halmaza végtelen.
K: Mit állít az aritmetika alaptétele?
V: Az aritmetika alaptétele kimondja, hogy minden pozitív egész szám felírható prímszámok szorzataként egyedi módon.
K: Mi a Goldbach-féle sejtés?
V: A Goldbach-féle sejtés egy megoldatlan probléma a matematikában, amely azt állítja, hogy minden kettőnél nagyobb páros egész szám kifejezhető két prímszám összegeként.
K: Ki jegyezte fel a bizonyítékot, hogy nincs legnagyobb prímszám?
V: Euklidész jegyezte fel a bizonyítékot, hogy nincs legnagyobb prímszám.
