Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Százezer dolláros prímek

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ű 220 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 http://www.mersenne.org honlapon.

Már Euklidész is tudta

Mersenne-prímeknek a 2k-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+22+...+2k-1=2k-1 prím, akkor 2k-1(2k-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=2k-1(2k-1) szám osztóit, ahol q=2k-1 prímszám:

1+2+4+...+2k-1+q+2q+...+2k-2q=2k-1+q(2k-1-1)=q2k-1=n.

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 2k-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 2k-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=uv, ahol u,v>1, akkor az an-bn= (a-b)(an-1+an-2b+...+bn-1) azonosság alapján 2k-1= (2u)v-1v osztható 2u-1-gyel, tehát 2k-1 is összetett.

Az is világos, hogy kis k értékekre könnyen ellenőrizhető, hogy 2k-1 prím vagy összetett, de akár már 231-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: 267-1 és 2257-1 valójában összetett számok, ugyanakkor a hiányzó 261-1, 289-1 és 2107-1 prímek.

Rend a lelke mindennek

Természetesen Mersenne ismerhetett néhány olyan tételt, amelyek megkönnyítik egy Mp=2p-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) Mp minden prímosztója 2kp+1, valamint egyben 8j\(\displaystyle \pm\)1 alakú. Így például M43=243-1 prímosztói egyszerre 86k+1 és 8j\(\displaystyle \pm\)1 alakúak, és a legkisebb ilyen prím, a 431 osztója is M43-nak. Hasonlóan, M31 prím voltához elég csak azt ellenőrizni, hogy nem osztható a négyzetgyökénél kisebb 248t+1 és 248t+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 Mp minden prímosztója 2kp+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=c0,c,c2,c3,..., cn,... milyen maradékot adnak m-mel osztva. Mivel a maradékok száma véges, ezért lesz olyan 0\(\displaystyle \le\)i<j, amelyre cj és ci azonos maradékot adnak, azaz cj-ci= ci(cj-i-1) osztható m-mel. Ebből (c;m)=1 alapján következik, hogy cj-i-1 is osztható m-mel, azaz cj-i maradéka 1. Legyen r a legkisebb pozitív egész, amelyre cr maradéka 1. Ekkor 1=c0, c, c2, c3, ..., cn, ... 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 om(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 cq-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 oq(c)| q-1.

Legyen most q az Mp=2p-1 Mersenne-szám egy prímosztója, ahol p>2 prím. Ekkor 2p maradéka q-val osztva 1. Ez azt jelenti, hogy oq(2)| p. Mivel a p prím, és 21 maradéka nem 1, ezért oq(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=2kp+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\(\displaystyle \equiv\)b (mod m) azt jelenti, hogy a és b azonos maradékot adnak m-mel osztva, azaz m| a-b. A c rendje \(\displaystyle \bmod~m\) a legkisebb olyan r pozitív egész, amelyre cr\(\displaystyle \equiv\)1 (mod m). A kis Fermat-tétel szerint

cq-1\(\displaystyle \equiv\)1 (mod q),

ha q prím és c nem osztható q-val, illetve cq\(\displaystyle \equiv\)c (mod q) bármely c esetén. A rendnek az említett periódushossz tulajdonsága azt fejezi ki, hogy

\(\displaystyle c^i\equiv c^j\pmod m\iff i\equiv j\pmod{o_m(c)}. \)

Azt, hogy Mp prímosztói egyben 8j\(\displaystyle \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 a1=4, an+1=an2-2 rekurzió alapján működik: Egy p>2 prímet véve Mp=2p-1 pontosan akkor prím, ha Mp| ap-1.

Például p=7-re a1=4, a2=14, a3=194\(\displaystyle \equiv\)-60 (mod 127), a4\(\displaystyle \equiv\)3598\(\displaystyle \equiv\)42 (mod 127), a5\(\displaystyle \equiv\)1762\(\displaystyle \equiv\)-16 (mod 127), a6\(\displaystyle \equiv\)254\(\displaystyle \equiv\)0 (mod 127), tehát M7=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 M67 összetett, anélkül, hogy egy osztóját elő tudta volna állítani. M67-et tényezőkre bontani csak jó negyedszázaddal később sikerült Cole-nak. Lucas azt is igazolta, hogy M127 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 ai számokat kiszámítani, elég mindig az Mp-vel való osztási maradékukat tekinteni. Az Mp-vel való maradékos osztás különösen egyszerűen hajtható végre a számítógépeken, ugyanis Mp 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 103 és így 103k maradéka mindig 1, ezért 21 357 246= 21.106+ 357.103+ 246\(\displaystyle \equiv\)21+ 357+ 246\(\displaystyle \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

(1)Mp| ap-1,

akkor Mp 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 \(\displaystyle a+b\sqrt3\) (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 \(\displaystyle a_k=\big(2+\sqrt{3}\,\big)^{2^{k-1}}+ \big(2-\sqrt{3}\,\big)^{2^{k-1}}\). Ennek alapján az (1) feltétel ekvivalens az

\(\displaystyle M_p\,\big|\,\big(2+\sqrt{3}\,\big)^{2^{p-2}}+\big(2-\sqrt{3}\,\big)^{2^{p-2}} \)

oszthatósággal. A jobb oldalt \(\displaystyle \big(2+\sqrt{3}\,\big)^{2^{p-2}}\)-vel szorozva \(\displaystyle \big(2-\sqrt{3}\,\big)\big(2+\sqrt{3}\,\big)=1\) miatt

(2)\(\displaystyle M_p\,\big|\,\big(2+\sqrt{3}\,\big)^{2^{p-1}}+1,\quad{\rm azaz}\quad\big(2+\sqrt{3}\,\big)^{2^{p-1}}\equiv-1\pmod{M_p} \)

adódik. Mp 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

(3)\(\displaystyle \big(a+b\sqrt{3}\,\big)^q\equiv a+b\sqrt3\quad{\rm vagy}\quad a-b\sqrt{3}\pmod{q}. \)

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

(4)\(\displaystyle \big(a+b\sqrt{3}\,\big)^q=a^q+\binom{q}{1}a^{q-1}b\sqrt3+ \binom{q}{2}a^{q-2}3b^2+\ldots+b^q3^{\tfrac{q-1}{2}}\sqrt3. \)

A kis Fermat-tétel szerint aq\(\displaystyle \equiv\)a (mod q) és bq\(\displaystyle \equiv\)b (mod q), továbbá q prím volta miatt \(\displaystyle \binom{q}{1},\binom{q}{2},\ldots,\binom{q}{q-1}\) mindegyike osztható q-val. Végül ismét a kis Fermat-tétel alapján

\(\displaystyle q\,\big|\,\Big(3^{\tfrac{q-1}{2}}\Big)^2-1= \Big(3^{\tfrac{q-1}{2}}-1\Big)\Big(3^{\tfrac{q-1}{2}}+1\Big), \)

és mivel q prím, szükségképpen osztja az egyik tényezőt, azaz \(\displaystyle 3^{\tfrac{q-1}{2}}\equiv\pm1\pmod 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 az Mp egy prímosztója (itt nyilván q>3); azt kell igazolnunk, hogy q=Mp. Ekkor a (2)-beli kongruencia \(\displaystyle \bmod~q\) is teljesül, azaz

(5)\(\displaystyle \big(2+\sqrt{3}\,\big)^{2^{p-1}}\equiv-1\pmod{q}. \)

Ezt négyzetre emelve kapjuk, hogy

(6)\(\displaystyle \big(2+\sqrt{3}\,\big)^{2^{p}}\equiv1\pmod{q}. \)

(5)-ből és (6)-ból a rend tulajdonságai szerint következik, hogy \(\displaystyle o_q\big(2+\sqrt{3}\,\big)\,\big|\,2^p\), de \(\displaystyle o_q\big(2+\sqrt{3}\,\big)\nmid2^{p-1}\), azaz \(\displaystyle o_q\big(2+\sqrt{3}\,\big)=2^p\).

Másrészt (3) alapján \(\displaystyle \big(2+\sqrt{3}\,\big)^q\equiv2\pm\sqrt3\pmod q\). Ha itt a + előjel érvényes, akkor

\(\displaystyle \big(2+\sqrt{3}\,\big)^{q-1}=\big(2-\sqrt{3}\,\big)\big(2+\sqrt{3}\,\big)^q\equiv\big(2-\sqrt{3}\,\big)\big(2+\sqrt{3}\,\big)=1\pmod{q}, \)

és így \(\displaystyle o_q\big(2+\sqrt{3}\,\big)=2^p\le q-1\), ami q\(\displaystyle \le\)Mp=2p-1 miatt lehetetlen.

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

\(\displaystyle \big(2+\sqrt{3}\,\big)^{q+1}\equiv1\pmod q, \)

tehát \(\displaystyle o_q\big(2+\sqrt{3}\,\big)=2^p\le q+1\), ahonnan q\(\displaystyle \le\)Mp=2p-1 miatt kapjuk, hogy q=Mp, vagyis Mp 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.25 054 502+1 áll (a maga több mint másfél millió számjegyével). Az ilyen r.2k+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.

Freud Róbert