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ű 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 http://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^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:

1+2+4+...+2^k-1+q+2q+...+2^k-2q=2^k-1+q(2^k-1-1)=q2^k-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 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=uv, ahol u,v>1, akkor az aⁿ-bⁿ= (a-b)(a^n-1+a^n-2b+...+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³¹-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⁶⁷-1 és 2²⁵⁷-1 valójában összetett számok, ugyanakkor a hiányzó 2⁶¹-1, 2⁸⁹-1 és 2¹⁰⁷-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 2kp+1, valamint egyben 8j\(\displaystyle \pm\)1 alakú. Így például M₄₃=2⁴³-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 M₄₃-nak. Hasonlóan, M₃₁ 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 M_p 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=c⁰,c,c²,c³,..., cⁿ,... 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 c^j és cⁱ azonos maradékot adnak, azaz c^j-cⁱ= cⁱ(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⁰, c, c², c³, ..., cⁿ, ... 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 az 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¹ 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=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 c^r\(\displaystyle \equiv\)1 (mod m). A kis Fermat-tétel szerint

c^q-1\(\displaystyle \equiv\)1 (mod q),

ha q prím és c nem osztható q-val, illetve c^q\(\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 M_p 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 a₁=4, a_n+1=a_n²-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₁=4, a₂=14, a₃=194\(\displaystyle \equiv\)-60 (mod 127), a₄\(\displaystyle \equiv\)3598\(\displaystyle \equiv\)42 (mod 127), a₅\(\displaystyle \equiv\)1762\(\displaystyle \equiv\)-16 (mod 127), a₆\(\displaystyle \equiv\)254\(\displaystyle \equiv\)0 (mod 127), tehát M₇=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₆₇ összetett, anélkül, hogy egy osztóját elő tudta volna állítani. M₆₇-et tényezőkre bontani csak jó negyedszázaddal később sikerült Cole-nak. Lucas azt is igazolta, hogy M₁₂₇ 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³ és így 10^3k maradéka mindig 1, ezért 21 357 246= 21^.10⁶+ 357^.10³+ 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

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 \(\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

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

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

A kis Fermat-tétel szerint a^q\(\displaystyle \equiv\)a (mod q) és b^q\(\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 M_p egy prímosztója (itt nyilván q>3); azt kell igazolnunk, hogy q=M_p. Ekkor a (2)-beli kongruencia \(\displaystyle \bmod~q\) is teljesül, azaz

Ezt négyzetre emelve kapjuk, hogy

(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\)M_p=2^p-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\)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^.2^5 054 502+1 áll (a maga több mint másfél millió számjegyével). Az ilyen r^.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.

Freud Róbert