Kezdőlap


Cím:	Százezer dolláros prímek
Szerző(k):	Freud Róbert
Füzet:	2004/február, 72 - 77. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Amint a KöMaL 2004/1. száma is hírül adta, a fenti összeget az Electronic Frontier Foundation (EFF) annak fizeti ki, aki először állít elő legalább tízmillió jegyű prímszámot. A jelenlegi rekord a $6 320 430$ jegyű $2^{20 996 011} - 1$ , amelyet a Great Internet Mersenne Prime Search (GIMPS) projekt keretében találtak 2003. november 17-én. Ebbe a programba bárki bekapcsolódhat, a részleteket lásd a www.mersenne.org honlapon.

Már Euklidész is tudta

Mersenne-prímeknek a

2^{k} - 1

alakú prímeket nevezzük. A névadó Marin Mersenne a 17. század jelentős francia ,,tudományszervezője'', Fermat, Descartes és más vezető tudósok intenzív levelezőpartnere volt. Ezek a prímek azonban már a régi görögöknél is felbukkannak, a tökéletes számok keresésénél. A tökéletes számok azok, amelyek ,,a részeikből összeállnak'', azaz a valódi (= önmagukon kívüli) osztóik összege maga a szám. Ilyen a 6 vagy a 496. Euklidész Elemek c. könyvének IX.36 tétele így szól:

Ha az egységtől kezdve kétszeres arányban képezünk egy mértani sorozatot, amíg a sorösszeg prím nem lesz, és az összeggel megszorozzuk az utolsó tagot, akkor a szorzat tökéletes szám lesz.

Vagyis ha

1 + 2 + 2^{2} + ... + 2^{k - 1} = 2^{k} - 1

prím, akkor

2^{k - 1} (2^{k} - 1)

tökéletes szám. Pl.

k = 2

-re a 6-ot,

k = 5

-re a 496-ot kapjuk.
A bizonyításhoz (és ez volt lényegében Euklidész bizonyítása is) összegezni kell az

n = 2^{k - 1} (2^{k} - 1)

szám osztóit, ahol

q = 2^{k} - 1

prímszám:

\begin{matrix} 1 + 2 + 4 + ... + 2^{k - 1} + q + 2 q + ... + 2^{k - 2} q = 2^{k} - 1 + q (2^{k - 1} - 1) = q 2^{k - 1} = n . \end{matrix}

Euklidész képlete csupa páros tökéletes számot ad. Ma is megoldatlan probléma, hogy létezik-e egyáltalán páratlan tökéletes szám (az valószínűsíthető, hogy nem). Viszont Euklidész algoritmusával az összes páros tökéletes számot megkapjuk, amint ezt mintegy 2000 évvel később Euler bebizonyította. Ez azt jelenti, hogy kölcsönösen egyértelmű megfeleltetés áll fenn a páros tökéletes számok és a

2^{k} - 1

alakú prímek között. Sajnos ma sem tudjuk, hogy az ilyen prímek száma véges vagy végtelen (általában az utóbbira tippelnek). Erdős Pál megfogalmazásában ,,ez a kérdés talán a legnehezebb, ha nem is a legsürgősebb probléma, amivel az emberiség szemben áll.''

A rejtélyes lista

Mersenne is a tökéletes számok kapcsán foglalkozott a fenti alakú prímekkel. 1644-ben előállt híressé vált listájával, miszerint

2^{k} - 1

prím, ha

k = 2,3,5,7,13,17,19,31,67,127

és 257, de minden más 257-nél kisebb

k

esetén összetett.
A listát szemügyre véve azonnal feltűnik, hogy csak prím kitevők fordulnak elő. Ez nem véletlen, ugyanis ha

k

összetett, azaz

k = u v

, ahol

u, v > 1

, akkor az

a^{n} - b^{n} = (a - b) (a^{n - 1} + a^{n - 2} b + ... + b^{n - 1})

azonosság alapján

2^{k} - 1 = {(2^{u})}^{v} - 1^{v}

osztható

2^{u} - 1

-gyel, tehát

2^{k} - 1

is összetett.
Az is világos, hogy kis

k

értékekre könnyen ellenőrizhető, hogy

2^{k} - 1

prím vagy összetett, de akár már

2^{31} - 1

prím voltának igazolása is igen kemény számolást jelent, ha azt a ,,próbaosztásos'' módszerrel végezzük, azaz végigszámoljuk, hogy nem osztható a négyzetgyökéig terjedő (1-nél nagyobb) egészek egyikével sem (illetve elég ezt csak a prímekre ellenőrizni, azonban ekkor az adott határig terjedő prímek ismeretére is szükség van). Maga Mersenne írja, hogy ,,ahhoz, hogy egy 15- vagy 20-jegyű számról megállapítsuk, prím-e vagy sem, egy egész élet ideje sem elég.'' Ezek után igazán meglepő, hogy (máig sem tisztázott meggondolások alapján) elő mert állni egy ilyen listával, és még meglepőbb, hogy amint közel 300(!) évvel később végleg tisztázódott, a lista mindössze öt hibát tartalmaz:

