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).