Tóth Attila
Prímszámok
Prímszámok A cikkben szereplő eredmények 2008 decemberéből származnak.
Bevezetés Prímszámokon vagy felbonthatatlan számokon olyan pozitív egész számokat értünk, amelyeknek csak két pozitív osztójuk van, nevezetesen az 1 és önmaguk. Ezeket szokták triviális (nyilvánvaló) osztóknak is hívni. A prímszámok 2, 3, 5, 7, 11, 13, 17,. . . sorozata a matematika egyik legegyszerűbben megadott, ugyanakkor talán legtitokzatosabb halmaza. A sok eredmény között ugyanis rengeteg a tisztázatlan kérdés, megoldatlan probléma. Néhány érdekes eredményt, illetve sejtést szeretnék az alábbiakban megfogalmazni. A továbbiakban csak pozitív egész számokról lesz szó, tehát számokon ezentúl mindig ilyen számokat fogok érteni. Ha egy számnak triviálistól különböző osztója is van, akkor összetett számnak nevezzük. Talán a legismertebb, prímszámokkal kapcsolatos tétel a számelmélet alaptétele, mely szerint minden 1-nél nagyobb szám felbontható prímszámok szorzatára, és a felbontás a tényezők sorrendjétől eltekintve egyértelmű. Könnyű bebizonyítani, hogy ha n összetett √ szám, akkor a legkisebb prímosztója nem lehet nagyobb n-nél. Így√ ha el szeretnénk dönteni például a 30 031 számról, hogy prímszám-e, akkor elég 173 < 30 031 < 174 miatt 173-ig elosztani a prímszámokkal. Ha elvégeznénk az osztásokat, akkor azt tapasztalnánk, hogy egyik prím se osztja, így 30 031 prímszám. Hogyan lehet meghatározni egy n számig a prímszámokat? Egyik lehetőség az úgynevezett eratosztenészi szita. Írjuk fel 1-től n-ig a számokat. Húzzuk ki az 1-et, hiszen az nem prímszám. Az első, nem kihúzott számot karikázzuk be, ez prímszám lesz (2). Húzzuk (szitáljuk) ki a 2 többszöröseit n-ig, majd a számok sorozatában az első ki nem húzott és be nem karikázott számot karikázzuk be, ez lesz a következő prímszám (3). Most ennek a többszöröseit kell kiszitálni n-ig, majd az első, ki nem szitált és be nem karikázott számot (5) kell bekarikázni, ez lesz a következő prím. És így tovább. A bekarikázott számok lesznek n-ig a prímszámok.
1
Typeset by LATEX
Tóth Attila
Prímszámok
Felmerül a kérdés, hogy van-e tetszőlegesen sok prímszám? A válasz erre igen, végtelen sok prímszám van. Ugyanis, ha véges sok prímszám volna, akkor ezek szorzatához 1-et adva egy újabb prímszámot kapunk. Érdemes meggondolni, hogy miért. Könnyű-e meghatározni egy szám prímtényezős felbontását? Látszólag igen, hiszen csak meg kell nézni rendre, hogy osztható-e 2-vel, 3-mal, stb. Ha találunk egy prímosztót, akkor a hányadost kell tovább bontani. Ha pedig a szám négyzetgyökéig elmenve egyáltalán nem találunk osztót, akkor a szám biztosan prímszám. Ily módon gyorsan fel tudjuk bontani például a 143-at, vagy be tudjuk látni, hogy a 197 prímszám. Próbálkozzunk azonban mondjuk a 267 − 1 számmal. Mersenne (ejtsd: mer(s)zen) francia matematikus 1644-ben egy hosszú listát közölt prímszámokról, amelyben erről a számról azt állította, hogy prímszám. Ezt a kérdést több mint 200 évig nem tudták eldönteni. 1876-ban a szintén francia Lucas (ejtsd: lüká) kimutatta, hogy Mersenne tévedett; ez a szám összetett. Prímtényezőkre azonban neki sem sikerült bontania, csak az összetettség tényét igazolta. Végül 1903-ban az amerikai Cole (ejtsd: kól) találta meg a 193 707 721 · 761 838 257 287 felbontást, miután sok évig minden vasárnap délutánját ennek a problémának szentelte. A Rivest–Shamir–Adleman (RSA) nyilvános kulcsú titkosírás Nagy számok prímfelbontásának a kérdésekor a nehézséget az jelenti, hogy olyan sok próbálkozást kellene végrehajtani, amelyhez évmilliárdok sem elegendők. Egy 200 jegyű számot, amelynek nincsenek kis prímosztói, vagy nincs valamilyen speciális tulajdonsága, a jelenlegi leggyorsabb számítógépek sem tudnak a Nap kihűlése előtt tényezőkre bontani. Ugyanakkor vannak olyan eljárások, amelyek gyorsan eldöntik, hogy egy nagy szám prímszám-e vagy összetett (azonban az utóbbi esetben sem tudják megadni a tényezőket). Ha tehát valaki két nagy prímszámot összeszoroz, akkor az így kapott szorzatot senki sem tudja felbontani rajta kívül, ez egyedül az ő titka marad. Ezen alapulnak azok az új titkosírási sémák, amelyeket ma szerte a világon, a katonai, a diplomáciai és az üzleti élet számos területén sikerrel alkalmaznak. A nyilvános kulcsú titkosírás arra használható, hogy úgy kódolja két levelező partner üzenetét, hogy ha valaki meg is tudja szerezni a kódolt üzenetet, akkor sem tudja megfejteni. A nyilvános kulcsú titkosírás lehetővé teszi azt is, hogy a felek hamisíthatatlan „digitális aláírással” lássák el az elektronikus üzenetet. Ez az aláírás a hivatalos dokumentumok kézirásos aláírásának elektronikus változata. Bárki könnyen összevetheti az eredetivel, de 2
Tóth Attila
Prímszámok
nem hamisítható, azaz szavatolja mind az aláíró személyét, mind az aláírt üzenet tartalmát. Az RSA nyilvános kulcsú titkosírás létét annak a szinte drámai különbségnek köszönheti, hogy milyen könnyű nagy prímszámokat találni, és ezzel szemben milyen nehéz két nagy prím szorzatát tényezőkre bontani. Biztonságosnak tűnik ez az eljárás, bár nincs kizárva, hogy valaki talál egy olyan módszert, amellyel gyorsan tud nagy számokat is prímtényezőkre bontani és akkor hozzáfér a megfejtő kulcshoz. Mindez azonban meglehetősen valószínűtlen.
Prímszámok eloszlása A továbbiakban a prímszámoknak a számok sorozatában való eloszlását vizsgáljuk. Hézag a szomszédos prímszámok között Igen érdekes tétel az úgynevezett hézag tétel, mely szerint tetszőleges nagy n pozitív számhoz meg lehet adni n számú szomszédos összetett számot. Ez azt jelenti, hogy két „szomszédos” prímszám között tetszőleges nagy lehet a távolság (hézag). Tehát lehet mondani egymás után mondjuk egymillió összetett számot. Másik érdekes tétel a Csebisev-tétel. A tétel szerint minden 1-nél nagyobb szám és a kétszerese között van prímszám. Ezek szerint például 100 és 200 között kell lenni legalább egy prímszámnak. Fontos megjegyezni, hogy ez a tétel nem áll ellentmondásban a hézag tétellel. A számos megoldatlan problémák egyike: igaz-e, hogy két négyzetszám között mindig van prímszám? Számtani sorozatok prímszámai A 3–5–7, 5–11–17–23–29, 7–37–67–97–127–157,. . . olyan prímszámok, amelyek egyenlő távolságra helyezkednek el.
3
Tóth Attila
Prímszámok
Az eddig talált leghosszabb számtani sorozatnak, amely csupa prímszámból áll, 22 tagja van, ebből hármat ismerünk: 28 383 220 937 263 + 1 861 263 814 410 · k,
k = 0, 1, . . . , 21.
A differencia 2 · 35 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 103. 11 410 337 850 553 + 4 609 098 694 200 · k,
k = 0, 1, . . . , 21.
A differencia 23 · 3 · 52 · 7 · 11 · 13 · 17 · 19 · 23 · 1 033.
376 859 931 192 959 + 18 549 279 769 020 · k,
k = 0, 1, . . . , 21.
A differencia 22 · 3 · 5 · 72 · 11 · 13 · 17 · 19 · 23 · 5 939.
Könnyű megmondani viszont, hogy végtelen számtani sorozat már nem állhat elő csupa prímszámokból, ehhez elég csak a hézag tételre hivatkozni. A közelmúltban, 2004-ben bizonyította be Ben Green (University of British Columbia, Vancouver) és Terence Tao (University of California, Los Angeles), hogy van tetszőleges véges hosszú számtani sorozat csupa prímszámból. Nem tudjuk, hogyan lehet 23 tagú sorozatot találni, de már tudjuk, hogy ilyenek léteznek. Egy további érdekes tétel a német Dirichlet (ejtsd: dirislé) nevéhez fűződik. Dirichlet tétele szerint az ak + b, k = 0, 1, 2, . . . számok között akkor és csak akkor van végtelen sok prímszám, ha a és b relatív prímek. Mivel például a 4 és 1 relatív prímek, ezért a 4k + 1 alakú számok közt (4-gyel osztva 1 maradékot adnak) végtelen sok prímszám van. Megoldatlan probléma, hogy végtelen sok k 2 + 1 alakú prím van-e. Prímszámtétel Jelöljük π(x)-szel az x-ig terjedő prímszámok számát. Tehát például π(10) = 4, π(20) = 8, π(100) = 25. Ha érdekel minket, hogy x-ig körülbelül mennyi prímszám van, akkor először ki kell számolnunk, hogy 2,7182-nek hányadik hatványa az x, majd ezzel a számmal el kell osztani x-et. Körülbelül ennyi prímszám van x-ig. Nézzük meg, hogy 1 000-ig körülbelül mennyi prímszám van! Mivel 1 000 ≈ 2, 71826,9078 , 4
Tóth Attila
Prímszámok
1 000 . Ez az érték körülbelül 144. A négyjegyű függvénytáblázatok 6, 9078 53. oldala alapján a pontos érték 168.
ezért π(1 000) ≈
Ez a tétel mutatja, hogy a prímszámok sokkal „sűrűbben” helyezkednek el az egész számok között, mint például a négyzetszámok.
Nevezetes problémák Ikerprímek nek nevezzük az olyan szomszédos páratlan számokat, amelyek mindegyike prímszám. Néhány példa ikerprímekre: 3–5, 5–7, 11–13, 17–19. A mai napig kérdéses, hogy van-e végtelen sok ikerprím. Valószínűnek tűnik, hogy igen, ennek ellenére még nem nyert bizonyítást ez az állítás. A legnagyobb ismert ikerprím: 2 003 663 613 · 2195 000 ± 1, mindkettő 58 711 számjegyű. Ellenben könnyű belátni, hogy olyan hármasiker ből, mint a 3–5–7, csak ez az egy van. Érdekes probléma az úgynevezett Goldbach-sejtések problémája. 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7. Igaz-e, hogy minden 4-nél nagyobb vagy egyenlő páros szám felírható két prímszám összegeként? Ez a nyitott kérdés a páros Goldbach-sejtés. A páratlan Goldbach-sejtés szerint minden 7-nél nagyobb vagy egyenlő páratlan szám felírható három prímszám összegeként. Be lehet bizonyítani, hogy ha a páros Goldbachsejtés igaz, akkor igaz a páratlan is. Sajnos csupán csak a páratlan Goldbach-sejtés nyert bizonyítást, ez is csak „elég nagy” számokra, és ebből a páros Goldbach-sejtés nem következik.
Mersenne-prímek és tökéletes számok Mersenne-nek az előbbiekben említett listája a 2k − 1 alakú prímszámokra vonatkozott. Nem nehéz bebizonyítani, hogy ha 2k − 1 prím, akkor szükségképpen maga k is prím. Ezeket a prímszámokat ma Mersenne-prímek nek nevezzük. Jelenleg 46 ilyen prímszám ismert, ezek az alábbi k kitevőkhöz tartoznak: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1 279, 2 203, 2 281, 3 217, 4 253, 4 423, 9 689, 9 941, 11 213, 19 937, 21 701, 23 209, 44 497, 86 243, 110 503, 132 049, 216 091, 756 839, 859 433, 1 257 787, 1 398 269, 2 976 221, 3 021 377, 6 972 593, 13 466 917, 20 996 011, 24 036 583, 25 964 951, 30 402 457, 32 582 657, 37 156 667 és 43 112 609. Közülük az utolsó, 243 112 609 − 1 a legnagyobb ismert prímszám, 12 978 189 számjegyből áll. Ha ezt a számot megpróbálnánk leírni úgy egy spirálfüzetbe, hogy minden egyes számjegyet egy négyzetrácsba írunk, akkor a szám 5
Tóth Attila
Prímszámok
hossza közel 65 km lenne. Megoldatlan probléma, hogy végtelen sok ilyen alakú prím van-e. Valószínűnek látszik, hogy a 2p − 1 alakú számok között, ahol p prím, végtelen sok prímszám van, és végtelen sok összetett szám szerepel, de mindkét probléma megoldatlan. Hogyan lehet egy nagy 2k − 1 alakú számról viszonylag gyorsan eldönteni, hogy prím-e? Erre vonatkozik az alábbi teszt, amit a már említett Lucas dolgozott ki, majd azt Lehmer tökéletesítette. Legyen a1 = 4 és an+1 = a2n − 2, ha n ≥ 1. Legyen továbbá p > 2 prím. Ekkor az Mp = 2p − 1 szám akkor és csak akkor lesz prím, ha Mp | ap−1 . Ennek a tételnek a segítségével találta meg Lucas az első hibát a Mersenne-féle listában, és ma is ilymódon tesztelik a nagy Mersenne-számokat. Természetesen nem szükséges magukat az ai -ket kiszámítani, csak az Mp -vel vett maradékukra van szükség. A LucasLehmer teszt nem adja meg az összetett Mersenne-számok egyetlen osztóját sem. Sajnos. A Mersenne-prímek szoros kapcsolatban állnak az úgynevezett tökéletes számok kal. A régi görögök azokat a számokat hívták így, amelyek megegyeztek osztóik összegével, ha magát a számot nem tekintjük osztónak. Ilyen például a 6 = 1 + 2 + 3, a 28 = 1 + 2 + 4 + 7 + 14, stb. Egy tétel szerint egy n szám akkor és csak akkor tökéletes, ha n = 2k−1 (2k − 1), ahol 2k − 1 Mersenne-prím. A tétel „akkor” részét már Euklidész is ismerte mintegy 2300 évvel ezelőtt, a másik irányt Euler bizonyította be XVIII. században. Ennek alapján tehát jelenleg 46 páros tökéletes számot ismerünk, és megoldatlan probléma, hogy végtelen sokan vannak-e. Az is megoldatlan, hogy létezik-e páratlan tökéletes szám. Biztos sokakban felmerül, hogy kapjuk elő a számológépet és keressünk páratlan tökéletes számot. Nem érdemes! Számítógéppel 100200 -ig egyet se találtak (a világegyetem részecskéinek számát „mindössze” 1088 -ra becsülik). Ha vannak ilyen számok, ennél a számnál biztosan nagyobbak. Ezek talán a matematika legrégibb megoldatlan problémái. Pedig milyen egyszerűen hangzanak!
6
