i
i
“5-2-Stare-0” — 2010/9/2 — 11:06 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 5 (1977/1978)
Številka 2
Strani 81–86
Janez Stare:
NEKAJ O TEORIJI ŠTEVIL
Ključne besede: matematika.
Elektronska verzija: http://www.presek.si/5/5-2-Stare.pdf
c© 1977 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.
NEKAJ OTEORIJI šTEVIL
Sodobna matematika obsega precej vej, katerih poimenovanje,
utrjeno skozi stoletja , ne pove vedno njihove dejanske vsebine.
To velja tudi za teorijo števil, eno najstarejših vej matemati-
ke, ki je privlačevala pozornost mnogih velikih matematikov
skozi preteklih 2300 let. Z njo so se ukvarjali stari Grki, In-
dijci in Kitajci, hiter razvoj pa je doživela predvsem po Fer-
matu {1601-1665}, enem od največjih francoskih matematikov.
Ime "teorija števil" bi nas lahko privedlo na misel, da je
to neke vrste splošna teorija, ki se ukvarja s pojmom števila,
teorija torej, ki iz naravnih števil izvede cela, racionalna,
realna in kompleksna števila in ki gradi teorijo operacij nad
temi števi 1i . Pričakoval i bi, da sta npr. znana za kona
a+b = b+a
{a+b}+ a = a+{b+a}
a.b = b.a
{a .b}. a = a . {b.a }
komutativnostni zakon
asociativnostni zakon,
ki veljata za seštevanje in množenje vseh naštetih vrst števil,
produkta teorije števil. Toda to ni tako . Teorija števil se za-
nima za lastnosti celih števil
.. . -3, -2, -1, 0,1,2,3 , ...
Pri tem privzame pojem celega števila in teorijo operacij nad
temi števili za znana. Pri svojih raziskovanjih lastnosti celih
števil pa s pridom uporablja tudi realna in kompleksna števila
in nemalokrat poseže v druge veje matematike, kot sta npr. ana-
liza in algebra .
Najlaže opišemo teorijo števil tako, da navedemo več proble-
mov, ki sodijo v teorijo. Da je naštevanje problemov čim bolj
urejeno, jih razdelimo glede na njihovo naravo v štiri skupine.
Ti ne zajamejo vsega, kar teorija števil obravnava, vtis o njej
pa bomo vendarle dobili .
Najprej so tu multiplikativni problemi, ki obravnavajo delji-
vost celih števil. V to skupino spada eden najosnovnejših in
najpomembnejših izrekov v teoriji števil; včasih imenovan "os-
novni izrek teorije števil", ki pravi:
Vsako pozitivno celo število n, ki je večje od 1, se da eno-
lično zapisati kot produkt praštevil , če se ne oziramo na vrstni
red faktorjev. Pri tem je praštevilo vsako celo število večje od
81
l. ki je deljivo samo z 1 in s samim s eboj, č e . upo štev amo s amo
pozitivne delitel je.
Uporabnost tega izre ka v teoriji števil je iz redno vel i ka.
Iz r a zs t a v i t ve števila n na produ kt praštevil lah ko določ imo
š t ev il o pozi t ivnih deliteljev št ev i l a n. To štev i lo označ i mo z
d (n ) . Različna števila i maj o v splošnem s eveda ra zl ično mnogo
deliteljev in zato z ozna ko d (n) na kaž emo. da j e š t ev i lo del i-
teljev d odvisno od n . Pr avimo, da je š t ev i l o d fun kci ja š tev i -
la n. Zdaj si lahko zastavimo r a z na vpra šanja o vrednosti d (n ) .
Ali z večanjem števila n tudi d (n ) ves č a s nara šča. ali doseže
poljubno velike vredn osti, ali zav zame kak šno vred nost ve č krat
in podobno. Na na šteta v pr a šanj a je kaj l a hko odgov oriti , a pr e-
den se lotimo odgovo rov . poda jmo s t a be lo prvi h nek a j vred nosti
f unkc i j e d (n ) :
n d (n ) n d (n )
1 1 13 2
2 2 14 4
3 2 15 4
4 3 16 5
5 2 17 2
6 4 18 6
7 2 19 2
8 4 20 6
9 3 21 4
10 4 22 4
1 1 2 23 2
12 6 24 8
Le na prvi pogled je očitno . da j e ved enje fun kc ij e d (n ) zel o
neurejeno. če j e n = 2m• deli jo n š t ev i la 1,2,2 2 • . ..• 2m tak o . da
je d (2m) = m+l . če pa je n pr a število, j e seved a d (n ) = 2 . Ker
je. kot bomo spoznali . pr aštevil n eskončn o , uv i d i mo , d a d os eže
d (n ) po ljubno veli ke vr ednosti in obenem vr edn ost 2 za ne sko nč n o
mnogo n. S tem smo odgovorili na zastavljena vpr a š a nja. toda ob
nadaljnem študir a nju t a be le se hi tr o zas tavi jo nova :
a) Ali j e za r e s d (n) l i ho samo t a kr a t , kadar je n kva dra t?
b) Ali velja d (m ).d (n ) = d (m.n ), če m in n nimat a sk upne ga fa kto r-
ja?
c) Kol ikšna je p ovprečna vredn ost d (n ). s e pr av i , kaj l ah ko pove-
82
mo o (d(1) + d(2) + • . , + d (N ) ) I N , ko N narašča čez vsako
mejo?
d) Ali zavzame d (n) naj več jev red nost i pri n z obl i ko 2m
e) Približno koliko je praštevil med 1,2, . •. ,N?
Vsa gornja vprašanja so značilna za multiplikativno teorijo
števil. Formulirana so kratko in jasno in marsikdo bi pričakoval,
da odgovori nanje niso preveč trd oreh. Toda za matematiko je
značilno, da je pogosto težko dokaz ati ravno preprosto postavlje-
ne probleme. Razlog je verjetno delno ta , da tak izrek s svojim
besedilom ne da nobenega namiga o pripomočkih , ki naj bi jih ra-
bili pri dokazovanju, deloma pa ta, da ustreznih pripomočkov ne
poznamo . V teoriji števil je veliko izrekov takšne vrste in prav
to jo dela še posebej privlačno . Na prvo izmed vprašanj je zelo
lahko odgovoriti. Naslednja vprašanja so težja, na zadnje vpraša-
nje pa nista uspela popolnoma odgovoriti niti tako velika mate-
matika,kot sta bila C.F . Gauss in A. Legend re, čeprav sta oba
slutila rešitev .
Vprašanj~ doka zov v teoriji števil bomo malo kasneje posvetili
še nekaj pozornosti, zdaj pa nadaljujmo z razdelitvijo teorije
števil.
V drugo skupino sodijo problemi aditivne teorije števil . Sem
spadajo vprašanja predstavljivosti pozitivnih celih števil kot
vsote celih števil določenega tipa . Pokaže se, da nekatera cela
števila, npr. S = 22 + 12 in 13 = 22 + 32, lahko zapišemo kot
vsoto dveh kvadratov, drugih, npr. 3 ali 12, pa ne moremo. Katera
cela števila se dajo zapisati kot vsota k-tih potenc in koliko je
takšnih zapisov in ali obstaja pri danem k neko takšno število
g(k), da vsako celo število lahko zapišemo kot vsoto kvečjemu
g(k) k-tih potenc. Ti vprašanji sta tipični za aditivno teorijo
števil .
V tretjo skupino bi lahko šteli diofantske enačbe , imenovane
po grškem matematiku Diophantu, ki jih je prvi študiral. To so
enačbe z eno ali več neznankami , njihove rešitve iščemo med celi-
mi števil i. Znano je npr., da je 32 + 42 = S2, kar nam da rešitev
diofantske enačbe x 2 + y2 = z2 . Vendar pa nas pri reševanju manj
zanima posamezna (partikularna) rešitev, bolj pa splošna formula
za vse rešitve . Zelo znana diofantska enačba je Fermatova enačba:
x n + yn = zn. Fermat je trdil, d a ta enačba nima rešitve, pri ka-
teri bi bili x, y in z vsi različni od nič, če je n ~ 3; trditev
83
ni koli ni bi la dokazan a ali ovržena za vse n. Danes pravzaprav ne
moremo govoriti o neki spl ošni t eor iji diofantskih enačb, čeprav
obs t a j a pr ecej s pe c ia ln i h metod, ki. so bile v e č i n o m a razvite za
r e š evanje dol o č eni h en a čb.
Di of an t sk e a pr oksim aci je s est avljajo zadnj o sk upi no . Ta veja
teo r ij e štev il s i na jbrž n a jv e č izpo soja iz drugih vej matemati-
ke in j im naj več vra ča . Zato t uka j o njej ne bomo govori li. Za
ra do ve d neže ome ni mo sa mo , da sp adata v to s kupino do kaza o trans-
c end e ntnos t i * štev i l e in ~.
Teor i jo št ev i l bi la hko ra zdel il i tudi drugače, npr. po meto-
dah, ki jih r ab i mo pr i do kaz ovanju izrekov . Toda bodi dovolj o
delitvah, raj ši pos ve t i mo š e nek aj besed doka zom.
Denimo, da imam o opraviti z ve čjim številom izrekov, ki govore
o istem predmetu, a s e njihov i dokazi v bistvu zelo razlikujejo.
V t em primeru imamo tehnik e pri različnih dokazih za posebne tri-
ke, od katerih je vsak uporaben ,s amo pri dokazu tist ih izrekov,
s katerimi je povezan. Tehnika pren e ha biti tri k in postane meto-
da š e l e takrat, ko je uporab ljena tolikokrat, da s e zdi na ravna .
D olo čen predmet imamo lahko z a "vrečo trikov", č e je število teh-
ni k v pr imerjavi s števi lom izr ekov preve liko. Zal so elementarno
te orij o š t ev i l v čas ih imeli za tak predmet . Z nadaljnim delom na
tem p odr očju pa so mnogo trikov združili v metodo : teorija števil
je poka za l a več en otn ost i, kot j e s prv a ka za lo .
Nakažimo na primeru e no od metod do kaz ovanja, tipičnih za teo-
rij o š t ev i l . Pos kusimo d okazati trditev, da je d (n ) sodo števi lo,
č e rt ni kvad r a t kak ega c e l ega š t evi l a . Dokaz teče t a kole: če d
de l i n , t udi nl d del i n . č e n ni kvadrat, d F nl d , ker je sicer
n = d 2 . Se pr a v i , č e n ni kvad r at , lahko njegove delitelje zdru-
ž imo v pare (d, n / d) t ako , da vsak delitelj števila n nastopa na-
t a nko en krat kot element e nega od t e h parov . š t ev i l o deliteljev
j e torej dvakrat š te v i l o parov in zato sodo . Bistven element t ega
dokaza je grupira nj e deliteljev š t ev i l a n v pare. Metoda grupi-
r a nj a števil v dolo čene s kupine j e ze lo uporabna , kadar hočemo
prešteti ce la števi la z d o l o č e n o l a s t nos t jo . Seveda pa te skupine
niso vedno pari, temveč je treba za posa mezen prob lem te vr s t e
šele odkr it i us t r e ze n nači n grupiranja.
Vel i ko je v teoriji števil negati vni h t rditev, npr . "vsake ga
* Štev ilo je tran~cen dentno, če pr i nobenem naravnem števi lu n ni reši tev
enačbe xn + Q,Xn- + . . . + Qn = O; Qi so cela števi la .
84
pozitivnega celega števila ne moremo izraziti kot vsoto treh
kvadratov". Takšne trditve zahtevajo od nas samo to, da najdemo
en sam primer. Za navedeno trditev je to npr. število 7. Na
drugi strani pa pozitivne trditve, kot je "vsako pozitivno celo
število se da izraziti kot vsota štirih kvadratov", ne moremo
dokazati s primeri, naj bodo ti še tako številni.
Poleg specialnih metod se v teoriji števil velikokrat srečamo
z dvema zelo splošnima tipoma dokazov: dokaz s protislovjem in
dokaz z indukcijo. O dokazih z indukcijo je bralec že slišal v
šol i ali paš e boa 1 i pa je 'preb ral kak šen čl ane k, ki govori s a-
mo o tem. Zato tukaj o indukciji ne bomo govorili. Pač pa na
primeru ilustrirajmo dokaz sprotislovjem.
Pravimo, da smo trditev P dokazali s protislovjem, če smo iz
predpostavke, da je p napačna, izpeljali trditev Q , za katero
vemo, da je napačna ali da Q nasprotuje predpostavki o nepravil-
nosti p. Za primer dokažimo trditev, da je praštevil neskončno
mnogo. Poskusimo torej iz nasprotne trditve priti do protlslovja.
Predpostavimo, da je praštevil končno. Naj bodo to PI' P2'"''
Pk' Tvorimo število N = P1P2''' Pk+1. š t ev i l o N je ali praštevilo
ali sestavljeno število. če je N praštevilo, smo že prišli do
protislovja, saj je N večje od vseh praštevil med PI' P 2, .. ·, Pk.
če pa je N sestavljeno število , je gotovo deljivo z nekim prašte-
vilom p. Vendar N ni deljivo z nobenim od praštevil PI,P2,,, ,,Pk'
saj je ostanek pri deljenju s temi praštevili vedno enak 1. Pra-
število P torej ne more biti enako nobenemu praštevilu med PI'
P2"",Pk' Zopet smo prišli do protislovja in tako dokazali, da
je praštevil neskončno.
Omenimo na koncu še tri lastnosti naravnih ali pozitivnih ce-
lih števil, ki jih v teoriji števil večkrat uporabljamo :
1. Vsaka neprazna množica naravnih števil ima najmanjši e lement .
2. če sta a in b naravni števili, obstaja naravno število n tako,
da je na > b.
3. Naj bo n naravno število. če razdelimo množico iz n+l elemen-
tov v n ali manj podmnožic tako, da vsak element spada v na-
tanko eno podmnožico, vsaj ena podmnožica vsebuje več kot en
element.
Vse tri lastnosti so posledice aksiomov, ki jih je za naravna
števila postavil Peano in jih v teoriji števil privzamemo brez
dokaza.
8 5