Prímszámokról további ismeretek

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ím a 2.
Mivel a prímszámok száma végtelen, ezért legnagyobbról nem beszélhetünk.
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:

A felfedezett prímszám a 2 a 77 millió 232 ezer 917-ik hatványon mínusz egy – számoltak be az eredményről a Mersenne-prímszámokat kutató Great Internet Mersenne Prime Search (GIMPS) nevű amerikai projekt munkatársai.

https://24.hu/tudomany/2018/01/05/megtalaltak-az-eddigi-legnagyobb-primszamot/

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.

Print Friendly, PDF & Email

Comments are closed, but trackbacks and pingbacks are open.