2^{67} - 1

és

2^{257} - 1

valójában összetett számok, ugyanakkor a hiányzó

2^{61} - 1

2^{89} - 1

és

2^{107} - 1

prímek.

Rend a lelke mindennek

Természetesen Mersenne ismerhetett néhány olyan tételt, amelyek megkönnyítik egy

M_{p} = 2^{p} - 1

alakú szám prímosztóinak a keresését, ahol

p

prím (az ilyen számokat nevezzük a továbbiakban Mersenne-számoknak). Az egyik ilyen tétel szerint (

p > 2

-re)

M_{p}

minden prímosztója

2 k p + 1

, valamint egyben

8 j \pm 1

alakú. Így például

M_{43} = 2^{43} - 1

prímosztói egyszerre

86 k + 1

és

8 j \pm 1

alakúak, és a legkisebb ilyen prím, a 431 osztója is

M_{43}

-nak. Hasonlóan,

M_{31}

prím voltához elég csak azt ellenőrizni, hogy nem osztható a négyzetgyökénél kisebb

248 t + 1

és

248 t + 63

alakú prímek egyikével sem. Mindez esetleg magyarázatot adhat arra, hogy miért szerepel a listán a 31 kitevő, és miért nincs ott a 43 (de továbbra sem adhat támpontot a lista túlnyomó részének a megtippeléséhez).
Az alábbiakban bebizonyítjuk, hogy

M_{p}

minden prímosztója

2 k p + 1

alakú. Ebben a rend fogalma lesz a segítségünkre.
Legyenek

c

és

m

relatív prímek, és vizsgáljuk meg, hogy a

c

hatványai,

1 = c^{0}, c, c^{2}, c^{3}, ..., c^{n}, ...

milyen maradékot adnak

m

-mel osztva. Mivel a maradékok száma véges, ezért lesz olyan

0 \leq i < j

, amelyre

c^{j}

és

c^{i}

azonos maradékot adnak, azaz

c^{j} - c^{i} = c^{i} (c^{j - i} - 1)

osztható

m

-mel. Ebből

(c; m) = 1

alapján következik, hogy

c^{j - i} - 1

is osztható

m

-mel, azaz

c^{j - i}

maradéka 1. Legyen

r

a legkisebb pozitív egész, amelyre

c^{r}

maradéka 1. Ekkor

1 = c^{0}, c, c^{2}, c^{3}, ..., c^{n}, ...

maradékai periodikus sorozatot alkotnak, amelyben a (legkisebb) periódus hossza éppen

r

. Ezt az

r

számot nevezzük a

c

szám rendjének modulo

m

, és

o_{m} (c)

-vel jelöljük és ordo

m

c

-nek ejtjük.
Fel fogjuk még használni a kis Fermat-tételt, amely szerint a

q

prímmel osztva

c^{q - 1}

maradéka 1, feltéve hogy

c

nem osztható

q

-val. Az előző bekezdés szerint így a

c

rendje osztója

(q - 1)

-nek, azaz

o_{q} (c) ∣ q - 1

.
Legyen most

q

M_{p} = 2^{p} - 1

Mersenne-szám egy prímosztója, ahol

p > 2

prím. Ekkor

2^{p}

maradéka

q

-val osztva 1. Ez azt jelenti, hogy

o_{q} (2) ∣ p

. Mivel a

p

prím, és

2^{1}

maradéka nem 1, ezért

o_{q} (2)

csak

p

lehet. Ebből az előző bekezdés alapján következik, hogy

p ∣ q - 1

, továbbá

q - 1

páros, ezért valóban

q = 2 k p + 1

alakú.
A rend fogalmát és az iménti bizonyítást kényelmesebben megfogalmazhatjuk a kongruenciák segítségével. Itt

a \equiv b (mod m)

azt jelenti, hogy

a

és

b

azonos maradékot adnak

m

-mel osztva, azaz

m ∣ a - b

. A

c

rendje

mod m

a legkisebb olyan

r

pozitív egész, amelyre

c^{r} \equiv 1 (mod m)

. A kis Fermat-tétel szerint

\begin{matrix} c^{q - 1} \equiv 1 (mod q), \end{matrix}

q

prím és

c

nem osztható

q

-val, illetve

c^{q} \equiv c (mod q)

bármely

c

esetén. A rendnek az említett periódushossz tulajdonsága azt fejezi ki, hogy

