Prímszámok

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

(Prímszám szócikkből átirányítva)

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 egynél nagyobb 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). Az általában természetes számnak tekintett 0 ugyancsak nem prím és nem is összetett (minden természetes szám osztója, de nem írható fel prímszámok szorzataként).
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 – de a prímszámoknak nincs is több, míg a többi 1-nél nagyobb számoknak (az összetett számoknak) van.

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, 127, 131, 137, 139, 149, 151.

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.

[szerkesztés] A matematikai definíció

A természetes számok körében (fontos, hogy csak ott, mert van olyan számkör, ahol a prím nem feltétlenül felbonthatatlan) 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 a szám 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.

Prímszámtáblázatok vizsgálatával, 15 éves korában Gauss vette észre, hogy az x-nél kisebb prímszámok π(x) száma az $x / log x$ , sőt az ennél sokkal pontosabb

$Li(x)=\int^x_0 \frac{dt}{\log t}$

mennyiséggel közelíthető. A prímszámtétel, vagyis az az állítás, hogy $\pi(x)\sim\frac{x}{\log x}$ csak a 19. század végén nyert igazolást. Hosszú ideig még az sem tűnt kizártnak, hogy minden x>2-re $L i (x) > π(x)$ teljesül. Ezt végül Littlewood cáfolta meg, 1914-ben. Noha igazolta a $π(x) - L i (x)$ különbség végtelen sok jelváltását, bizonyítása nem adott korlátot az $x 1$ első jelváltásra, csak jóval később, 1933-ban sikerült Skewes-nak az

$x_1<10^{10^{10^{10^{34}}}}$

becslést adnia. Ezt Bays és Haudson 1999-ben $x_1<1,3982\cdot 10^{316}$ -ra javította és meggyőző heurisztikus érveik vannak arra, hogy $x 1$ ténylegesen nem sokkal kisebb ennél.

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

Eratoszthenész szitája

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

Minden háromnál nagyobb prímszám felírható a következő alakban:6k +/- 1

A prímszámok tulajdonságaira vonatkozó tételek közül néhány a következő.

[szerkesztés] Fermat kis tétele

Bővebben: kis Fermat-tétel

E tétel azt állítja, hogy ha p prímszám, a tetszőleges szám, akkor $a p - a$ osztható p-vel. Ezzel ekvivalens formája az, hogy hogy ha p prímszám, a tetszőleges p-vel nem osztható szám, akkor $a p - 1 - 1$ osztható p-vel

[szerkesztés] Wilson tétele

Bővebben: Wilson-tétel

Eszerint, ha p prímszám, akkor $(p-1)!\equiv -1 \pmod{p}$ .

[szerkesztés] Wolstenholme tétele

E tétel azt mondja ki, hogy ha p>3 prímszám, akkor az

$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$

tört számlálója osztható $p 2$ -tel. Továbbá az

$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{(p-1)^2}$

tört számlálója osztható p-vel, és ezekből levezethető, hogy

${2p \choose p}\equiv 2 \pmod{p^3}.$

[szerkesztés] Bang tétele

Bang 1886-ban igazolt tétele szerint, ha n>1 és $n\neq 6$ , akkor $2 n - 1$ -nek van olyan prímosztója, ami nem osztja a $2^2-1,2^3-1,\dots,2^{n-1}-1$ számok egyikét sem. Ezt Karl Zsigmondy 1892-ben a következő állításra terjesztette ki: ha $a>b\geq 1$ és $(a, b) = 1$ , akkor minden $a n - b n$ alakú számnak van olyan prímosztója, ami semmilyen $a k - b k$ -nak nem osztója $k < n$ -re, kivéve, ha a=2, b=1, n=6 vagy a és b páratlanok, n=2 és a+b 2 hatványa.

[szerkesztés] Speciális alakú prímek

A számelmélet számos mély tétele, nevezetes problémája azzal foglalkozik, léteznek-e bizonyos alakú prímek.

A híres Dirichlet-tétel szerint, ha a és q relatív prím természetes számok, akkor végtelen sok $a + q x$ alakú prím van. Végtelen sok $x 2 + y 4$ alakú prím van (Friedlander-Iwaniec). Végtelen sok $x 3 + 2 y 3$ alakú prím van (Heath-Brown).

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 olyan polinomok, amelyek a változó sok egymásutáni értékére prímértéket adnak. A legismertebb az $x 2 - x + 41$ polinom, ami a $0\leq x \leq 40$ helyeken prímet ad. $x = 41$ -re ez már osztható 41-gyel, tehát összetett. Általában is igaz, hogy nincs olyan nemkonstans egyváltozós polinom, ami minden helyen prímet ad.

Olyan p prímszám, amire igaz, hogy az $x 2 - x + p$ polinom minden $0\leq x\leq p-1$ értékre prímet ad, csak véges sok van, ezek között a legnagyobb $p = 41$ .

Vannak olyan polinomszerű képletek is, amelyek a változó sok egymásutáni értékére prímszámot adnak. Így például

| x 4 - 97 x 3 + 3294 x 2 - 45458 x + 213589 |

prímszámot ad a $0\leq x \leq 49$ értékekre ^[1].

[szerkesztés] Prímtesztek

Bővebben: prímteszt

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

Bővebben: prímszámtétel

[szerkesztés] Csebisev tétele

Tétel: Bármely nullától különböző pozitív szám és a kétszerese közt van prímszám.

[szerkesztés] Lásd még

[szerkesztés] Hivatkozások

^ Al Zimmermann's Programming Contests

[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.
Geometry of prime numbers and perfect numbers

A lap eredeti címe: „http://hu.wikipedia.org/wiki/Pr%C3%ADmsz%C3%A1mok”

Kategóriák: Számelmélet | Nevezetes számsorozatok