Prímszámok

A Wikipédiából, a szabad lexikonból.

A matematika területén prímszámnak, törzsszámnak vagy röviden prímnek nevezzük azokat a természetes számokat, amelynek pontosan két osztójuk van (maga a szám és 1). A többi természetes számot összetett számnak nevezzük. Magát az 1-et egyik kategóriába sem soroljuk bele (csak egy osztója van).
Tágabb értelemben, ha az egész számok gyűrűjében vizsgálódunk, prímszámnak azokat a 0-tól és 1-től különböző abszolútértékű számokat nevezzük, melyeknek csak pontosan két pozitív osztójuk van.

A prímszámok megkülönböztetését az indokolja, hogy két osztója minden 1-nél nagyobb természetes számnak van, az 1 és önmaga, ezek egy természetes szám triviális osztói.

A legelső (legkisebb) pozitív prímszámok a következők:

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

A gyűrűelméletben, az absztrakt algebra egyik ágában a "prímelemnek" külön jelentése van, és ebben az értelemben a prímszám additív inverze (ellentettje) is prímszám. Más szavakkal, ha az egész számokat gyűrűnek tekintjük, akkor a −7 prímelem.

Tartalomjegyzék

1 A matematikai definíció
2 A számok felírása prímek szorzataként
3 Hány prímszám van?
4 Prímszámok keresése
5 A prímszámok néhány tulajdonsága
6 Megoldatlan problémák
7 A legnagyobb ismert prím
8 Alkalmazás
9 Prímszámképletek
10 Prímtesztek
11 A prímek közötti hézagok nagysága, a prímek sűrűsége
12 Csebisev részrehajlása
13 Lásd még
14 Külső hivatkozások

[szerkesztés] A matematikai definíció

A természetes számok körében a prímfogalomnak több egymással ekvivalens definíciója is létezik (lásd később). Ezen megfogalmazások közül prímtulajdonságnak nevezzük a következőt:

Definíció - Azt mondjuk, hogy egy p egynél nagyobb természetes szám prímszám, ha minden olyan esetben amikor p két természetes szám szorzatának osztója, akkor p a szorzat legalább egyik tényezőjének is osztója. Azaz tetszőleges a illetve b természetes számra:

$p\mid a\!\cdot\!b \; \Rightarrow \; ( p \mid a \; \vee\; p\mid b )$

Ugyanennek a tulajdonságnak egy másik fontos megfogalmazása a felbonthatatlan tulajdonság:

Definíció - Azt mondjuk, hogy egy f egynél nagyobb természetes szám felbonthatatlan, ha minden olyan esetben, amikor előáll két természetes szám szorzataként, a szorzatnak legalább az egyik tényezője 1, azaz tetszőleges a illetve b természetes számra:

$f = a\!\cdot\!b \; \Rightarrow \; ( a = 1\; \vee\; b = 1 )$

Azokat az egynél nagyobb természetes számokat, melyek nem felbonthatatlanok, összetett számoknak nevezzük.

A természetes számoknak ezeken kívül még fontos oszthatósági jellemzője, hogy hány osztójuk van. Mivel minden a természetes számra

$a\cdot 1 = 1 \cdot a = a$

ezért egy természes számnak az 1 és saját maga mindenképpen osztója. Ez azt jelenti, hogy ha a nagyobb mint 1, akkor a-nak legalább két osztója biztosan van, éspedig 1 és a, ezért ezeket az a triviális osztóinak nevezzük. Speciális eset még az 1, melynek egyetlen természetes szám az osztója (önmaga), és a 0, melynek az

$a\cdot 0 = 0 \cdot a = 0$

tulajdonság miatt minden szám osztója. Így a természetes számoknak az osztók száma szempontjából négy kategóriája van:

szám	pozitív osztóinak száma
0	$\infty$
1	1
felbonthatatlanok	2
összetett számok	>2

Állítás - Az természetes számok körében a következő három kijelentés egymással egyenértékű:

1) a p egynél nagyobb természetes szám prím

2) a p egynél nagyobb természetes szám felbonthatatlan

3) a p egynél nagyobb természtes szám pozitív osztóinak száma kettő.

[szerkesztés] A számok felírása prímek szorzataként

A számelmélet alaptétele szerint minden összetett szám felírható prímszámok szorzataként (kanonikus alak), és a felírás a sorrendtől eltekintve egyértelmű. Ezt a műveletet törzstényezős felbontásnak nevezzük. Példa:

$23244 = 2^2 \cdot 3 \cdot 13 \cdot 149$

Egy adott szám ilyen formájú felbontásai csak a tényezők sorrendjében különböznek.

Ez a tétel az egyik oka annak, hogy az 1-et kihagyjuk a prímszámok halmazából. Ha az 1-et prímszámnak vennénk, a tételhez további megkötéseket kellene adnunk.