\begin{matrix} c^{i} \equiv c^{j} (mod m) \Leftrightarrow i \equiv j (mod o_{m} (c)) . \end{matrix}

Azt, hogy

M_{p}

prímosztói egyben

8 j \pm 1

alakúak is, a másodfokú kongruenciák elméletével, az ún. Legendre-szimbólum segítségével lehet igazolni, lásd pl. a Freud ‐ Gyarmati: Számelmélet c. egyetemi tankönyvben.

Az örökifjú teszt

Mersenne listájának helyességén az első rést 1876-ban ütötte Edouard Lucas egy egészen új eljárás segítségével, és lényegében ugyanezen az alapon keresi ma is a GIMPS több mint

200 000

számítógépből összekapcsolt hálózata az újabb és újabb Mersenne-prímeket. Ez a teszt az

a_{1} = 4

a_{n + 1} = a_{n}^{2} - 2

rekurzió alapján működik: Egy

p > 2

prímet véve

M_{p} = 2^{p} - 1

pontosan akkor prím, ha

M_{p} ∣ a_{p - 1}

.
Például

p = 7

-re

a_{1} = 4

a_{2} = 14

a_{3} = 194 \equiv - 60 (mod 127)

a_{4} \equiv 3598 \equiv 42 (mod 127)

a_{5} \equiv 1762 \equiv - 16 (mod 127)

a_{6} \equiv 254 \equiv 0 (mod 127)

, tehát

M_{7} = 127

prímszám.
A fenti példa természetesen csak illusztrációs jellegű, a módszer hatékonysága a nagyobb kitevők esetén érvényesül. Lucas ezzel bizonyította be 1876-ban, hogy

M_{67}

összetett, anélkül, hogy egy osztóját elő tudta volna állítani.

M_{67}

-et tényezőkre bontani csak jó negyedszázaddal később sikerült Cole-nak. Lucas azt is igazolta, hogy

M_{127}

valóban prím, és ez maradt a legnagyobb ismert prímszám a számítógépek megjelenéséig.
Amint az illusztrációs példából is kiderült, nem kell magukat az

a_{i}

számokat kiszámítani, elég mindig az

M_{p}

-vel való osztási maradékukat tekinteni. Az

M_{p}

-vel való maradékos osztás különösen egyszerűen hajtható végre a számítógépeken, ugyanis

M_{p}

kettes számrendszerbeli alakja csupa 1-esből áll. Így hasonló a helyzet ahhoz, mintha tízes számrendszerben mondjuk a

21 357 246

szám 999-cel való osztási maradékát keresnénk: mivel

10^{3}

és így

10^{3 k}

maradéka mindig 1, ezért

21 357 246 = 21 \cdot 10^{6} + 357 \cdot 10^{3} + 246 \equiv 21 + 357 + 246 \equiv 624 (mod 999)

, azaz a maradékot számjegycsoportok egyszerű eltolásával kaphatjuk meg.

Kiruccanás más számkörbe

A teszt elégségességi részét igazoljuk az alábbiakban: Ha

\begin{matrix} M_{p} ∣ a_{p - 1}, \end{matrix}

(1)

akkor

M_{p}

prím.
(A szükségesség igazolása hasonló eszközökkel történik, és alkalmazni kell a már említett Legendre-szimbólumot is.)
A bizonyításhoz az

a + b \sqrt[]{3}

(

a

b

egész) alakú számok körében az egészek mintájára bevezetett oszthatóság, kongruencia és rendfogalom elemi tulajdonságait használjuk fel (ezek itt is ugyanúgy érvényesek, mint az egész számoknál).
Teljes indukcióval könnyen adódik, hogy

a_{k} = {(2 + \sqrt[]{3})}^{2^{k - 1}} + {(2 - \sqrt[]{3})}^{2^{k - 1}}

. Ennek alapján az (1) feltétel ekvivalens az

\begin{matrix} M_{p} | {(2 + \sqrt[]{3})}^{2^{p - 2}} + {(2 - \sqrt[]{3})}^{2^{p - 2}} \end{matrix}

oszthatósággal. A jobb oldalt

{(2 + \sqrt[]{3})}^{2^{p - 2}}

-vel szorozva

(2 - \sqrt[]{3}) (2 + \sqrt[]{3}) = 1

miatt

\begin{matrix} M_{p} | {(2 + \sqrt[]{3})}^{2^{p - 1}} + 1, azaz {(2 + \sqrt[]{3})}^{2^{p - 1}} \equiv - 1 (mod M_{p}) \end{matrix}

(2)

adódik.

M_{p}

prím voltát (2)-ből fogjuk levezetni.
Szükségünk lesz a következő lemmára:
Ha

q > 3

tetszőleges prímszám, akkor

