Prímszámok

A prímszámok olyan számok, amelyek csak 1-gyel és önmagukkal oszthatók. A prímszámok tulajdonságait gyakran használják például a kriptográfiában.

Definíció és példák

A prímszám olyan természetes szám, amely maradék nélkül csak 1-gyel és önmagával osztható, az 1 viszont nem prímszám. A legkisebb prímszám a 2 – maradék nélkül osztható 1-gyel és 2-vel. Egyben ez az egyetlen prímszám, amely páros. Az összes többi prímszám páratlan, hiszen bármely más páros szám az 1-en és önmagán kívül osztható még 2-vel is.

Az első néhány prímszám sorozata: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271…

A prímszámokhoz kapcsolódik a számelmélet alaptétele, amely azt mondja ki, hogy minden 1-nél nagyobb egész szám felbontható prímszámok szorzatára.

Teszteld, hogy a szám prímszám-e

A prímszámok tulajdonságai

• Végtelen sok prímszám van. A bizonyítás az indirekt bizonyításról szóló cikkben található.
• Minden z>1 egész számra igaz, hogy a ]z; 2z[ intervallumban van legalább egy prímszám. Példa: z = 2 esetén a ]2; 4[ intervallumot kapjuk. Az egyetlen egész szám ebben az intervallumban a 3, és ez prímszám. z = 5 esetén a ]5; 10[ intervallumot kapjuk, vagyis a 6, 7, 8, 9 számokat. A 7 prímszám. Nagyobb z esetén hasonlóan.
• A Mersenne-prím olyan prímszám, amely eggyel kisebb, mint a 2 valamilyen egész kitevős hatványa. Az M Mersenne-prím tehát M = 2^z − 1 alakú, ahol z valamilyen természetes szám. Példa erre a 3, mert 2² − 1 = 3. Vagy a 7, mert 2³ − 1 = 7.
• A legnagyobb ismert prímszámok általában éppen Mersenne-prímek. Például 2008. augusztus 23-án találták meg az M_43112609 Mersenne-prímet, ahol az alsó index a z kitevőt adja meg. Ez tehát a 2^43112609 − 1 prímszám, amelynek 12 978 189 számjegye van, és akkoriban ez volt a legnagyobb ismert prímszám.

Prímszámmentes sorozat

Tetszőlegesen hosszú véges sorozatot találhatunk egymást követő természetes számokból úgy, hogy közöttük egyetlen prímszám sincs. Egy ilyen sorozat lehet például k!+2, k!+3, …, k!+k alakú, és k − 1 egymást követő összetett számot tartalmaz (a felkiáltójel a faktoriális).

Például k = 6 esetén öt egymást követő összetett számot kapunk: 720 + 2, 720 + 3, 720 + 4, 720 + 5, 720 + 6. Ezek rendre oszthatók 2-vel, 3-mal, 4-gyel, 5-tel és 6-tal, mert a 6! = 720 biztosan osztható mindezekkel a számokkal, hiszen az ő szorzatukból keletkezett: 6! = 6 · 5 · 4 · 3 · 2. Ha a 720 osztható 3-mal, akkor a 720 + 3 is osztható 3-mal. A többinél hasonlóan.

A kis Fermat-tétel

Minden p prímszámra és minden z egész számra igaz, hogy a z^p − z szám osztható a p prímszámmal.

Példa: vegyük a p = 3 prímszámot és a z = 4 egész számot. Kiszámítjuk a 4³ − 4 értékét. Ez 60. Közben igaz, hogy 60/3 = 20, vagyis a 3 maradék nélkül osztja a 60-at, ami megfelel a Fermat-tételnek. Egy másik példa: p = 7, z = 10. Kiszámítjuk a részeredményt: 10⁷ − 10 = 9999990, és ezt elosztjuk 7-tel: 9999990/7 = 1428570. Ismét maradék nélküli eredményt kaptunk.

Megoldatlan kérdések

A prímszámokhoz sok híres sejtés kapcsolódik, amelyeket még (2011-ben) nem sikerült sem bebizonyítani, sem megcáfolni. A két legismertebb:

• Az ikerprímek végtelensége: az ikerprím-pár olyan (z; z + 2) számpár, amelynek mindkét tagja prímszám. Például (3; 5) vagy (29; 31). A kérdés az, hogy végtelen sok ilyen ikerprím-pár van-e. Feltételezik, hogy igen, de a bizonyítás hiányzik.
• A Riemann-sejtés: A Riemann-féle zéta-függvény minden nem triviális zérushelyének valós része $\frac{1}{2}$. A tétel a prímszámok eloszlásához kapcsolódik, és az úgynevezett millenniumi problémák egyike, ha megoldod, egymillió dolláros jutalom vár rád.