Bizonyítás: Minden 1-nél nagyobb pozitív számnak van prímosztója.

Ezt indirekt bizonyítással látjuk be; feltesszük, hogy van legalább egy olyan egynél nagyobb szám, aminek nincs prímosztója. Ekkor, mivel a prímosztó nélküli, egynél nagyobb pozitív egészek halmaza nem üres, a jólrendezési tulajdonság miatt lesz egy legkisebb eleme, amit nevezzünk n-nek. Mivel n-nek nincsenek prímosztói, de osztja saját magát, n nem lehet prímszám. Így tehát létezik egy 1-től és önmagától különböző osztója; legyen a; eszerint n felírható n=ab alakban, ahol 1<a<n és 1<b<n. Mivel a<n, lennie kell prímosztójának. Viszont a bármely osztója osztója n-nek is, így n-nek van prímosztója. Ellentmondásra jutottunk, ami csak úgy oldható fel, ha az eredeti állítás igaz, azaz minden egynél nagyobb pozitív egész számnak van prímosztója.

[szerkesztés] Hány prímszám van?

Végtelen sok prímszám van. Ennek az állításnak a legrégibb bizonyítását Euklidész adta meg Elemek című munkájában. Euklidész állítása a következő: "a prímszámok darabszáma nagyobb bármely adott (véges) számnál", a bizonyítása pedig a következő:

Tegyük fel, hogy a prímszámok darabszáma véges. Legyen ez a szám m. Szorozzuk össze mind az m darab prímet, majd adjunk hozzá egyet. A kapott szám egyik prímmel sem osztható a halmazunkból, hiszen bármelyikkel osztva egyes maradékot kapunk, az egy pedig egyik prímmel sem osztható. A szorzat tehát vagy maga is prím, vagy osztható egy olyan számmal, ami nincs benne a fenti véges halmazban. (Ez azért igaz mindig, mert minden 1-nél nagyobb egésznek van prímosztója. A bizonyítást lásd fentebb.) Mindkét esetben legalább m+1 darab prímszám létezik. A fenti érvelés viszont nem függ m értékétől, így (m+1)-re is ugyanígy felírható. Így tehát a prímszámok darabszáma nagyobb bármely adott véges számnál.

[szerkesztés] Prímszámok keresése

eratosztenészi szita

[szerkesztés] A prímszámok néhány tulajdonsága

kis Fermat-tétel, Wilson-tétel, Dirichlet-tétel, primitív gyök

[szerkesztés] Megoldatlan problémák

ikerprím-sejtés
végtelen sok n²+1 alakú prím van
szomszédos négyzetszámok között mindig van prím
végtelen sok Mersenne-prím van
a Fermat-prímekre vonatkozó sejtés: nincs $2^{2^n}+1$ alakú prím n≥5-re.

[szerkesztés] A legnagyobb ismert prím

$232582657 - 1$ (2006. szeptember 6.)

[szerkesztés] Alkalmazás

Rendkívül nagy prímszámokat (amelyek nagyobbak mint 10¹⁰⁰) használnak számos nyíltkulcsos titkosítás algoritmusában. A prímeket használják még hasítótáblákhoz (hash table) és álvéletlenszám generátorokhoz.

[szerkesztés] Prímszámképletek

Vannak ám! Egyelőre lásd Laczkovich Miklós erről írott cikkét a KöMalban.

[szerkesztés] Prímtesztek

Főcikk: prímteszt

[szerkesztés] A prímek közötti hézagok nagysága, a prímek sűrűsége

prímszámtétel

[szerkesztés] Csebisev részrehajlása

[szerkesztés] Lásd még

Prímelem
Felbonthatatlan
A számelmélet alaptétele
Relatív prímek

[szerkesztés] Külső hivatkozások

The prime pages
MacTutor history of prime numbers – a prímek története
The "PRIMES is in P" FAQ – a prímteszt polinomiális bonyolultságáról
Prímek 10 000-ig
A Prím fejtörők Angol nyelvű, prímekkel kapcsolatos probléma és megoldás összefoglaló
A Prím Projekt minden egyes megtekintéskor újabb prímszámot készít, a lista fordított nagyságrendben van. (angol nyelvű lap)
Prímek aWIMS-től: online prímszám generátor. (angol nyelvű lap)
Laczkovich Miklós cikke a KöMalban a prímszámképletekről
Prímszorzatok. A prímek sorozatának különböző racionális függvényeinek viselkedése.

A lap eredeti címe "http://hu.wikipedia.org../../../p/r/%C3%AD/Pr%C3%ADmsz%C3%A1mok.html"

Kategória: Számelmélet

We provide Linux to the World