i i “966-Strnad-naslov” — 2009/6/3 — 9:38 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 17 (1989/1990) Številka 6 Strani 326–330 Milena Strnad: PRAŠTEVILA NEKOČ IN DANES - Kar so osnovni delci v fiziki in elementi v kemiji, so praštevila v teoriji števil Ključne besede: matematika. Elektronska verzija: http://www.presek.si/17/966-Strnad.pdf c© 1990 Društvo matematikov, fizikov in astronomov Slovenije c© 2009 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. PRAŠTEVILA NEKOe:: IN DANES "Kar ' so osnovni delci v fiziki in elementi v kemiji, so praštevila v teoriji števil" Na vprašanje "Kaj so prsštevilel" zna odgovoriti vsak učenec. ki je končal peti razred osnovne šole: "To so tista naravna števila. ki so večja od 1 in deljiva le z 1 in s samim seboj." Našteti nekaj manjših praštevil tudi ni težko : 2. 3. 5. 7. 11. 13. 17. 19.... Marsikdo bi še dodal. da se da vsako naravno število . ki ni praštevilo . razcepiti na produkt samih praštevil - prafaktorjev. Zato imenujemo ta števila sestavljena števlls. Tak racep je mogoč le na en način. če se ne menimo za vrstni red prafaktorjev . na primer: 12 = 2 · 2· 3. 15 = 3 . 5. 16 = 2 . 2 · 2 · 2 = 24 . 120 = 23 · 3· 5. Manj učencev najbrž ve. da je na to vprašanje znal odgovoriti Grk Evklid že 350 let pred našim štetjem . Dokazal je tudi. da je praštevil neskončno mnogo. Dokaz in še marsikaj zanimivega o praštevilih. tudi drugačno. a enakovredno definicijo praštevila . najdete v članku B. Lavriča v lanski 2. številki Preseka . Matematiki ne bi bili matematiki. če si ne bi postavili še več vprašanj. na primer: 1. Kako naj praštevila ločimo od vseh naravnih števil 1. 2. 3.4. 5.6.7.8. .. . N -1, N? 2. Ali obstaja aritmetična formula . ki zajame vsa . skoraj vsa ali le nekatera praštevila? 3. S kakšno metodo zanesljivo ugotovimo . ali je neko naravno število praštevilo ali ni? Na prvo vprašanje je odgovoril že Grk Eratosten v drugem stoletju pred našim štetjem. O Eratostenovem situ je pisal Presek dvakrat . v omenjenem članku in v 1. številki leta 1973/74. Ta metoda je uporabna le pri dovolj majhnih številih . Pri številih z več kot osmimi ciframi namreč t udi ob pomoči velikih račun alnikov z njo ni preprosto ugotoviti. ali gre za praštevilo ali ne. Drugo vprašanje ima več delnih odgovorov. Omenimo le najzna- menitejšega . ki ga je v obliki hipoteie zapisal eden izmed največjih francoskih matematikov Pierre de Fermat (slika 1). O njegovem življenju in delu je pisal Presek v 1. številki leta 1975/76. Fermat je v pismu rojaku Marinu Mersennu zatrdil , da so vsa števila - dandanes jim pravimo Fermatova števi!s - z obliko Fn = 2 2 n + 1 za nE N praštevila . Hitro ugotovimo . da Fermatova trditev za n = 1. 2 in 3 zares velja: Fi = 5. F2 = 17. F3 = 257. Z F4 = 65537 za n = 4 pa je nekaj več dela. Resne težave se začnejo že pri n = 5 in se z vsakim naslednjim Slika 1. Pierre de Fermat (1601 do 1665) 327 Slika 2. Carl Friedrich Gauss (1777 do 1855) naravnim številom hitro veča]o. saj zaporedje Fermatovih števil izredno hitro narašča. Zato ni čudno. da je Fermatovo hipotezo ovrgel šele leta 1732 znameniti matematik Leonhard Eu/er. ki je dokazal. da število Fs = 232 + 1 = 4294967297 ni praštevilo . ker je deljivo s 641. Fermatova hipoteza je napeljala druge matematike na pomembna od- kritja. Tako je Kar/ Friedrich Gauss (slika 2) po proučevanju Fermatovih števil napisal leta 1801 znamenito delo Dlsqulsltiones erithmetlcse, ki je temelj moderne teorije števil. V zadnjem. sedemnajstem razdelku knjige je dokazal tesno povezavo med Fermatovimi praštevili in konstrukcijo pravilnih mnogokotnikov z ravni/om in šestilom. Pri tem smemo uporabljati ravnilo le za risanje črt. ne pa za merjenje. in šestilo le za risanje krožnic. ne pa za prenašanje dolžin. Pokazal je. da je na ta način mogoče konstruirati vse pravilne mnogokotnike. katerih število stranic se da zapisati v obliki 2k pl P2...Pr. če je k naravno število ali O in so Pl, P2 ''''0 Pr Fermatova praštevila. To. da je mogoče z ravnilom in šestilom konstruirati pravilni sedemnajstkotnik (F2 = 17). je Gauss imel za svoje največje matematično od kritje. Želel je celo. da mu mnogokotnik narišejo na nagrobnik. Želje 328 mu niso izpolnili. p a č pa je narisa n pravilni sede mnajs t kotnik na Gaussove m spomeniku v njegovem rojs tne m kraju Braunsc hweigu. Na tretje vprašanje pozn amo pravilen teoreti čen od govor že iz sta rih grških č a sov. Njegovo upor abo pa odkrivajo šele sedaj. Metodo. ki teme lji na definicij i pra števila, imenujemo deljenje s preizkušanjem. Število N kar po vrst i delimo s števili 2. 3. 4. 5. 6. 7. ... . (N - 1). Kakor hitr o je eno izmed njih delit elj števila N . vern e . da je to število sestavljeno . Tako ugotovimo tudi najmanjši delitelj števila N in njegov prvi prafaktor. Po delje nju števila N s tem prafakto rjem do bimo količ n i k , ki ga zopet delimo s preizku šanj em . Teoreti č n o lahko tako ugotovimo vse prafaktorje sestavljenega števila . V praksi pa je metoda uspe šna le. č e število N ni preveliko . na primer 150 = 2 ·75 = 2·3· 25 = 2 . 3 .5 2 . Metodo deljenj a s prelzku ša njcrn izboljš amo tak o. da se opremo na Eratostenovo ugotovitev in iz množice vseh možnih deliteljcv števila N i zl oči mo vsa tis ta števila . ki niso pra števila in niso večja od št evila .;N. Zakaj je tako . lahko preb eret e v knjigi l.Vidava Re šeni in nerešeni problemi m ate ma tike . DMFA Slovenije. Tak n a čin je ob pom oč i dobrega r ač un a l n i ka uporaben pri štcvili h z najve č dese timi ciframi. Pri številih z dvaj se t in veC ciframi pa od pove. kol razbe remo iz tab ele. Za ugot ovite v. ali je dano število z dvajse t do t isoč cifra mi praš te vilo. obsta ja več dob rih računalniških metod. Ena izmed njih slo ni na primer na Wilsonovem izreku: p je pra števi lo tedaj in sa mo ted aj. če je število (p - 1)! + 1 deljivo s p. Pri te m jc N! = 1. 2.3.. .(N - 1)N . Toda s temi metodami v sploš nem ne moremo velikega scs tavljencga šte vila razs ta viti na prafakto rje. StevIl o c if er d elje nj e s prei zku SJnjem racun alnt ska m eto da 20 50 10 0 200 1 0 00 Tabela 1 : 2 uri 1 0 se kund 10 let 1 5 se ku n d 1 0 3 6 let 40 seku nd 1 0 8 6 let 10 m in u t 104 8 6 let 1 teden C as . ki j e p otreb en . d a z raCunain ikom preve ri mo . ;:l ii je ka ko stev t!o oras t evuo Obs tajajo pa metode . s kate rimi je mogoce razcep iti Fermatova števila . ki imajo do osemdese t cifer . Tako je Landry leta 1880 dokazal. da je šte vilo F6 deljivo z 274177. Lel a 1905 sta Morehcad in WesterelI pokazala . da je šte vilo F7 z 39 ciframi sest avljeno šte vilo. Štiri leta za tem sta to pokazal a t udi za šte vi lo F8 z 78 ciframi . Dokon čen razce p štev ila F7 . ki velja za doslej najt ežjega . sta šele leta 1971 naš la Brilhart in Morrison . Za t a razce p 329 je računalnik IBM 360-91 porabil poldrugo uro. Število Fs sta leta 1981 razcepila z računalnikom UNIVAC 1100/42. Prvi prafaktor s 16 ciframi je računalnik izračunal po dveh urah. Nista pa ugotovila , ali je drugi faktor z 62 ciframi praštevilo ali ne. Da gre za praštevilo. je kmalu zatem ugotovil Williams. Pokazalo se je. da vsebujejo Fermatova števila od F9 do F13 razmeroma majhne najmanjše prafaktorje. največjega s 13 ciframi vsebuje število F13 . Kljub temu. da ta števila niso zelo velika. pa jih doslej še niso uspeli razcepiti. Prav tako še ni znan razcep sestavljenega števila s 148 ciframi. ki pornnoženo spraštevilom 24148333 tvori število F9 . Praštevila in šifriranje Prastavlla je rnococe uporabiti prI strrtranju sporočll . Zelo zanesljivo strro RSA Public Key System so si IzmIslIII matematiki Rlvest, Shamlr ln Adleman na osnovi spoznanja , da ni sorosns metode, po katerl bl razcaplll stavno z dvesto ciframi na oraraktorja s , denimo, po sto cltrarnl. Površno rečeno, ustreza šlfrlranje množenju z dvema velikima pr aštevllorna. dasltrtranje pa razcep u na praštevlla . Načln je Se posebno uporaben za to . ker pri Slfrlranju ni treba poznati obeh prataktorjev, ampak samo njun produkt. Pri dašltrtranlu pa je treba poznati oba praraktorja . Tako po šl llate ll u sporočl la ni treba poznati šlt re, dovolj je, da jo pozna prejemnIk . Zato ta nacln strrtranja uporabljajo v javnih Informacijskih ornrazj tn, na primer telefonu . Rekordi Zelo zanimive podatke o praštevlllh vsebuje knjloa P.Rlbenbolma , The Book of Prime Number Records , Sprlnoer 1989 . • V EvklIdovem dokazu nastopa produkt vseh orastavtt , ma nj šlh od P. povečan za 1, torej 2 ·3 ·5 ... P + 1. V nekaterih primerih je to praštevllo , Sedanji rekorder je za o = 13649 praštevl!o, ki Ima 5862 cifer . • o ln o + 2 je dvojček orastevu. Za Zdaj je rek order dvoj ček 107570463 . 1022 50 ± 1. • Nekatera Izmed št evl l , ki Jih sestavljajo same enice . 111 .. .1, so praštevlla . Sedanji rekorder je orastevtto s 1031 enicamI. • Mersennova stevl la Imajo obliko 2 n -l. Mersennovo števllo 2216091_ 1 s 65050 ciframi je bilo najvecje znano praštevllo med letoma 1985 ln 1989 . Rlbenbolm je v uvodu svoje knjloe, ki obravnava resna vprašanja mate- matike ponekod na zabaven naein. zapisal: "Naravnost rečeno, bl se ml zdelo visoko civilizirano, Ce bl bral, da se je veni na šlh krčem razv ilo prerivanje Iz razcreta razprave o najve čjem cvojzku praštevll . Zdaj že vemo, da za vse vrednosti n od 5 do 16 (in še za nekatere druge) Fermatova števila Fn niso praštevila . Domnevajo celo, da so le prva štiri Fermatova števila praštevila. vendar ta hipoteza ni nič trdnejša. kakor je bila Fermatova. Stevilo cifer najvegjega znanega praItevila je zalielo hitro naragtati , ko so se razvili raCunalniki. Leta 1952 je irnelo najvecje znano praStevilo 157 cifer. a leta 1978 fe 6533 cifer. Leta 1985 je D. Slowinski s sodelavci ugotovil, da je Mersennovo EteviIo 22160g1 - 1 s 65050 ciframi pra5tevilo. To praSteviio navaja Ribenboim kot rekordno. Toda poleti 1989 so .InBrown in njegovi sodelavci povda l i rekord za 37 cifer. Zdaj ima rekordno praBtevilo re 65087 cifer. Kdo ve. kako dolgo bo "dr2alo" rekord? Dobili so ga takole. Najprej so izbrali 350000 kandidatov. S preiz- ku5anjem so j ih delili z nekaj milijardami najmanjYih praftevil. Preizkus je prestalo samo 7000 kandidatov. Te so nato obdelali z raEunalnirkimi metodami. Obdelava enega Ltevila z rarunalnikom je trajala kar osemdeset minut. KO se je Stevilo kandidatov Ye motneje razredtilo, so za eno Stevilo porabili le He pol ure. Tako so se naposled preprillali, da je zapisano Stevilo praKtevilo. Take ratune delajo razunatnigke dru2be. EeH da lahko uporabijo pridobljene izkuEnje pri izboljSanju ratunalnikov. Najbr;! pa gre pri tern tudi za tekmovanje. Milena Strnad