\begin{matrix} {(a + b \sqrt[]{3})}^{q} \equiv a + b \sqrt[]{3} vagy a - b \sqrt[]{3} (mod q) . \end{matrix}

(3)

A lemma bizonyítása: A binomiális tétel alapján

\begin{matrix} {(a + b \sqrt[]{3})}^{q} = a^{q} + (\binom{q}{1}) a^{q - 1} b \sqrt[]{3} + (\binom{q}{2}) a^{q - 2} 3 b^{2} + ... + b^{q} 3^{\frac{q - 1}{2}} \sqrt[]{3} . \end{matrix}

(4)

A kis Fermat-tétel szerint

a^{q} \equiv a (mod q)

és

b^{q} \equiv b (mod q)

, továbbá

q

prím volta miatt

(\binom{q}{1}), (\binom{q}{2}), ..., (\binom{q}{q - 1})

mindegyike osztható

q

-val. Végül ismét a kis Fermat-tétel alapján

\begin{matrix} q | {(3^{\frac{q - 1}{2}})}^{2} - 1 = (3^{\frac{q - 1}{2}} - 1) (3^{\frac{q - 1}{2}} + 1), \end{matrix}

és mivel

q

prím, szükségképpen osztja az egyik tényezőt, azaz

3^{\frac{q - 1}{2}} \equiv \pm 1 (mod q)

. Ezeket (4)-be beírva éppen (3), azaz a lemma állítása adódik.
Visszatérve a tételünk bizonyítására, tegyük fel, hogy (2) fennáll, és legyen

q

M_{p}

egy prímosztója (itt nyilván

q > 3

); azt kell igazolnunk, hogy

q = M_{p}

. Ekkor a (2)-beli kongruencia

mod q

is teljesül, azaz

\begin{matrix} {(2 + \sqrt[]{3})}^{2^{p - 1}} \equiv - 1 (mod q) . \end{matrix}

(5)

Ezt négyzetre emelve kapjuk, hogy

\begin{matrix} {(2 + \sqrt[]{3})}^{2^{p}} \equiv 1 (mod q) . \end{matrix}

(6)

(5)-ből és (6)-ból a rend tulajdonságai szerint következik, hogy

o_{q} (2 + \sqrt[]{3}) | 2^{p}

, de

o_{q} (2 + \sqrt[]{3}) ∤ 2^{p - 1}

, azaz

o_{q} (2 + \sqrt[]{3}) = 2^{p}

.
Másrészt (3) alapján

{(2 + \sqrt[]{3})}^{q} \equiv 2 \pm \sqrt[]{3} (mod q)

. Ha itt a

+

előjel érvényes, akkor

\begin{matrix} {(2 + \sqrt[]{3})}^{q - 1} = (2 - \sqrt[]{3}) {(2 + \sqrt[]{3})}^{q} \equiv (2 - \sqrt[]{3}) (2 + \sqrt[]{3}) = 1 (mod q), \end{matrix}

és így

o_{q} (2 + \sqrt[]{3}) = 2^{p} \leq q - 1

, ami

q \leq M_{p} = 2^{p} - 1

miatt lehetetlen.
Ha a

-

előjel érvényes, akkor hasonlóan adódik, hogy

\begin{matrix} {(2 + \sqrt[]{3})}^{q + 1} \equiv 1 (mod q), \end{matrix}

tehát

o_{q} (2 + \sqrt[]{3}) = 2^{p} \leq q + 1

, ahonnan

q \leq M_{p} = 2^{p} - 1

miatt kapjuk, hogy

q = M_{p}

, vagyis

M_{p}

prím.

Ki lesz a befutó?

Az EFF százezer dollárját jó eséllyel egy Mersenne-prímmel lehet majd megszerezni, bár egyre erősebb a konkurencia. A legnagyobb ismert prímek listáját 2004. január 17-én három Mersenne-prím vezeti, de a negyedik helyen a 2003. decemberében(!) talált

5359 \cdot 2^{5 054 502} + 1

áll (a maga több mint másfél millió számjegyével). Az ilyen

r \cdot 2^{k} + 1

alakú számok prím volta kis szerencsével szintén elég gyorsan kimutatható, ha

r

viszonylag kis páratlan szám. Emellett az ilyen típusú prímek valószínűleg sokkal sűrűbben fordulnak elő, mint a Mersenne-prímek, tehát nem kizárt, hogy előbb bukkannak ezek közül egy legalább tízmillió jegyűre, mint Mersenne-prímre. Ugyanakkor a Mersenne-prímek gyönyörűen kapcsolják össze több mint kétezer év matematikáját, elegendő munkát hagyva a következő kétezer évre is, és az igazi befutók talán azok lesznek, akik az eddigiekhez elméletileg is hozzá tudnak majd tenni egy keveset.