A prímszámok fogalmát valószínűleg már az egyiptomiak és a mezopotámiai népek is ismerték. Első, tervszerű tanulmányozói a püthagoreusok voltak, de a prímszámokra először Eukleidésznél találunk pontos meghatározást.
Mivel a prímszámok a természetes számok, illetve az egész számok „atomjai”, mindig nagyon foglalkoztatták a matematikusokat.
A prímszámokkal kapcsolatos legfontosabb kérdések:
• Prímszámok előállítása.
• Prímszámok elhelyezkedése, eloszlása.
• Prímszámok fajtái.
• Minél nagyobb prímszámot találni.
• Hogyan lehet egy számról megállapítani, hogy prím-e?
Prímszámok előállításáról:
Mivel az eratoszthenészi szita nagy számok esetén meglehetősen fáradságos (főleg, amikor még számítógépek sem álltak rendelkezésre), sok matematikus próbált a prímszámok előállítására formulát találni, de ezek a kísérletek nem jártak sikerrel. Érdekes megemlíteni Euler képletét: p(n)=n2+n+41. Ez a képlet prímszámokat ad n=1-től n=39-ig, de könnyű belátni, hogy n=40 illetve n=41 esetén a kapott szám összetett szám lesz.
Prímszámok eloszlása, elhelyezkedése a természetes számok között.
o Prímszámok száma végtelen.
o Ha a prímszámok elhelyezkedését vizsgáljuk, azt találjuk, hogy minél nagyobb számokból álló intervallumban keresünk, annál kevesebb számú prímet találunk. Például:
| 0 és a 100 között | 25 db prím |
| 900 és 1000 között | 14 db prím |
| 10 000 000 és 10 000 100 között |
2 db prím |
Egy más megközelítésben:
| Meddig | Prímszámok száma | % |
| 10-ig | 4 db | 40% |
| 100-ig | 25 db | 25 % |
| 1 000-ig | 168 db | 17 % |
| 10 000-ig | 1229 db | 12 % |
Gauss 1791-ben, 14(!) éves korában becslést adott erre, azt találta, hogy ezres számkörben a prímszámok száma fordítottan arányos a számok logaritmusával. Ezt később többen, például Riemann német matematikus is pontosították
o Ikerprímek, mint azt a prímszámok fogalmánál már láthattuk, azok, amelyek különbsége 2. Azaz közel vannak egymáshoz. Úgy tűnik, végtelen sok ikerprím van, de ezt még mind a mai napig nem sikerült bizonyítani.
o Bizonyított azonban, hogy a prímszámok között tetszőleges nagy hézagok vannak (amely számok között nincs prímszám).
o Bizonyított az is, hogy minden természetes szám és kétszerese között van prímszám. (Csebisev tétel.)
o Nem bizonyított viszont, hogy két négyzetszám között mindig van prímszám.
Különböző fajta prímek:
A páratlan prímszámok alapvetően két osztályba sorolhatók:
• 4n+1 alakú, ahol n pozitív egész. Például: 5, 13, 17, stb.
• 4n-1 alakú prímek, ahol n pozitív egész. Például: 3, 7, 11, stb.
Fermat tétele, hogy a 4n+1 alakú prímek mindig előállíthatók két négyzetszám összegeként (pl. 13=22+32), míg a 4n-1 alakú prímekre ez nem teljesül. Ez a tétel is azok közé tartozik, amelynek bizonyítását Fermat nem közölte. Jóval halála után Euler bizonyította be.
A prímszámokat csoportosíthatjuk még:
1. a⋅n + b alakú prímszámok, ahol n egész, és (a,b)=1, azaz relatív prímek. Ha n végigfut a nem-negatív egész számokon, akkor ezek a számok adott a és b esetén egy számtani sorozatot alkotnak.
Bebizonyítható, hogyha (a;b)=1, akkor ebben a számtani sorozatban végtelen sok prímszám lesz. De persze nem mindegyik.
Legyen a=3, b=5, így (3;5)=1, tehát 3⋅n+5 alakú számok között végtelen sok prímszám van. (n=1 esetén az érték 8 nem prím, n=2 esetén 11, ez prím, stb.)
2. Nagyon sok prímszám n2+1 alakú, ahol n pozitív egész.
Nyitott kérdés, hogy az ilyen típusú prímszámokból végtelen sok van-e?
Megjegyzés: Persze, ez a formula sem mindig prímszámot ad. Például n=1 esetén 2, n=2 esetén 5 is prím, de n=3 esetén 10 már nem prím.
3. 2n+1 alakú Fermat-féle prím, ahol n kettő hatvány, azaz n=2k, ahol k nem-negatív egész.
Például ez a kifejezés k=0, 1, 2,3, 4 esetén prímszámot ad, ezek 20+1=3, 22+1=5, 24+1=17, 28+1=257, 216+1=65537, de k=5 esetén a 232+1=4 294 967 296+1=4 294 967 297 nem prím, mivel 4 294 967 297=641*6 700 417. Ezt Euler mutatta ki.
Kétséges, hogy k>5 esetén a kapott számok prímek-e. Persze minden Fermat féle prím egyben n2+1 alakú is.
Érdekes geometria kapcsolat van a Fermat-féle prímek és a szabályos sokszögek szerkeszthetősége között.
Gauss bebizonyította, hogy az n oldalú prímszám oldalszámú szabályos sokszögek közül csak azok szerkeszthetők, amelyeknél az oldalak száma Fermat-féle prím. Tehát a prímszám oldalszámú sokszögek közül szerkeszthető a 3, 5, 17, 257 és a 65537 oldalú szabályos sokszög. A 17 oldalú sokszög szerkesztését maga Gauss oldotta meg.
4. 2p-1 alakú, Mersenne-féle prímek. (p prímszám). Marin Mersenne (1588. 09. 08. – 1648. 09. 01) francia matematikus, minorita szerzetesről kapta a nevét, aki Descartes osztálytársa volt. Ezek a prímek azért is nevezetesek, mert az ismert legnagyobb prímek mind ilyen alakúak. Mindössze 38 db. Mersenne prím volt ismert 2000. évig.
Melyik az ismert legnagyobb prímszám?
A legkisebb prímszám a 2, az egyetlen páros prím..
Bár tudjuk, hogy nem létezik legnagyobb prímszám, ennek ellenére a matematikusok egyre nagyobb prímszámok után kutatnak.
Sokáig (számítógépek előtti korszakban)a 2127-1 tartotta a rekordot, ez a szám is több mint 1038!
A számítástechnika színrelépésével következtek: 22281-1, majd 23217-1, és 24423-1 prímszámok.
Az 1996-ban indult GIMPS projekthez világszerte több mint százezer önkéntes csatlakozott, akik mind egy ingyenesen letölthető szoftvert telepítettek a számítógépükre. Az így létrehozott hálózat, a PrimeNet olyan, mint egy virtuális szuperszámítógép, másodpercenként 29 billió művelet végrehajtására képes, amely valóban a szuperszámítógépekéhez fogható teljesítmény. A két újjal együtt a GIMPS mostanáig 12 Mersenne-prímmel gazdagította az emberiséget.
A következő pályázat díja 150 ezer dollár. Az kapja meg, aki százmilliónál több jegyből álló Mersenne-prímszámot talál.
2016-ban talált prímszám: http://index.hu/tudomany/2016/01/21/22_millio_szamjegybol_all_az_eddigi_legnagyobb_primszam/
2018-ban talált prímszám: https://24.hu/tudomany/2018/01/05/megtalaltak-az-eddigi-legnagyobb-primszamot/.
Ez a prímszám 23 249 425 számjegyet tartalmaz és ez 50. ismert Mersenne-prím is. (277 232 917 –1).
2018. év végén talált 51. Mersenne-prím már 24,862,048 számjegyből áll. (282 589 933 –1)
Az eddig ismert nagyon nagy prímszámok közül néhányat megtalálsz ebben a táblázatban.
Hogyan lehet egy számról megállapítani, hogy prím-e?
A fenti gigantikus méretű számoknál bizony nagyon nehéz. De ezeknél jóval kisebb számoknál sem egyszerű. A második Fermat tétel néha segít ennek eldöntésében.
A második, vagy kis-Fermat tétel a következőt mondja ki: Ha p prímszám, a pedig egy olyan tetszőleges egész szám, amely nem osztható p-vel, akkor az ap-1-t p-vel osztva 1-t ad maradékul.
Például 210=1024. Ha az 1024-et elosztjuk 10+1=11-el, akkor a maradék 1 lesz. A 11 pedig tényleg prím. Ha viszont a 211=2048-al tesszük ugyanezt, azaz 2048-at elosztjuk 11+1=12-vel, akkor 8-at kapunk maradékul, nem 1-et, de hát a 12 nem is prím.
Ezek egyszerű példák, de az ap-1-nek p-vel való osztási maradékának a meghatározása viszonylag hatékony, ezért ez egy elég jó eljárás egy szám összetettségének megállapítására.
Comments are closed, but trackbacks and pingbacks are open.