ISSN 0351-6652 Letnik 25 (1997/1998) Številka 3 Strani 130-136
Ivan Vidav:
KAKO UGOTOVIMO, DA JE NARAVNO ŠTEVILO SESTAVLJENO, PREDEN GA RAZSTAVIMO?
Ključne besede: matematika, teorija števil, naravna števila, praštevila, sestavljena števila.
Elektronska verzija: http://www.presek.si/25/1335-Vidav.pdf
© 1997 Društvo matematikov, fizikov in astronomov Slovenije © 2010 DMFA - založništvo
KAKO UGOTOVIMO. DA JE NARAVNO ŠTEVILO SESTAVLJENO, PREDEN GA RAZSTAVIMO?
Uvod.
Pred nekaj leti sta Richard Crandall in Christopher Doenias (ZDA) z računalniki dognala, da je dvaindvajseti člen Fermatovega zaporedja F22 sestavljeno število. Do istega rezultata, sta skoraj istočasno toda z drugačnim računalniškim programom prišla, tudi Vilmar Trevisan in Joao Carvalho v Braziliji. Ne prvima ne drugima pa ni uspelo najti nobenega faktorja.
Fermatovo zaporedje se glasi
Fn = 22" + 1 .	(1)
Členi Fn z indeksom n izredno hitro naraščajo. Tako se F22 izraža, v desetiškem sestavu s številko, ki ima nad milijon števk, in je torej nepredstavljivo veliko. Je največje naravno število, o katerem vemo, d a je sestavljeno, ne poznamo pa. (še) nobenega njegovega faktorja.
Fermat je domneval, da sestoji zaporedje (1) iz samih praštevil. Za prve štiri člene to res velja: Fj, = 5, F2 — 17, F3 = 257 in F4 = 65 537. Toda že Euler je odkril, da. je F& = 232 + l sestavljeno število, deljivo je namreč s 641. Pozneje so ugotovili, da so sestavljena števila tudi mnogi drugi členi, npr. Fq, F7, Fg, F9, F10 itd., praštevila pa niso našli med njimi nobenega več. Zanimivo je, da sta Morehead in Western dognala na začetku tega stoletja, da sta. Fj in Fg sestavljeni števili, čeprav nista, dobila nobenega faktorja. Na prafaktorje so ju razstavili skoraj 70 let pozneje, ko so izdelali boljše metode za razstavljanje in so se pojavili sodobni računalniki. Števili Fg in F1Ql prvo ima v desetiškem sestavu 155 in drugo 309 števk, pa so razstavili na prafaktorje šele pred nekaj leti.
Kakor vemo iz aritmetike, je vsako naravno število bodisi praštevilo bodisi sestavljeno in, če je sestavljeno, se da razstaviti v bistvu na. en sam način v produkt praštevil. Obstajajo metode, s katerimi moremo vsako dano število razstaviti na prafaktorje. Najpreprostejši postopek je s po-Škušanjem: Število Ar delimo z zaporednimi naravnimi števili 2, 3 itd. do največjega celega števila, ki ne presega Vn. Ce ni z nobenim deljivo, je N praštevilo, če pa je s katerim izmed navedenih števil deljivo, je najmanjše med njimi (to je prvi delit.elj, ki nanj pri tem postopku naletimo), prafaktor p. N razstavimo v produkt N = p • Ari in na drugem faktorju Ari ponovimo postopek. Metoda s poskušanjem nas sicer privede vselej do cilja, toda je izredno počasna. Veliko truda potrebujemo, da z njo razstavimo nekoliko večje število. Ce bi pa hoteli po tej metodi z računalnikom,
ki opravi milijon deljenj na sekundo, razstaviti pet deset mestno število, bi potrebovali v najneugodnejšem primeru tudi nekaj bilijonov let.
Na dejstvu, da ne znamo razstaviti velikih števil v razumnem času na prafaktorje in to niti s sodobnimi računalniki ne, sloni metoda tajnopisa z javnim ključem, ki sojo razvili Rivest, Shamir in Aldeman (metoda RS A). Javni ključ je produkt dveh orjaških praštevil. Tajnopis pa lahko razvozla samo tisti, ki pozna oba faktorja (glej članek M. Vencelj: Šifriranje z javnim ključem, Presek 22, str. 354-357). Avtorji so pred dvajsetimi leti objavili v časopisu Scientifie American število s 129 mesti in pozvali bralce, naj kdo izmed njih poskuša razstaviti to število v produkt. Razcep se je posrečil šele leta 1994. Med tem časom so nainreČ razvili nove metode za razstavljanje, ki so seveda hitrejše od metode z zaporednim deljenjem. 2 njimi je zdaj mogoče razstaviti števila, ki imajo, zapisana v desetiškem sestavu, nekaj nad sto števk. Med drugim se je posrečilo razstaviti Fg
in Fi0.
Kako lahko vemo o kakšnem naravnem številu, da je sestavljeno, preden smo ga razstavili? Včasih je to mogoče ugotoviti pri številih, ki se odlikujejo z določenimi lastnostmi, oziroma imajo posebno obliko. Namen tega članka je, da si ogledamo nekaj takih primerov.
1,	Vzemimo Število 1 000 001. Pišemo ga lahko v obliki
1000 001 = 1003 + 13 ,
se pravi kot vsoto d veli kubov. Iz elementarne algebre pa vemo, da se da vsota dveh kubov razstaviti
a3 + i>3 = {a + b)(a2 -ab + b2).
Če postavimo a = 100 in b = 1 dobimo razcep 1 000 001 = 101'9901. Oba faktorja na desni sta praštevili.
Tudi vsota dveh petih, sedmih in splošno dveh poljubnih potenc z enakima lihima eksponentoma se da razstaviti. Tako je npr, 100 001 = = 10G + 15 = 11-9091. V vseh teh primerih vemo, daje število sestavljeno, preden smo ga razstavili, pa tudi faktorja takoj najdemo.
2.	Če je naravno število vsota dveh kvadratov, ni vselej sestavljeno. Včasih je praštevilo, kot kaže zgled 41 = 42 + 52, včasih sestavljeno: 50 = = l2 + 72 = 2 ■ 52. Pri tem velja:
Če je kakšno naravno število izrazljivo na dva različna načina kot vsota dveh kvadratov, je sestavljeno.
Na primer G5 je enako l2 + 82 in 42 + 72. Število 65 je produkt prafaktorjev 5 in 13, fi5 = 5 ■ 13.
Dokažimo zdaj našo trditev! Denimo, da smo naravno število N na dva različna, načina zapisali kot vsoto dveh kvadratov
N = A2 + B2 in N = C2 + D2.	(2)
Tu so A. B. C, D znana naravna števila in je par A, B različen od para C, D. Pri dokazovanju se bomo omejili na primer, ko je N lih (če je sod, ima faktor 2 in je sestavljeno število). Ugotovili bomo, da je N produkt dveh takih faktorjev U in V, torej N = UV, ki sta oba izrazljiva z vsoto dveh kvadratov. Privzemimo, da je to res, in postavimo
U - a2 + b2 in V = c2 + d2 .	(3)
a, b, c, d so cela števila, ki jih za zdaj še ne poznamo. Kako bi jih izračunali?
Preprosta verifikacija pokaže, da veljata identiteti
UV = (a2 + J>2)(c2 + d2) = (se + bdf + {ad - bc)2	(4)
UV = {a2 + b2){c2 + d2) = (ac - bd)2 + (ad + bc)2	(4*)
Ker je UV — N, vidimo, da sta enačbi (2) izpolnjeni, če postavimo
ac + bd = A , ad — bc ~ B ,
(5)
ac — bd = C ad + bc — D .
Poskušajmo iz tega sistema izračunati a, c in d. S seštevanjem in odštevanjem dobimo produkte
ac^l-(A + C), ad=l-{B + D), bd = ±(A - C), bc=±(D-B).
(6)
Ker je N lih, pove prva enačba (2), da je eno izmed števil A in B liho in eno sodo. Isto pove druga enačba (2) o paru C, D. Naj bosta npr. A in C soda ter B in D liha. Potem so vse desne strani v (6) cela števila. Ker so tudi n, b, c, d cela števila, vidimo iz prvih dveh enačb, daje a skupni delitelj števil \{A + C) in ¿¿(B + D). Vzemimo za a kar največji skupni delitelj teh dveh števil. Izračunamo ga lahko z Evklidovim algoritmom. Tako dobimo a in nato iz prvih dveh enačb (6) še c in d:
c= (A + C)/2a in d = {B + D)/2a .
Ker je a največji skupni delitelj produktov ac in ad, sta si c in d tuja. Potem izračunamo b iz tretje ali četrte enačbe. Obe nam dasta isto vrednost: Iz enačb (2) namreč izhaja, da je A2 — C2 = D2 — B2 in zato (A - C)a/(B + D) - (D - B)a/(A + C). Da je tudi b celo število, ugotovimo takole: b je kvocient celih števil (A — C)a in B + D. Torej je racionalen in ga lahko zapišemo v obliki okrajšanega, ulomka b = r/s, kjer sta 7' in .9 celi števili brez skupnega faktorja in je s > 0. Ker sta produkta bd = rd/s in bc = rc/s celi števili, to namreč povesta zadnji enačbi (6), sta števca rd in rc v ulomkih na desni deljiva z s. Toda r je tuj proti s in sta potemtakem c in d deljiva z s. Ker sta si tudi d in c tuja, pa mora, biti imenovalec s = 1 in b = r celo število.
Pri tako določenih a. b, c, d veljajo enačbe (6). Če produkte (6) vstavimo v (5), vidimo, da so tudi te enačbe izpolnjene. Ker je U — = a2 + b2 in V = c2 + d2, pove identiteta (4), da je UV = A2 + B2 = N, Par A. B je različen od para C, D in so zato desne strani v (6) različne od nič. To pa pomeni, da so tudi a. b, c, d različni od nič in, ker so cela števila, je U > 1 ter V > 1; razcep N — UV je pravi. S tem smo dokazali trditev, daje N sestavljeno število, našli faktorja U in V, hkrati pa smo U in V" izrazili z vsoto dveh kvadratov.
Ker lahko pišemo
je vsako Fermatovo število vsota dveh kvadratov. Če bi se nam posrečilo zapisati Fn Še kako drugače kot vsoto dveh kvadratov, bi vedeli, da je sestavljeno število, in tudi razstaviti bi ga znali v produkt dveh faktorjev. Za zgled vzemimo
F5 = (216)3 + l2 = 65 5362 + 1 , ki ga lahko pišemo tudi v obliki
F5 = 62 2642 + 20 4492 .	(7)
Zdaj imamo
A = 65 536 , 0 = 1, C = 62 264 , D — 20 449 . Enačbe (6) se tu glasijo
ac — 63 900, ad = 10 225, bd = 1636, bc = 10 224. (8)
Najprej poiščemo z Evklidovim algoritmom največji skupni deliteij števil 63 900 in 10 225 in dobimo, da je 25. Največji skupni deliteij je enak a, torej a = 25. Enačbe (8) zdaj dajo c = 2 556, d = 409, 6=4. Potemtakem je U = 252 + 42 = 641 in V = 25562 + 4092 = 6 700 417, torej F-a = G41 6 700 417. Oba faktorja sta praštevili.
Seveda bo kdo vprašal, kako smo našli izrazitev (7)? Odgovor se glasi: s poskušanjem. Vendar je treba priznati, da je s tem poskvišanjem kar precej dela. Ker je tu faktor 641 razmeroma majhen, najdemo razcep veliko hitreje, če delimo Fr> z zaporednimi naravnimi števili. 3. Obstajajo tudi metode, s katerimi včasih ugotovimo, da je dano število sestavljeno, ne povejo pa te metode, kako priti do kakšnega faktorja. Mali Fermatov izrek iz teorije števil nam na primer da tale kriterij:
Naj bo N dano naravno število. Izberimo poljubno celo število a. Če razlika a,N — a ni deljiva z ¿V, je N sestavljeno število.
Dokaz najde bralec v knjigi: J. Grasselli, Osnove teorije števil, 1975, na strani 74.
Pripomba, Ta kriterij ne pove nič v primeru, kadar je razlika aN — a deljiva z N: tedaj je lahko N praštevilo ali sestavljeno število.
Test napravimo tako, da si najprej izberemo o., npr. 0 = 2 ali a = 3. in potem izračunamo aN — a, Ker je N po navadi veliko število, se na prvi pogled zdi. da je ta metoda ugotavljanja praštevilskosti počasnejša od metode s poskušanjem, saj bi opravili deljenje z vsemi števili do \/N verjetno prej, kakor pa izračunali potenco aN, ki je pri velikem N orjaško število. Vendar ta videz vara. Potenco a- izračunamo razmeroma, hitro z zaporednimi kvadriranji in si tako prihranimo veliko dela. In ker gre pri testu le za vprašanje deljivosti razlike aN — a z N, se lahko pri računanju omejimo na števila manjša od N.
Oglejmo si posebni primer, ko je N oblike 2m + 1. kjer je eksponent m sod (če je lih in > 1, je število N deljivo s 3 in sestavljeno). Pri Fermatovih številih je m = 2n, Sestavimo zaporedje naravnih števil
0o, Oi, o2, o3,...	(9)
takole: Naj bo oq = 3, Če smo člen o^ že našli, ga kvadriramo in kvadrat o J*, delimo z N. Ostanek pri tej delitvi je naslednji Člen Ok+i- (Denimo, da je N > 9. Potem je oi = Oq = 9, ker dobimo ostanek 9, če delimo 9 s številom večjim od 9. Podobno je 02 = 81, če je Ar > 81.) Zaporedje (9) lahko priredimo vsakemu naravnemu številu N > 3. Ker so členi Oi, . .. ostanki pri deljenju z A', so vsi manjši od N.
Iz zgoraj navedenega testa pri a = 3 izpeljemo z uporabo reciproč-noslnega zakona iz teorije števil tale pogoj za praštevilskost:
Število N = 2m + 1 je praštevilo natanko takrat, kadar je člen i pripadajočega zaporedja (9) enak N — 1, torej =
= N~ 1 = 2m.
Zgledi.
1.	Vzemimo najprej m — 4, torej N = 2'4 + 1 = 17 = F2. Poiskati je treba člen 03 zaporedja (9). Tu je O] — 9, o2 = 13 in 03 = 16 = N — 1. Res je N = 17 praštevilo.
2.	Pri m = 6 potrebujemo člen 05. Zdaj je 01 = 9, 02 = 16, 03 = 61, o4 - 16 in o5 = 61 ± 64 = 26. Število N = 26 + 1 = 65 ni praštevilo, 65 — 5 ■ 13.
Pripomba. Ni težko ugotoviti, da je 2m + l praštevilo kvečjemu tedaj, kadar je m potenca od 2, se pravi m = 2".
3.	Pri Fermatovih številih Fn je eksponent m = 2", ki z n hitro narašča. Zato se liitro veča število členov zaporedja (9), ki jih je treba izračunati pri tem testu, še hitreje pa raste Fn. Za število F5 je m = 25 = 32 in moramo izračunati člen 031, če želimo ugotoviti, da F^ ni praštevilo (faktorja nam test ne da). Z računanjem je precej dela in spet pridemo hitreje do faktorja 641 z zaporednim deljenjem.
Oglejmo si F22■ Po število ima, zapisano v desetiškem sestavu, kakor smo že povedali, nad milijon števk. Ker je tum = 222 = 4 194 304, moramo izračunati 4 194 303 člene zaporedja (9). Pri določanju ostankov je treba deliti števila z nad milijon mesti. Dela je vsekakor ogromno. Vendar so ga sodobni računalniki zmogli. Potrebovali so okoli 10lfl osnovnih operacij. Test je pokazal, da je F22 sestavljeno število, seveda pa ni dal nobenega faktorja. Razstaviti F22 na prafaktorje je težja naloga, ki terja neprimerno večji obseg računanja. (Z zaporednim deljenjem ne pridemo nikamor, saj je pri tako velikem številu, kakor je F22, velika verjetnost, da ima tudi najmanjši prafaktor nad tisoč mest.) Morda se bo razcep posrečil, ko bodo odkrili še boljše metode za razstavljanje in izdelali še hitrejše računalnike. Naloge.
1. Najmanjše naravno število, ki je izrazljivo na dva načina kot vsota dveh četrtih potenc, je 635 318 657. Je namreč
635 318 657 = 133"1 + 1344 = 594 + 1584 .
Razstavi to število na prafaktorje!
2.	Z žepnim računalnikom razstavi F& na dva faktorja, če veš, da je
F6 = 4 046 803 2562 + 1 438 793 7592 .
3.	Naj bo N sodo število, ki se da na dva različna načina zapisati kot vsota dveh kvadratov: N = A2 + B2 in N = C2 H- D2. Dokazi, da so v tem primeru bodisi vsa števila A, B, C, D soda bodisi vsa liha in da sta faktorja U in V pripadajoče razcepitve večja od 2.
Ivan Vidav
Literatura
Richard E. Crandall: The Challenge of Large Numbers. Scientific American. Vol. 276, Febr. 1997, str. 58 62.
Akademika prof. dr. Ivana Vidava, znanstvenika in vzgojitelja številnih rodov slovenskih matematikov, poznajo Pre-sekovi bralci predvsem kot avtorja zanimivih matematičnih člankov. V kratkem bo naš spoštovani sodelavec praznoval okrogli življenjski jubilej.
Za praznik mu iskreno voščimo!