i
i
“1458-Potocnik-0” — 2010/8/23 — 10:28 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 28 (2000/2001)
Številka 6
Strani 349–351
Primož Potočnik:
NAJVEČJA ZNANA PRAŠTEVILA – nekoč in da-
nes
Ključne besede: novice, zgodovina matematike, teorija števil, prašte-
vila, praštevilski dvojčki, GIMPS.
Elektronska verzija: http://www.presek.si/28/1458-Potocnik.pdf
c© 2001 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
INovice
NAJVEČJA ZNANA PRAŠTEVILA
NEKOČ IN DANES
Čeprav je defin icija praš t evila enost avna in vsakomur razumljiva, je pre-
sen etlj ivo veliko vprašanj v zvezi z njimi še vedno odprt ih . Celo tako
preprosta naloga, kot je ugotoviti , a li je dano naravno št evilo praštevilo ,
je lahko zelo trd oreh. Preprost in dobro znan postopek , Eratoste novo
rešeto1 , p ostane pri ugot avlj anju praštevilskosti velikih števil (z denimo
nekaj tisoč števkami) zelo zamude n in praktično neuporaben. Prav na
dejst vu , da je za velika števila težko preveriti, a li so praštevila ali ne, sloni
ena najrazširjenejših met od šifriranja sporočil (glej članek: M. Ven celj ,
Šifriranje z javnim ključem, Presek , letnik 22, št . 6 (1994-1995), stran
354- 357).
Že antični Grki so vedeli, da je praš t evil neskončno mnogo. Kljub
temu pa prav velikih praš t evi l niso poznali . Prvo praštevilo om embe
vredne velikosti lahko zasledimo pri it alijanskem matematiku Pietru Ca-
t ald iju" , ki je leta 1588 pr avilno pr everil , da st a št evili 217 - 1 = 131071
in 219 - 1 = 524287 praštevili . Ti dve šte vili sta zarad i svoje majh-
nosti ravno še primerni za up orabo Eratoste novega rešeta. Če želimo
namreč preveri ti , da je dano število n pr aš t evi lo, je dovolj preveriti , da
n ni deljivo z nobenim pr aštevilom, ki je manjše ali enako kvadratnemu
korenu iz šte vila n . Cataldiju pa so bi la vsa prašt evi la med 2 in kor enom
zgornj ih dveh št evil že znana. Opogumljen s svoj im rezultatom je Catald i
domneval , da so t ud i števila 2" - 1 za n = 23,2 9,31 in 37 prašt evila .
Da je bil a njegova do mneva napačna pri n = 23 in n = 37, je dobrih 50
let kasneje dokazal zname nit i matematik Fermat. Podobno se je go dilo
Cataldijevi domnevi pri n = 29. Pač pa je imel več sreče pri šte vilu
231 - 1 = 2147483647. Leta 1772 (torej še dobrih sto let za Fermatom ) je
Euler namreč s pr ecej spretnosti dokazal , da je to število res pr ašt evilo .
Prvo veliko prašt evilo, ki ni ob like 2" - 1 (praštevilom oblike 2" - 1
pravimo danes Mersennova pr ašt evi la - o njih bo govora v eni nas le-
dnjih št evilk Preseka), je leta 1867 našel Landry. Njegovo praštevilo je
v resni ci praštevil ski deli t elj št evi la 259 - 1 in znaša (259 - 1)/ 179951 =
= 3203431780337. Do prave revolu cije pri iskanju velikih prašt evi lje prišlo
1 E ratos ten (276- 194 pr. n . št .) . Roj en je bil v današnji Libiji , nekaj časa je deloval
v Ate nah , kas neje pa se je preselil v Aleksandrijo v Eg ipt u , kjer je bil med d ru gim
imenovan za vodjo znamenite a leksand rij ske knjižnjice . Tam je t ud i umrl.
2 Pi etro Catald i (1548- 1626) . Roj en je bi l v Bologni. Od 17. leta da lje je poučeval
matem atiko v različnih kr ajih It al ije, med drugim t udi na univerzi v Perugi. Leta 1584
se je vrnil v Bo logno, kje r je poučeval mate m at iko in astronomijo vse do svoje smrti.
Novice I
let a 1876 , ko je francoski matematik Eduard Lucas' odkril domiseln in
prep rost kr iterij , ki preverj anj e, katero šte vilo oblike 2" - 1 je praštevilo,
močno olaj ša . S svojo metod o je dokazal , da je 39-m estno število 2127 - 1
pr ašt evilo. Lucasov rezult at že predstavlja uvod v računalniško dobo
iskanj a velikih praš t evil.
Danes si iskanja velikih prašt evil brez pomoči računalnika ne moremo
zamislit i. Po zaslugi Lucasovega testa so računalniki posebej uspešn i pri
iskanju velikih Mersennovih praštevil. Tako je med desetimi največjimi,
do sedaj znanimi praštevili, kar sedem Merse nnovih. Največja št ir i so bila
odkrita s pomočjo velikega int ernetskega iskanj a Mersennovih praštevil
(GIMP S - Great Internet l'vIers en ne Prime Search) , v katerega se lahko
vključi vsakdo, ki ima dostop do interneta. O projektu GIMPS lahko
br alc i Preseka več izvejo na intern etskem naslovu www . mersenne. org, kaj
več o njem pa bo mo nap isali t ud i v P reseku , brž ko bomo v ur edništvu
zbrali nekaj vti sov sodelujočih.
Po leg iskanja veliki h praštevil je zelo zanimivo in te žko iskanj e t.i.
prašt evilskih dvojčkov . Pravimo , da prašt evili p in q tvorita praštevilski
dvoj ček , če se po absolutni vrednosti raz likuje ta za natanko 2. Tako
so praštevilski dvoj č ki: (3,5), (5, 7) , (11, 13) , (17, 19) , it d. Tako kot za
Mersennova praštevila t ud i za praštevilske dvoj čke še vedno ni znano, ali
j ih je neskončno mnogo ali ne. To vprašanje sodi med najznamenitejše in
najst arejše odprte probleme s področj a t eorije števil.
Za konec si oglej mo še tabeli šestih največjih , do sed aj znanih, pra-
šte vil in praštevilskih dvojčkov .
prašt evilo št. mest od kr it elji letnica odkritja
26972593 - 1 2098960 GIMPS 1999
23021377 - 1 909526 GIM PS 1998
22976221 - 1 895932 GIM PS 1997
21398269 - 1 420921 GIMPS 1996
21257787 - 1 378632 Slowinski , Gage 1996
4859465536 + 1 307140 Scott, Gallot 2000
Tabela šes t ih največjih praštev il
3 Ed uard Lucas (1842- 189 1) . Rojen je b il v Amien su v Fr anciji . M ed francosko-
p ru sko vo jno (1870-1871) je slu žil v fra ncoski vojski ko t t opniški častnik. Po francoskem
porazu se je za p os lil kot profesor m a temat ike na ene m od p ariških licej ev . R a ziskovalno
je deloval pred vsem n a področj u t eorije števil. Njemu pripisujemo odkritje formule
..;5Fn = (( 1 + ..;5 )/2) n - (( 1 - ..;5 )/2 )n za n-ti člen F ibonaccijev ega zaporedja Fn.