Fejezetek a prímszámok csodálatos életéből
Bolyai János véleménye „Az egész számtan, sőt az egész tan mezején – alig van szebb és érdekesebb – … s a legnagyobb nyitászok (matematikusok) figyelme és eleje óta elfoglalt tárgy mint a főszámok (prímszámok) oly mély homályban rejlő titka.”
Értelmezés Az a természetes szám osztója a b természetes számnak, ha van olyan c természetes szám, hogy a és c szorzata éppen b. Minden természetes számnak osztója az 1 és maga a szám. Ezek a szám nem valódi osztói. Minden más osztó valódi osztó. Ha egy számnak valódi osztói is vannak, akkor az a szám összetett szám. Ha egy számnak csak nem valódi osztói vannak, akkor az a szám törzsszám. Egy 0-tól és 1-től különböző természetes számot prímszámnak nevezünk, ha két szám szorzatának pontosan akkor osztója, ha valamelyik tényezőnek osztója.
Prímtulajdonság A természetes számok körében a törzsszámok megegyeznek a prímszámokkal. Minden törzsszám prímszám és minden prímszám törzsszám. Így azok a természetes számok lesznek prímszámok, amelyeknek csak az 1 és maga a szám az osztója, azaz csak két osztójuk van. Ezek pedig: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, …
A prímek számáról Végtelen sok prímszám van. (Euklidesz) Tegyük fel, hogy véges sok prímszám van. Ekkor ezek szorzata összetett szám. Ha ezt a számot 1-gyel megnöveljük, akkor annak nem lesz osztója a véges sok prímszám közül egyik sem. Az így kapott szám nem lehet összetett szám, akkor viszont prím. Konstruáltunk egy olyan prímszámot, amely a véges sok ismert prímtől különböző. Így nem lehet igaz az a feltevés, hogy véges sok prímszám van. Ez viszont azt jelenti, hogy végtelen sok prímszám van.
Eratoszthenészi-szita Prímszámok megtalálására szolgáló eljárás, amely során egy-egy prím többszöröseit kivesszük a lehetséges prímek közül.
A számelmélet alaptétele Minden összetett szám – a tényezők sorrendjétől eltekintve – egyértelműen írható fel prímszámok hatványainak szorzataként. Például: 18 = 2 ⋅ 32
69 = 3 ⋅ 23
Felhasználható: Legnagyobb közös osztó: (18; 69) = 3 Legkisebb közös többszörös: [18; 69] = 2 ⋅ 32 ⋅ 23 = 414 τ(69) = 2 ⋅ 2 = 4 Osztók száma: τ(18) = 2 ⋅ 3 = 6
Goldbach-sejtés (1742.) Minden 2-nél nagyobb páros természetes szám előáll két páratlan prímszám, vagy az 1 és egy páratlan prímszám összegeként. Például: 22 = 3 + 19 = 5 + 17 = 11 + 11 100 = 3 + 97 = 29 + 71 = 47 + 53 2010 = 997 + 1013 Minden 5-nél nagyobb páratlan természetes szám előáll három páratlan prímszám összegeként. Például: 69 = 3 + 7 + 59 595 = 97 + 181 + 317 2971 = 983 + 991 + 997
A prímszámok eloszlása A szomszédos prímszámok között akármekkora hézagok előfordulnak. (Azaz tetszőleges hosszúságú prímszámmentes intervallum van.) Tekintsük a következő számokat: n! + 2, n! + 3, n! + 4,…, n! + n (Megjegyzés: n! = n ⋅ (n – 1) ⋅ (n – 2) ⋅ …⋅ 3 ⋅ 2 ⋅ 1) Ez n – 1 egymást követő szám, amelyek egyike sem prím, hiszen rendre oszthatók 2-vel, 3-mal, 4-gyel, és végül n-nel. Például: Ha n = 6, akkor 722 és 726 között nincs prím.
A prímszámok eloszlása Egy pozitív egész szám és a kétszerese között mindig van prímszám. Azaz bármely n esetén található olyan p prímszám, hogy n < p ≤ 2n. (Csebisev-tétel) Például: 2 – 3 – 4 vagy 5 – 7 – 10 A tétel egyszerű bizonyítását 19 évesen adta meg Erdős Pál (1913-1996.). Előtte már bizonyította 1850 körül Csebisev is. A mai napig nem sikerült még rájönni arra, hogy mindig van-e prímszám két négyzetszám között.
A prímszámtétel A prímszámok eloszlásáról a legtöbbet a prímszámtétel mondja, amelyet Hadamard és de la Valle-Poussin egymástól függetlenül bizonyított be 1896-ban. (Erdős és Selberg meg adott egy egyszerűbb bizonyítást 1949ben.) Legyen x pozitív valós szám. Ekkor ̟(x) jelölje az x-nél nem nagyobb prímek számát. Pl.: ̟(10) = 4 (ezek 2, 3, 5, 7); ̟(100) = 25; ̟(1000) = 168 A prímszámtétel a következőt állítja: x π (x ) π (x ) ~ lim =1 x →∞ x ln x ln x
Például: 10 / ln10 ≈ 4,34 100 / ln100 ≈ 21,71 1000 / ln1000 ≈ 144,76
Prímszámképletek Azt tényként közölhetjük, hogy nincs olyan nem konstans, egyváltozós polinom, amelynek minden helyettesítési értéke prímszám lenne. De vannak olyan polinomok, amelyek helyettesítési értékei prímek – bizonyos számú, egymás után következő értékek esetén. A legismertebb: f(x) = x2 + x + 41, ha 0 ≤ x < 40. Leonhard Euler (1707-1783.) egyik prímeket generáló képlete. Számítógépek segítségével meggyőződtek arról, hogy ez a képlet meglepően jól működik. Ugyanis a 10 millió alatti értékeknél 47,5%ban prímeket eredményezett.
Prímszámképletek Szintén Euler érdeme az f(x) = x2 + x + 17 képletet, amely prímeket ad, ha 0 ≤ x < 16. (Az Ulam-spirál főátlójában lévő prímek.) Ugyancsak prímeket ad az f(x) = x2 – 79x + 1601 polinom, ha 0 ≤ x < 80. (Escott) És egy újabb: f(x) = x4 – 97x3 + 3294x2 – 45458x + 213589, ha 0 ≤ x < 50.
Nevezetes prímszámok A számelmélet számos mély tétele, nevezetes problémája foglalkozik azzal, hogy léteznek-e bizonyos alakú prímek. Az viszonylag könnyen belátható, hogy végtelen sok 4k – 1 alakú prím van. (Például: 3, 7, 11, 19, 23,…) Kicsit nehezebb annak a bizonyítása (de megcsinálható), hogy a 4k + 1 alakú prímszámokból is végtelen sok van. (Például: 5, 13, 17, 29,…) Ezek viszont mindig előállíthatók két négyzetszám összegeként. Viszont a mai napig nem sikerült még belátni azt, hogy végtelen sok k2 + 1 alakú prímszám van. (Például: 2, 5, 17, 37,…)
Fermat-prímek A Fermat-számok a 22n + 1 alakú számok. Az ilyen alakú prímszámok a Fermat-prímek. Például: 3, 5, 17, 257, 65537. (Csak ezek ismertek. Azt sejtik, hogy nincs is több.) Pierre de Fermat (1601-1665.) Az triviális, hogy végtelen sok Fermatszám van. De az is belátható, hogy bármely kettő ezek közül relatív prím (legnagyobb közös osztójuk az 1).
Szabályos sokszögek Karl Friedrich Gauss (1777-1855.) bizonyította be a szabályos sokszögek szerkeszthetőségére vonatkozó tételt. Egy szabályos n-szög akkor és csak akkor szerkeszthető körzővel és vonalzóval, ha n = 2k ⋅ p1 ⋅ p2 ⋅…⋅ pr ahol k = 0, 1, 2,… és p1, p2,…, pr mind különböző Fermat-prímek.
Szabályos sokszögek A jelenleg ismert öt Fermat-prím: 3, 5, 17, 257, 65537, így az ilyen oldalszámú szabályos sokszögek szerkeszthetők.
Szabályos ötszög
Szabályos tizenhétszög
Gauss síremlékén látható szabályos tizenhétcsillag
Szabályos 257-szög
És szerkeszthető még a szabályos hatszög, tizenkétszög, tízszög, tizenötszög, stb.
Mersenne-prímek A Mersenne-számok a 2p – 1 alakú számok, ahol p prímszám. Közülük a prímek a Mersenne-prímek. Például: 3, 7, 31, 127, 8191… Marin Mersenne (1588-1648.) Az látható, hogy a Mersenne-számok is végtelen sokan vannak. De azt még nem sikerült belátni, hogy a Mersenneprímek száma is végtelen.
Mersenne-prímek Jelenleg 47 Mersenne-prímet ismerünk. A 45. Mersenne-prím a ma ismert legnagyobb prímszám, 12 978 189 számjegyből áll. 2008. augusztus 23-án bukkantak rá:
243 112 609 – 1 2009. április 12-én találták meg a 47. Mersenne-prímet, amelynek 12 837 064 számjegye van, tehát kisebb mint a 45. Mersenne-prím:
242 643 801 – 1
GIMPS 1996-ban jött létre az Amerikai Egyesült Államokban a Great Internet Mersenne Prime Search (GIMPS) nevű szervezet. Akik csatlakoznak hozzá, jogosultak lesznek annak a programnak a használatára, amely ellenőrzi egy újabb Mersenne-számról a lehetséges prímségét. Ha a program lefut (ez 40-50 napot jelent), és jelzi, hogy van remény arra, hogy a vizsgált szám Mersenne-prím legyen, akkor lefuttatnak egy prímtesztet (Lucas-Lehmer-teszt) néhány szuperszámítógépen, hogy ellenőrizhessék a prímtulajdonságot.
www.mersenne.org
Csupa 1 prímek Ők olyan prímszámok, amelyek tízes számrendszerbeli alakja csak 1-es számjegyet tartalmaz.. Például: 11 1111111111111111111 (19 számjegy) 11111111111111111111111 (23 számjegy) A következőnek 317, az azt követőnek pedig 1031 számjegye van.
Szuperprímek Azok a prímszámok lesznek szuperek, amelyeknek a prímszámok sorozatában vett indexe is prímszám. Például: Index
1.
Prímszám 2
2. 3. 4. 5. 6. 7. 8. 9. 10. 11. … 3
5
7
11 13 17 19 23 29 31 …
Ikerprímek A p és p + 2 alakú prímeket ikerprímeknek nevezzük. (Olyan prímek, amelyek különbsége 2.) Például: 3 – 5, 5 – 7, 11 – 13,…, 1997 – 1999,… A mai napig nem sikerült még igazolni, hogy az ikerprímek száma is végtelen. A jelenleg ismert legnagyobb ikerprímek (2009-ből): 65516468355 ⋅ 2333333 – 1 és 65516468355 ⋅ 2333333 + 1
Unokatestvér prímek A p és p + 4 alakú prímeket unokatestvér prímeknek nevezzük. (Olyan prímek, amelyek különbsége 4.) Például: 3 – 7, 7 – 11, 13 – 17,…, 277 – 281,…
Szexi prímek A p és p + 6 alakú prímeket szexi prímeknek nevezzük. (Olyan prímek, amelyek különbsége 6.) Például: 5 – 11, 7 – 13, 11 – 17,…, 193 – 199,…
Álprímek Egy páratlan összetett N számot a alapú (Fermat-féle) álprímnek nevezünk, ha az aN – 1-nek az N-nel vett osztási maradéka 1. Például: 341 2-es alapú álprím Legyen N páratlan összetett szám, és N – 1 = 2s ⋅ d, ahol d páratlan. Az N számot a alapú dörzsölt álprímnek nevezzük, ha az ad-nek az Nnel vett osztási maradéka 1 vagy az a2r ⋅ d-nek az N-nel vett osztási maradéka –1, valamely r = 1, 2, 3,…, r – 1 számok esetén. Például: Ilyet nehéz találni. 25 milliárdig mindössze 13 olyan dörzsölt álprím van, amely a 2, 3, 5 alapokra egyaránt álprímnek bizonyul.
Prímsorok A prímszámok reciprokából álló sor ∞
∑ k =1
1 1 1 1 1 = + + + + ... pk 2 3 5 7
Tétel biztosítja azt a kellemes tényt, hogy a prímszámok reciprokából álló sor divergens, azaz a végtelen sok prímszám reciprokát összeadva az eredmény végtelen.
Prímsorok Az ikerprímszámok reciprokából álló sor
1 1 1 1 1 1 1 1 + + + + + + + + ... 3 5 5 7 11 13 17 19 Azt nem tudjuk, hogy véges vagy végtelen sok ikerprímszám van-e, de az biztos, hogy a reciprokaikból álló sor összege egy konkrét valós szám. Viggo Brun bizonyította ezt 1919-ben. Ez a szám pedig (közelítve):
B2 = 1,902160583208562
Ulam-spirál Stanislaw Ulam lengyel matematikus 1963-ban egy rendkívül hosszú és unalmas értekezést hallgatott, amikor is felírta egy papírra 1-től kezdődően a számokat spirál alakban, negatív irányban.
Ulam-spirál Ulam meglepődve látta, hogy a spirálban a prímszámok átlós vonalak mentén helyezkednek el.
Ulam-spirál 10 millióig le is ellenőriztette Ulam egy számítógéppel az átlós elhelyezkedést, és az igaznak bizonyult. A 200 × 200-as Ulam-spirál:
Ulam-spirál Ulam egy másik ábráján a 17 áll középen, és egészen 272-ig vezette a számokat. A prímszámok itt is átlós elrendezést mutatnak.
Az átlóban található prímek éppen az Euler-féle f(x) = x2 + x + 17 prímeket adó polinom helyettesítési értékei.
Geometriai elrendezések Reginald Brooks két érdekes elrendezést talált a prímszámokkal (2001.)
Spirál mentén helyezkednek el a prímszámok szabályos tízszögek csúcsaira illeszkedve.
Egy csillag mentén helyezkednek el a prímszámok ebben a konstrukcióban.
Prímcsillag Allan Johnson készítette az alábbi csillagot.
Érdekessége, hogy 3-tól 71-ig tartalmazza a prímszámokat úgy, hogy minden vonal mentén a számok összege állandó, ráadásul az is prím, a 167.
Az RSA-algoritmus Ez egy olyan kódolási (titkosítási) eljárás, amely prímszámokat használ fel. 1976-ban debütált a nyilvános kulcsú titkosítás ezen formája a MIT-en, Ronald Rivest, Adi Shamir és Len Adleman közreműködésével. Az eljárás legfőbb ötlete: Nagyon könnyű két prímszámot összeszorozni, de nagyon nehéz csak a szorzat ismeretében megadni, hogy mely prímeket is szoroztuk össze.
Az RSA-algoritmus Az algoritmus lépései: 1. Válasszunk véletlenszerűen két nagy prímszámot: p1 és p2. 2. Kiszámítjuk az m = p1p2 és ϕ(m) = (p1-1)(p2-1) paramétereket, és választunk véletlenszerűen egy e számot (1 és ϕ(m) között) úgy, hogy e és ϕ(m) relatív prímek legyenek. 3. Kiszámítjuk e inverzét (d), amelyre ϕ(m) osztója lesz a d ⋅ e – 1 különbségnek. 4. Nyilvánosságra hozzuk: m és e; titokban tartjuk: d, p1 és p2. 5. Az x nyílt üzenetet az y-ra titkosítjuk úgy, hogy m osztója legyen az xe – y különbségnek. (Az y ismeretében x visszafejthető, mert azt az x-et keressük, amelyre m osztója lesz az x – yd különbségnek.)
Az RSA-algoritmus Példa: 1. A két prím legyen 73 és 151. 2. Ekkor m = 73 ⋅ 151 = 11023, ϕ(m) = (73 – 1)(151 – 1) = 10800. Legyen e = 11. (Relatív prímek 10800-zal.) 3. Ekkor a 11 inverze kiszámítható és az 5891 lesz. 4. Nyilvánosságra hozzuk: 11023 és 11; titokban tartjuk: 5891, 73 és 151. 5. Ha x = 17-et kell titkosítani, akkor y = 1782-t kapunk.
A kutya különös esete… Mark Haddon: A kutya különös esete az éjszakában (2004.) A könyv egy autista fiú, Christopher kalandjait meséli el. Ő nagyon sokat tud a matematikáról és a fizikáról, de nagyon keveset az emberi érzelmekről. Alighanem ő a világirodalom egyik legkülönösebb nyomozója; egy este ugyanis a szomszéd kutyáját döglötten, vasvillával átszúrva találja a kertben, és elhatározza, hogy kinyomozza, ki ölte meg a kutyát.
A kutya különös esete… A 47. fejezetben olvasható a nevek számosításának ötlete. A betűknek megfeleltetjük a számokat, és a betűk értékeit összeadjuk. Az nagyon jó, ha az összeg prímszám lesz.
Például: James Bond (83) Scooby Doo (113) Sherlock Holmes (163) Molnár Zoltán (163)
Ajánlat Könyvek: Megyesi László: Bevezetés a számelméletbe Paul Hoffman: A prímember
Filmek: Tükröm, tükröm A 23-as szám
Feladvány 1. Add meg azt a négyjegyű prímszámot, amely számjegyeinek összege és szorzata is prím. 2. Oldd meg a 2x + 3y + 6z = 78 egyenletet a prímszámok körében! 3. James Bond a futóversenyen 4. Prímcsillag 5. Prímkeresztrejtvény
Konklúzió Miért is szeretjük a prímszámokat? Matematikai válasz: A természetes számok „építőkövei”. A másik válasz:
A 43. dia Ez a 43. dia.
