Poglavje 6 Računanje

6.1 Velikani v kratkih hlačah

Ste že kdaj z manj dela opravili več? Gotovo!

Nekatere postopke ponavljamo vedno znova in takrat se pogosto vprašamo, ali je postopek, ki ga uporabljamo kot pot do rešitve, dovolj učinkovit, ali morda celo optimalen (to pomeni, da je najboljši možen). Tisti prvi postopek, ki nas pripelje do rešitve ponavadi ni najbolj učinkovit in ga sčasoma, ko napredujemo v svojem znanju, popravimo in izboljšamo. Ideji, kako do rešitve problema, ki nam je prišla na misel na samem začetku, običajno rečemo:

• naivna (če očitno ni optimalna),
• požrešna (če brez premisleka pregleduje),
• izčrpna (če pregleda čisto vse možnosti), \(\dots\)

V tem razdelku bomo razmišljali o učinkovitosti osnovnih računskih operacij.

Učinkovit zapis števil

Ste se že kdaj vprašali, zakaj zapisujemo števila tako kot jih? Število 10 bi lahko zapisali tudi kot 10 črtic: \(||||||||||\). Za majhna števila je to še mogoče, za velika števila pa je to vsekakor zelo neučinkovito. Da bi število na ta način zapisali, bi trajalo veliko časa, še več pa bi ga porabili, ko bi ga želeli prebrati. Tak zapis pa vzame tudi veliko prostora na papirju. Za število \(10^6\) bi porabili kakšen list papirja, večina pa bi nas že okoli 100 obupala. Nekoliko boljši zapis števil je s petericami (tj. s po pet črticami skupaj, štiri napišemo z zadnjo pa jih prečrtamo): \(||||\!\!\!\!\!\!\mbox{---}\). Pri zapisu s peticami pa na vsakih 10 črtic za dve črtici prostora prihranino, kar pomeni, da je zapis za 1/5 krajši od prejšnjega. S tem zapisom bi namesto pri 100 obupali pri okoli 120. To pa ni velika izboljšava.

Morda ste že opazil, da nas zanima učinkovitost zapisa glede na njegovo dolžino. Rimljani so uporabljali rimske številke I, II, III, IV, V,. . . Takšen zapis števila je prostorsko veliko manj potraten kot črtice ali peterice. Na primer za število 100 potrebujemo le en znak - C. A še vedno je manj učinkovit kot zapis, ki ga danes uporabljamo. Število 1999 bi z rimskimi številkami napisali kot: MCMLXLIX.

Slika1

slike/rim.jpg

Arabske številke (to so številke kot jih poznamo danes) so Arabci le razširili po svetu, izumili pa so jih feničanski trgovci, da so lahko šteli in zapisovali svoje trgovske račune. Domnevno vsaka številka predstavlja natanko toliko kotov, kolikor je njena vrednost. Kar lepo vidi iz poenostavljenih oblik številk:

Slika2

slike/stevkeInKoti.jpg

Pravijo, da uporabljamo desetiški sistem, zato ker imamo na roki 10 prstov. Vendar pa je desetiški sistem, zelo učinkovit za zapis števil. Če bi tudi mi uporabljali dvojiški sistem, tako kot ga računalniki, bi za zapis in branje števila \(10=1010_2\) ponovno porabili več časa in tudi prostora na papirju. Podobno je s preostalimi številskimi sistemi. V desetiškem sistemu pa enostavno in učinkovito zapišemo število od desne proti levi, najprej s številom enic nato desetic, stotic, tisočic itd. Naj bo \(n\) število, ki ga zapisujemo in \(k\) dolžina zapisa. Pri zapisu z enicami je \(k\) kar enako \(n\). Za dvojiški sistem velja, da je \(k = \lfloor \log_2 n\rfloor\), za desetiškega pa podobno: \(k=\lfloor\log_{10} n\rfloor\). Z zapisom dolžine \(k\), se da zapisati eksponentno mnogo števil (koliko je to, si lahko ogledaš v Mi pa se bomo raje posvetili učnikovitosti računskih operacij, glede na dolžino zapisa \(k\).

Deljivost

Število \(a\) je s številom \(n\), če je \(a\) večkratnik števila \(n\), tj. \(a\in \{\dots ,-2n,-n,0,n,2n, \dots\}\). Pravimo tudi, da \(n\) število \(a\) in zapišemo \(n\,|\,a\) oziroma, da je \(n\) delitelj števila \(a\).

Zanima nas problem: katera naravna števila delijo \(a\ge 0\). Za začetek si oglejmo eno samo deljenje. Pri deljenju števila \(a\) s številom \(n\) iščemo celoštevilčni kvocient, tj. \(q=\lfloor a/n \rfloor\), ki nam pove kolikokrat gre \(n\) v \(a\).

Začnemo s \(q:=0\). Če je \(a<n\), ima kvocient \(q\) že pravo vrednost, sicer pa nadomestimo število \(a\) z \(a:=a-n\), kvocient \(q\) pa povečamo za \(1\) in se ponovno vprašamo ali je \(a<n\). Če je odgovor DA, že imamo pravi \(q\) (trenutna vrednost kvocienta \(q\)), sicer pa postopek z odštevanjem ponovimo …

Ker se v zgornjem algoritmu število \(a\) na vsakem koraku zmanjša, bomo po končnem številu korakov prišli do pravega kvocienta. Problem pa je, da je ta algoritem precej počasen, če je število \(n\) majhno v primerjavi z \(a\). Glede na velikost \(k\) števila \(a\) je algoritem eksponenten. Ker je razlika v velikosti dveh števil zelo očitna iz samega zapisa števil, se da zgornji algoritem precej pohitriti. Premislite sami kako in šele nato nadaljujte z branjem. Tako kot so nas učili v osnovni šoli:

številu \(a\) odštevamo večkratnike števila \(n\) pomnožene s čimvečjo števko in čimvečjo potenco osnove sistema v katerem delamo (običajno 10), tako da na vsakem koraku zmanjšamo število \(a\) za vsaj eno mesto.

Novi algoritem ni več eksponenten temveč le še kvadraten glede na \(k\).

Ko imamo enkrat kvocient \(q=\lfloor a/n \rfloor\), lahko izračunamo še ostanek pri deljenju \(r\): \[ r=a-qn <n. \] Deljenje števila \(a\) z naravnim številom \(n\) se izide natanko tedaj, ko je \(r=0\). Od tod izpeljemo prvi postopek za iskanje deliteljev:

Za dano naravno število \(a\) in za vsak \(n \in \{1,\dots,a\}\) iščemo ostanek~\(r\) pri deljenju \(a:n\). Če je \(r=0\), potem dodaj število \(n\) k deljiteljem števila \(a\).

Omenjeni postopek je pravilen, saj res najde vse deljitelje števila \(a\). Vendar pa ni učinkovit. Si predstavljate, kako bi bilo, če bi vsakič, ko bi iskali deljitelje števila \(a\), morali vedno znova preveriti vsa naravna števila do vključno števila \(a\)? Verjetno zelo izčrpljujoče in dolgočasno. Rešitev je torej očitno res izčrpna. Pa tudi naivna in požrešna, saj vemo, da je večina večjih števil sestavljena iz manjših (z izjemo praštevil), in nam ni potrebno preveriti prav vseh naravnih števil manjših od \(a\). Izkaže se, da je dovolj, da preverimo števila manjša od \(\sqrt{a}\). S tem smo že našli naslednji, učinkovitejši postopek za dani problem:

Za dano naravno število \(a\) in za vsak \(n\in\{1,\dots,\lfloor\sqrt{a}\rfloor\}\) iščemo ostanek~\(r\) pri deljenju \(a:n\).
Če je \(r=0\), potem dodaj števili \(n\) in \(a/n\) k deljiteljem števila \(a\).

V šoli nas učijo o deljivosti precej zgodaj. Celo tako zgodaj, da ne poznamo drugega kot desetiški sistem. Spomnimo se, da je število deljivo z:

• \(2\) natanko tedaj, ko se končuje s sodo števko (v sistemu pri osnovi \(2\) pa je taka samo števka \(0\)),

• \(3\) oziroma \(9\) natanko tedaj, ko je vsota števk deljiva s \(3\) oziroma \(9\),

• \(4\) natanko tedaj, ko je število sestavljeno iz zadnjih dveh števk deljivo s \(4\),

• \(5\) natanko tedaj, ko se končuje z \(0\) ali \(5\),

• \(6\) natanko tedaj, ko je deljivo z \(2\) in \(3\),

• \(8\) natanko tedaj, ko je število sestavljeno iz zadnjih treh števk deljivo s \(8\),

• \(10\) natanko tedaj, ko se končuje z \(0\),

• \(11\) natanko tedaj, ko je razlika vsote sodih in lihih števk enaka \(0\).

Opremljeni s temi pravili in morda še kakšno njihovo kombinacijo \((4,6,9,10,12,15,\dots)\), se spomnimo našega problema iz začetka članka. Omenjena postopka za iskanje deljiteljev števila \(a\) sta do sedaj uporabila le malo našega znanja. Izkoristila sta dejstvo, da se deljenje izide, če je ostanek enak \(0\), in pa dejstvo, da je večina večjih naravnih števil sestavljenih, ter je zato dovolj pregledati le naravna števila manjša od \(\sqrt{a}\). S pravili o deljivosti naravnih števil, pa lahko postopek še malo izboljšamo:

Naredimo si tabelo naravnih števil od 1 do \(\sqrt{a}\), nato si označujemo števila, ki so deljitelji:

Število \(a\) je deljivo s \(2\), če se končuje s sodo števko.

Število \(a\) je deljivo s \(3\), če je vsota števk deljiva s \(3\).

Število \(a\) je deljivo s \(4\), če je število, ki je sestavljeno iz zadnjih dveh števk od \(a\) deljivo s~\(4\).

Število \(a\) je deljivo s \(5\), če se končuje z \(0\) ali s \(5\).

Število \(a\) je deljivo s \(6\), če je deljivo z \(2\) in s \(3\).

Število \(a\) je deljivo s \(7\), če je ostanek pri deljenju s \(7\) enak \(0\).

Število \(a\) je deljivo s \(8\), če je deljivo z \(2\) in s \(4\).

Število \(a\) je deljivo s \(9\), če je vsota števk deljiva z \(9\).

Postopek je učinkovitejši od prejšnih, saj zelo malokrat (le za praštevila za katera nimamo posebnega kriterija povezanega s števkami) izračunamo ostanek pri deljenju, večinoma pa le preverjamo, ali držijo pravila o deljivosti.

Tako pričnemo razcepljati števila, a kmalu ugotovimo, da je dobro imeti tabelo praštevil, saj moramo vedeti, katera od njih delijo število \(a\). Naštejmo prvih 100 (ki jih lahko dobimo peš z Erastotenovim rešetom ali pa z enostavim ukazom {seq(ithprime(i),i=1..100)} npr. v MAPLE:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, \(\dots\)

Ostanki pri deljenju

Še enkrat ponovimo, da je število \(a\) deljivo s številom \(b\) natanko tedaj, ko je ostanek pri deljenju \(a\) z \(b\) enak \(0\). Pravilo o deljivosti s številom \(2\) nam torej pravi, da je ostanek pri deljenju \(a\) z \(2\) enak \(0\), ko je zadnja števka števila \(a\) soda. Sicer pa je ostanek \(1\). Pravilo o deljivosti s številom 10, nam pove, da je ostanek 0, če se zadnja števka števila \(a\) konča z 0. Vse ostale zadnje števke, pa nam že povedo ostanek pri deljenju z \(10\). Možni ostanki pri deljenju z 10 so torej \(0,1,2,3,4,5,6,7,8,9\). Iz pravila o deljivosti z 11 sledi, da ima poljubno naravno število pri deljenju z \(11\) enak ostanek kot razlika vsote števk na sodih mestih in vsote števk na lihih mestih.

Počasi že sumimo, da so možni ostanki naravnega števila \(a\) z naravnim številom \(n\), vedno vsa naravna števila \(b\) taka, da \(0\leq b \leq n-1\). Za primer si oglejmo ostanke pri deljenju s 5. Iz pravila o deljivosti vemo, da je ostanek 0, če se zadnja števka števila konča z 0 ali 5. Če pa se konča s števili \(1,2,3,4\), nam ta števila že predstavljajo ostanek pri deljenju. Kaj pa, če se število konča s števili \(6,7,8,9\)?

Izračunamo si ostanke:

• \(6:5=1\) ostane \(6-5=1\)
• \(7:5=1\) ostane \(7-5=2\)
• \(8:5=1\) ostane \(8-5=3\)
• \(9:5=1\) ostane \(9-5=4\)

Opazimo, da so možni ostanki pri deljenju s 5: \(0,1,2,3,4\).

Praštevilu \(7\) osnova \(10\) očitno ni naklonjena, več sreče imamo pri osnovi \(8\). Če privzamemo, da je število \(2012\) zapisano v binarni obliki (v osnovi \(2\)), ki je običajna za računalnike, potem izgleda takole: \[ \begin{array}{ccc} 2012 &=& 2^{10}+ 2^{9}+ 2^{8}+ 2^{7}+ 2^{6}+ 2^{4}+ 2^{3} +2^2 \\[1mm] &=& 11.111.011.100_2, \end{array} \] kar se da hitro spremeniti v zapis pri osnovi \(8\): \(3734_8\) (vsaka tri mesta, ki so ločena s pikami, ustrezajo eni števki).

Če seštejemo vse števke: \(11_2+111_2+11_2+100_2=10.001_2\) oziroma \(21_8\) in to še enkrat ponovimo za pravkar izračunano število: \(10_2+1_2=11_2\) oziroma \(3_8\), dobimo \(3\), kar je v resnici ostanek števila \(2012\) pri deljenju s \(7\).

Sedaj pa si natančneje oglejmo pravilo o deljivosti s \(3\) oziroma z \(9\)

Splošno število v desetiškem sistemu zapišimo tako, da začnemo pri enicah \[ a = a_0 + 10a_1 + 100a_2 + 1000a_3 + \cdots \] kar lahko zapišemo tudi kot:

\[ \begin{array}{ccc} a &=& a_0 + (a_1 + 9a_1) + (a_2 + 99a_2) + (a_3 + 999a_3) + \dots \\[2mm] &=& (a_0 + a_1 + a_2 + a_3 + \cdots) + 9(a_1 + 11a_2 + 111a_3 +\dots). \end{array} \]

Drugi člen te vsote je gotovo deljiv tako s \(3\) kot z \(9\). Če je deljiv s 3 oziroma z 9 tudi prvi člen, je število deljivo s \(3\) oziroma z \(9\). Prvi člen pa je ravno vsota vseh števk danega števila.

Iz tega sledi, da ima vsako naravno število pri deljenju s \(3\) (ali \(9\)) enak ostanek kot vsota števk pri osnovi 10 (ki je ravno za ena večja od večkratnika števila \(3\) oziroma od števila \(9\)). Če delimo s \(3\) so možni ostanki \(0,1,2\), pri deljenju z \(9\) pa \(0,1,2,3,4,5,6,7,8\).

6.2 Računala nove dobe

Ste že kdaj razmišljali o računanju (aritmetiki), ki ga uporabljamo v vsakdanjem življenju? Večina ljudi jo zamenjuje kar za celotno matematiko. Na kakšen način računajo računalniki ter ostale digitalne naprave (digit je angl. beseda za število), ki nas obkrožajo v času informacijske dobe? Nekateri se sicer skušajo prilagajati našemu načinu računanja, vse več pa je takih, ki so jim časovna in prostorska učinkovitost ter preciznost ključnega pomena. Take naprave računajo na malce drugačen način. V tem sestavku se bomo poskusili s pomočjo osnovnošolskega računanja približati računalom, ki jih preko številnih naprav, kot so osebni računalniki, diskmani in pametne kartice, uporabljamo v vsakdanji praksi.

Vsi poznamo tabeli za seštevanje in množenje (tabela 1).

Tabela 1a

\[ \begin{array}{|r|cccccccccccc} \hline + & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots &\\[0mm] \hline 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots &\\[0mm] 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots &\\[0mm] 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & \dots &\\[0mm] 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & \dots &\\[0mm] 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & \dots &\\[0mm] 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots &\\[0mm] 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & \dots &\\[0mm] 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & \dots &\\[0mm] 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & \dots &\\[0mm] 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & \dots &\\[0mm] \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \cr \end{array} \]

1. tablica za seštevanje,

Tabela 1b

\[ \begin{array}{|r|cccccccccccc} \hline * & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots &\cr \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots &\cr 2 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & \dots &\cr 3 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 & \dots &\cr 4 & 4 & 8 & 12 & 16 & 20 & 24 & 28 & 32 & 36 & 40 & \dots &\cr 5 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & \dots &\cr 6 & 6 & 12 & 18 & 24 & 30 & 36 & 42 & 48 & 54 & 60 & \dots &\cr 7 & 7 & 14 & 21 & 28 & 35 & 42 & 49 & 56 & 63 & 70 & \dots &\cr 8 & 8 & 16 & 24 & 32 & 40 & 48 & 56 & 64 & 72 & 80 & \dots &\cr 9 & 9 & 18 & 27 & 36 & 45 & 54 & 63 & 72 & 81 & 90 & \dots &\cr 10 & 10 & 20 & 30 & 40 & 50 & 60 & 70 & 80 & 90 & 100 & \dots &\cr \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \cr \end{array} \]

2. tablica za množenje.

Drugi tabeli pravimo poštevanka in se jo morajo drugošolci od nekdaj naučiti na pamet ter si jo zapomniti za celo življenje. Seveda si ni potrebno zapomniti vseh 100 zmnožkov; večkratniki števil 1 in 10 so otročje lahki, množenje z 2 ni nič težje kot seštevanje, vrstni red pri množenju ni prav nič pomemben (zakon o zamenjavi ali komutativnost) (tabela 2).

Tabela 2a

1. Ploščina pravokotnika s stranicama \(a\) in \(b\) je enaka tako \(ab\), kakor tudi \(ba\). Enkrat štejemo kvadratke po vrsticah, drugič pa po stolpcih.

Tabela za poštevanko je simetrična glede na diagonalo, torej si je potrebno zapomniti le približno tretjino produktov. Omenimo še dve bližnjici.

Večkratniki števila 9: Koliko je \(9 \times 7\)? Uporabimo metodo računanja s prsti. Ne vzamemo predse žepnega računala, temveč potegnemo iz žepov deset prstov. Ker gre za sedemkratnik števila devet, pripognemo sedmi prst z leve in odčitamo: šest (6) prstov na levi ter trije (3) na desni in že vemo, da je pravilen odgovor \(63\).

Večkratniki števila 11: Koliko je \(11 \times 13\)? Zelo enostavno! Enico in trojko razmaknemo, med njiju pa zapišemo njuno vsoto in že dobimo iskani produkt \(143\).

Ko končno obvladamo tablico množenja, ni več težko zmnožiti poljubnih števil (zapisanih v desetiškem zapisu), saj množimo le posamezne števke in nato samo še seštevamo (tabela 3).

Tabela 3

1. France Križanič v svoji knjigi “Križem po matematiki” predstavi indijski način množenja s pomočjo pravokotne mreže, razdeljene v kvadrate. Vsaki števki prvega faktorja pripada po en stolpec, vsaki števki drugega faktorja pa ena vrsta kvadratkov. V vsak kvadratek zapišemo produkt obeh števil, ki pripadata stolpcu in vrsti, v kateri je kvadratek. Desetice tako dobljenega produkta zapišemo v levi zgornji kot, enice pa v spodnji desni kot. Ko so vpisani vsi produkti, je potrebno le še sešteti števila v smeri diagonal in že dobimo produkt.

Če pa bi računali v petiškem zapisu ali celo dvojiškem, bi bila matematika v drugem razredu veliko lažja (tabela 4).

Tabela 4a (a) tabela za množenje v petiškem sistemu,

\[ \begin{array}{|r|cccccc} \hline * & 1_5 & 2_5 & 3_5 & 4_5 & 10_5 & \dots \cr \hline 1_5 & 1_5 & 2_5 & 3_5 & 4_5 & 10_5 & \dots \cr 2_5 & 2_5 & 4_5 & {11_5} & {13_5} & 20_5 & \dots \cr 3_5 & 3_5 & 11_5 & {14_5} & {22_5} & 30_5 & \dots \cr 4_5 & 4_5 & 13_5 & 22_5 & {31_5} & 40_5 & \dots \cr 10_5 & 10_5 & 20_5 & 30_5 & 40_5 & 100_5 & \dots \cr \vdots &\vdots&\vdots & \vdots & \vdots & \vdots& \ddots\cr \end{array} \]

Tabela 4b

\[ \begin{array}{|r|ccc} \hline * & 1_2 & 10_2 & \dots \cr \hline 1_2 & 1_2 & 10_2 & \dots \cr 10_2 & 10_2 & 100_2 & \dots \cr \vdots & \vdots & \vdots & \ddots\cr \end{array} \ \ \ \ \ \ \ \ \begin{array}{|r|ccc} \hline + & 0_2 & 1_2 & \dots \cr \hline 0_2 & 0_2 & 1_2 & \dots \cr 1_2 & 1_2 & 10_2 & \dots \cr \vdots& \vdots & \vdots & \ddots\cr \end{array} \]

2. tabela za množenje v dvojiškem sistemu,
3. tabela za seštevanje v dvojiškem sistemu.

V prvem primeru bi si bilo potrebno zapomniti le 6 zmnoškov, v drugem pa pravzaprav nobenega. Prav zato običajno računalniki računajo račune v dvojiškem sistemu. Pred njimi pa so tako računali že Indijanci. Ko so npr. želeli izračunati \(15\times 13\), so enega izmed faktorjev zapisali kot vsoto potenc števila 2, npr. \(13=1+4+8\), tj. v dvojiškem sistemu \(1101_2\), in nato drugega le množili z dve in seštevali (tabela 5a). Če je tudi drugo število zapisano v dvojiškem sistemu, tj. \(15=1+2+4+8=1111_2\), potem je množenje z dve doseženo na prav enostaven način: na koncu števila je potrebno pripisati ničlo (tabela 5b) in že dobimo \(11000011_2 = 128+64+2+1=195\).

Tabela 5

\[ 15 \times 1 \ = \ \ 15 \] \[ 30 \times 0 \ = \ \ \ 0 \] \[ 60 \times 1 \ = \ \ \! 60 \] \[ 120 \times 1 \ = 120 \] \[ 195 \]

\[ 1111_2 \times 1 = 1111_2 \] \[ 11110_2 \times 0 = 0_2 \] \[ 111100_2 \times 1 = 111100_2 \] \[ 1111000_2 \times 1 = 1111000_2 \] \[ 11000011_2 \]

Naloge

1. Poišči še kakšno zanimivo pravilo za množenje (kot sta bili pravili za računanje večkratnikov števil 9 in 11). Če ne gre v desetiškem sistemu, pa poskusi v katerem drugem sistemu.

Grupe in obsegi

Poleg seštevanja in množenja pa se v prvih razredih osnovne šole naučimo tudi odštevati in deliti. Seveda začnemo najprej odštevati manjša števila od večjih. Pri tem si lahko pomagamo s tabelo 1a. Če želimo izračunati \(a-b\) in je \(a\ge b\), se lahko vprašamo \[ \mbox{$b$ plus koliko je $a$}? \] To pomeni, da pogledamo v vrstico, ki ustreza številu \(b\), iskano razliko pa najdemo na vrhu stolpca, ki ustreza številu \(a\) iz te vrstice. Za razliko \(14-5\) poiščemo v peti vrstici število \(14\). Najdemo ga na osmem mestu in zato vemo, da je razlika enaka \(9\). Šele nekoliko kasneje se naučimo, da moramo v primeru, ko želimo odšteti večje število od manjšega, števili najprej zamenjati, na koncu pa dobljeni razliki spremeniti predznak. Zaradi tega smo povečali množico naravnih števil \(\mathbb{N}=\{1,2,\dots \}\) do množice celih števil \(\mathbb{Z}=\{\dots ,-2,-1,0,1,2,\dots \}\).

Deljenje ni tako preprosto. Če želimo \(a\) deliti z \(b\), se lahko prav tako kot prej vprašamo “\(b\) krat koliko je \(a\)?” Vendar ni gotovo, da bomo v vrstici, ki ustreza številu \(b\), našli število \(a\). Pogosto se namreč zgodi, da število \(a\) ni deljivo s številom \(b\). Množico števil lahko sicer povečamo do množice ulomkov \(\mathbb{Q}\), kjer se da deliti s poljubnim od nič različnim številom, a potem nastopijo druge težave. Najdemo lahko različne ulomke, ki so si poljubno blizu, tudi tako blizu, da jih računalnik ne more več ločiti. Ker pa si želimo, da bi se računalniki čim manj motili, se vprašajmo po množicah, v katerih bi lahko brez problemov tudi delili, po možnosti na enak način kot znamo odštevati. Da bi bilo to mogoče, se morajo v vsaki vrstici tabele pojaviti vsa od nič različna števila. Pravzaprav se je potrebno vprašati, na katera pravila se želimo pri računanju opreti. Naštejmo jih nekaj.

1. Običajno je prvo pravilo zaprtost, rezultat, ki ga dobimo po opravljeni operaciji med dvema številoma, je tudi v množici, iz katere smo izbrali števili. Množica naravnih števil je zaprta za seštevanje in množenje, saj v tabelah 1a in 1b nastopajo samo naravna števila. Ni pa množica naravnih števil zaprta za odštevanje. To lastnost ima na primer množica celih števil.

2. V množici celih števil igra pomembno vlogo število \(0\); pa ne samo zato, ker loči pozitivna števila od negativnih, pač pa tudi zato, ker se nobeno število s prištevanjem števila \(0\), ne spremeni. Tudi pri množenju najdemo nekaj podobnega. Če pomnožimo katerokoli od nič različno število z \(1\), dobimo zopet isto število. Takemu številu pravimo nevtralni element ali pa tudi enota za ustrezno operacijo.

3. V množici celih števil sta poljubni števili \(-a\) in \(a\) povezani z enoto za seštevanje na naslednji način: \(a+(-a)=0\). Pravimo, da je \(-a\) nasprotni element števila \(a\). Celo število \(b\) je obratni element celega števila \(a\), če je \(ab=1\). Od tod sledi \(a=b=1\), tj. v množici celih števil imata le števili \(1\) in \(-1\) obratni element.

4. Če si izberemo poljubna števila \(a\), \(b\) in \(c\), potem velja \[ a+(b+c)=(a+b)+c \ \ \ \ \ \mbox{in} \ \ \ \ \ a(bc)=(ab)c. \] O drugi enakosti se lahko prepričamo z računanjem prostornine kvadra s stranicami \(a\), \(b\) in \(c\). Tem lastnostim pravimo zakon o združevanju za seštevanje oziroma za množenje (ali tudi asociativnost). Le-ta nam pove, da je vseeno, ali začnemo računati z leve ali z desne. To seveda ne drži za odštevanje ali deljenje.

Če v neki množici \(G\) z binarno (dvočleno) operacijo \(\circ\), tj. operacijo, ki vsakemu urejenemu paru elementov iz \(G\) priredi natanko določen element, veljajo naslednja pravila:

(G1) za vsaka \(a,b\in G\) je \(a\circ b \in G\),

(G2) obstaja tak element \(e\in G\), da za vsak \(g\in G\) velja \(e\circ g = g\circ e = g\),

(G3) za vsak element \(g\in G\) obstaja tak \(f\in G\), da je \(g\circ f = f \circ g = e\),

(G4) za vse \(a,b,c \in G\) velja \((a\circ b)\circ c = a\circ (b\circ c)\),

potem pravimo, da je par \((G,\circ)\) grupa. Elementu \(e\) pravimo enota grupe, elementu \(f\) pa inverz elementa \(g\). Množica celih števil je grupa za seštevanje, ni pa grupa za množenje, saj ni izpolnjeno pravilo (G3) (le 1 in -1 imata inverzni element za množenje).

Morda bo kdo pomislil, da je prišla definicija grupe iz glave enega samega matematika, pa temu sploh ni tako. Matematiki so potrebovali več kot 100 let trdega dela, da so končno (eksplicitno) zapisali zgornja pravila (aksiome). Joseph Louis Lagrange (1736-1813) je leta 1771 postavil prvi pomembnejši izrek. Augustin Louis Cauchy (1789-1857) je študiral grupe permutacij, medtem, ko je Niels Henrik Abel (1802-1829) s teorijo grup pokazal, da enačba 5. stopnje ni rešljiva z radikali (tj. rešitve ne znamo zapisati s formulami kot v primeru enačb nižjih stopenj). Po njem pravimo grupam, v katerih velja pravilo zamenjave, tudi Abelove grupe (ali komutativne grupe). Pravi pionir abstraktnega pristopa pa je bil Evariste Galois (1811-1832),
ki je leta 1823 prvi uporabil besedo “grupa”. Vač o njem si lahko preberete v Preseku 29 (’01-02), str. 346-349. Proces poudarka na strukturi se je nadaljeval vse do leta 1854, ko je Arthur Cayley (1821-1895)
pokazal, da je grupo moč definirati ne glede na konkretno naravo njenih elementov.

Galois je vpeljal tudi naslednji pojem. Če za neko množico \({\cal O}\) z binarnima operacijama, ki ju bomo označili s + in \(*\) (četudi ne predstavljata nujno običajnega seštevanja in množenja), velja

(O1) par \(({\cal O},+)\) je grupa z enoto \(0\),

(O2) par \(({\cal O}\backslash\{0\},*)\) je grupa z enoto \(1\),

(O3) za vse \(a,b,c\in {\cal O}\) je \(a*(b+c)=a*b+b*c\) in \((b+c)*a=b*a+c*a\),

potem imenujemo trojico \(({\cal O},+,*)\) obseg. Množica ulomkov z običajnim seštevanjem in množenjem je primer obsega. O lastnosti (O3), ki jo imenujemo zakon o razčlenjevanju oziroma distributivnost, se lahko prepričamo z računanjem površine pravokotnika s stranicama \(a\) in \(b+c\).

Bertrand Russell je povzel moderen abstrakten pristop v svojem slavnem citatu,

Matematiko lahko definiramo kot predmet, pri katerem nikoli ne vemo, o čem govorimo niti nikoli ne vemo, ali je tisto, kar pravimo, resnično.

Če smo šli za koga prehitro, potem mu priporočamo Križaničevo knjižico Ukročena matematika, Presek 8/5 (1980-81). Ker smo zajadrali v bolj abstraktne vode, pred nadaljevanjem zastavimo še nekaj nalog.

2. Poznamo še veliko grup, ki ne izhajajo iz množice števil s seštevanjem ali pa množenjem. Poišči še kakšne množice z binarnimi operacijami in preveri katera izmed pravil (G1)-(G4) veljajo zanje. Zanimiva množica so simetrije določenega geometrijskega objekta, npr. enakostraničnega trikotnika ali pa kocke. Kakšno binarno operacijo bi vpeljali med simetrije, da bi dobili grupo? Spet druga zanimiva množica so funkcije. Kaj pa lahko rečemo o preseku in uniji množic?

3. Pokaži, da v grupi velja \((a\circ b)^{-1}=b^{-1}\circ a^{-1}\).

4. Prepričaj se, da je v poljubni grupi \(G\) za vsaka \(a,b\in G\) rešljiva enačba \(a\circ x=b\).
   Poišči nekaj najmanjših grup (glede na število elementov). Kako jih lahko najlažje predstaviš?

5. Poišči najmanjši obseg.

Najmanjše grupe in obsegi

Za cilj postavimo iskanje obsega s končno mnogo elementi, v katerem bo računanje v nekem smislu še udobnejše kot v obsegih, ki jih srečamo v osnovni ali srednji šoli (racionalna števila \(\mathbb{Q}\), realna števila \(\mathbb{R}\) ali celo kompleksna števila \(\mathbb{C}\)).

Gotovo ste hitro ugotovili, da mora imeti grupa zaradi aksioma (G2) vsaj en element, enoto \(e\) namreč, obseg pa vsaj dva, enoto za operacijo “\(+\)” in enoto za operacijo “\(*\)”. Potem se ni več težko prepričati, da je en element v primeru grupe že dovolj, saj nam \(e\circ e=e\) zadovolji vse aksiome (G1)-(G4). V primeru obsega z dvema elementoma je enako z multiplikativno grupo: \(1*1=1\) zadovolji aksiom (O2). Ne pozabite, da operaciji “\(+\)” in “\(*\)” ne predstavljata (nujno) običajnega seštevanja in množenja. V tem sestavku bomo spoznali kar nekaj takih obsegov. V vsakem obsegu je produkt poljubnega elementa \(a\) z aditivno enoto \(0\) enak \(0\), saj je \(0*a=(0+0)*a=0*a+0*a\) (upoštevali smo (G2) in (O3)) in po krajšanju z \(0*a\) res dobimo \(0*a=0\). Opozoriti je treba, da pravilo krajšanja velja v poljubni grupi, saj v resnici na obeh straneh “dodamo” inverzni element in nato upoštevamo zakon o združevanju (G4) ter (G2) (do tega ste se gotovo dokopali že sami pri reševanju 3. naloge iz prejšnjega razdelka). Seveda velja enako tudi, kadar vrstni red zamenjamo: \(a*0=0\). Torej tudi v primeru najmanjšega obsega velja \(0*0=0\) in \(0*1=0=1*0\), kjer je \(1\) multiplikativna enota. Kako pa je z grupo, ki ima dva elementa, npr. enoto \(e\) in \(a\)? Poleg \(e\circ e=e\) in \(e\circ a=a=a\circ e\) mora zaradi aksioma (G3), pravila krajšanja in \(e\ne a\) veljati še \(a\circ a=e\) in že so izpolnjeni vsi aksiomi (G1)-(G4). Torej velja za obseg z dvema elementoma in pravkar odkrito aditivno grupo tudi aksiom (O1). Zlahka preverimo še (O3) in že smo ugnali tudi najmanjši obseg.

Vrnimo se k vprašanju, koliko informacij potrebujemo za določitev grupe kot matematičnega objekta. Odgovor na to vprašanje je dal leta 1854 Arthur Cayley. Po analogiji s tablico množenja je vpeljal tablico za poljubno binarno operacijo, ki ji bomo rekli komponiranje. Elemente množice \(G\), v kateri je definirano komponiranje, razporedimo v zgornjo vrstico tablice in v enakem vrstnem redu še v levi stolpec tablice (imenovali ju bomo koordinatna vrstica in stolpec). Končno pa v polja tablice vpišemo ustrezne kompozitume. Za zgornje primere glej tabeli 6a in 6b.

Najmanjši obseg ima dva elementa, tablici za njegovi operaciji pa sta naslednji:

Tabela 6

\[ \begin{array}{|c|cc|} \hline + & 0 & 1 \cr \hline 0 & 0 & 1 \cr 1 & 1 & 0 \cr \hline \end{array} \quad \quad \quad \begin{array}{|c|cc|} \hline * & 0 & 1 \cr \hline 0 & 0 & 0 \cr 1 & 0 & 1 \cr \hline \end{array} \]

1. seštevanje,
2. množenje.

Gotovo ste opazili, da je \(1+1=0\). V naslednjem razdelku bo postalo jasno, da ne gre za napako. Omeniti moramo le še, da pri iskanju grupe z enim in dvema elementoma sploh nismo imeli izbire pri določanju tablice, pri grupi s štirimi elementi pa obstajata že natanko dve različni grupi (ena ustreza grupi simetrij pravokotnika, drugo pa boste spoznali v naslednjem razdelku).

Praštevilski obseg \(\mathbb{Z}_p\)

Namesto s celimi števili bomo tokrat računali z ostanki pri deljenju s 13, tj. z elementi iz množice \(\mathbb{Z}_{13}= \{0,1,\dots,12\}\). V tem primeru računamo na naslednji način: števili seštejemo ali zmnožimo tako, da običajni rezultat nadomestimo z njegovim ostankom pri deljenju z modulom \(13\). Na primer \(7+_{\scriptsize 13}9=7+9 \mod 13 =3\) in \(5*_{\scriptsize 13}4= 5* 4\mod 13 =7\), saj ima pri deljenju s 13 vsota 16 ostanek 3, produkt 20 pa ostanek 7, glej tabeli 7a, 7b in sliko 1.

Slika 1

1. Računanje po modulu 13 je podobno kot pri številčnici na uri.

Tabela 7a

\[ \begin{array}{|r|ccccccccccccc|} \hline +_{\scriptsize 13} & 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12 \cr \hline 0& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12 \cr 1& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 0 \cr 2& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 0& 1 \cr 3& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 0& 1& 2 \cr 4& 4& 5& 6& 7& 8& 9& 10& 11& 12& 0& 1& 2& 3 \cr 5& 5& 6& 7& 8& 9& 10& 11& 12& 0& 1& 2& 3& 4 \cr 6& 6& 7& 8& 9& 10& 11& 12& 0& 1& 2& 3& 4& 5 \cr 7& 7& 8& 9& 10& 11& 12& 0& 1& 2& 3& 4& 5& 6 \cr 8& 8& 9& 10& 11& 12& 0& 1& 2& 3& 4& 5& 6& 7 \cr 9& 9& 10& 11& 12& 0& 1& 2& 3& 4& 5& 6& 7& 8 \cr 10& 10& 11& 12& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9 \cr 11& 11& 12& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10 \cr 12& 12& 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11 \cr \hline \end{array} \]

1. seštevanje po modulu 13,

Tabela 7b

\[ \begin{array}{|r|c|cccccccccccc|} \hline *_{\scriptsize 13}\!\! & 0& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\cr \hline 0 & 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\cr \hline 1 & 0&{1}& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12\cr 2 & 0& 2& 4& 6& 8& 10& 12&{1}& 3& 5& 7& 9& 11\cr 3 & 0& 3& 6& 9& 12& 2& 5& 8& 11&{1}& 4& 7& 10\cr 4 & 0& 4& 8& 12& 3& 7& 11& 2& 6& 10&{1}& 5& 9\cr 5 & 0& 5& 10& 2& 7& 12& 4& 9&{1}& 6& 11& 3& 8\cr 6 & 0& 6& 12& 5& 11& 4& 10& 3& 9& 2& 8&{1}& 7\cr 7 & 0& 7&{1}& 8& 2& 9& 3& 10& 4& 11& 5& 12& 6\cr 8 & 0& 8& 3& 11& 6&{1}& 9& 4& 12& 7& 2& 10& 5\cr 9 & 0& 9& 5&{1}& 10& 6& 2& 11& 7& 3& 12& 8& 4\cr 10 & 0& 10& 7& 4&{1}& 11& 8& 5& 2& 12& 9& 6& 3\cr 11 & 0& 11& 9& 7& 5& 3&{1}& 12& 10& 8& 6& 4& 2\cr 12 & 0& 12& 11& 10& 9& 8& 7& 6& 5& 4& 3& 2& {1}\cr \hline \end{array} \]

2. množenje po modulu 13.

Če želimo sešteti ali pa zmnožiti tri števila iz \(\mathbb{Z}_{13}\), potem lahko pridemo do enakega rezultata tudi tako, da jih najprej seštejemo ali zmnožimo kot običajna cela števila in šele nato poiščemo ostanek pri deljenju z modulom. Zakoni o združevanju (asociativnost) celih števil za seštevanje, množenje in razčlenjevanje (distributivnost) nam torej zagotavljajo veljavnost zakonov o združevanju za seštevanje, množenje in razčlenjevanje po modulu.

Pozoren bralec bo opazil, da se v vsakem stolpcu in v vsaki vrstici tablice za seštevanje nahajajo prav vsi elementi iz \(\mathbb{Z}_{13}\). Podobno velja tudi za tablico množenja, če odmislimo vse ničle. Če bi 13 nadomestili s 14, potem tablica množenja po modulu 14 ne bi imela te lastnosti (le-ta je rezervirana samo za praštevila). Torej lahko v tablicah za seštevanje in množenje najdemo tudi razlike in kvociente. Na primer če želimo izračunati \(2:_{\scriptsize 13}7\), se vprašamo: 7 krat koliko je 2. V tablici množenja (tabela 7b) si izberemo vrstico, ki ustreza številu 7 in ugotovimo, da se število 2 nahaja v stolpcu, ki ustreza številu 4. Zato zaključimo, da je \(2:_{\scriptsize 13}7=4\). Do enakega zaključka bi prišli tudi, če bi številu 2 prišteli 13 tolikokrat, da bi dobljena vsota postala deljiva s 13 in nato bi izračunali kvocient. Pripomnimo, da se ne da izračunati \(2:_{\scriptsize 14} 7\), torej \(2:14\) v množici \(\mathbb{Z}_{14}\). Zakaj?

Sedaj se ni več težko prepričati, da je trojica \((\mathbb{Z}_{13},+_{\scriptsize 13},*_{\scriptsize 13})\) obseg. Prav tako hitro ugotovimo, da je \((\mathbb{Z}_n,+_{\scriptsize n})\) grupa za poljubno naravno število \(n\). Z razširjenim Evklidovim algoritmom (glej članka M. Juvana, O Evklidovem algoritmu, Presek 21 (1993-94), str. 116-121, ter A. Jurišića, Kako deliti skrivnost, Presek 29 (2001-02)), pa lahko enako pokažemo tudi za \((\mathbb{Z}_p\backslash \{0\},*_{\scriptsize p})\), kjer je \(p\) poljubno praštevilo. Tako smo prišli do praštevilskega obsega \((\mathbb{Z}_p,+_{\scriptsize p},*_{\scriptsize p})\).

Tablice in grupe

Sedaj pa si poglejmo tablice nekoliko pobliže. Vprašajmo se, kako lahko iz neke tablice ugotovimo, ali gre za grupo. Oglejmo si naslednje lastnosti \(n\times n\) razsežne tablice za komponiranje.

(T1) V tablici se lahko pojavijo samo tisti elementi, ki jih komponiramo.

(T2) Ena vrstica in en stolpec morata biti zaporedoma enaka koordinatni vrstici in koordinatnemu stolpcu, množica enot v tablici pa je simetrična glede na glavno diagonalo, tj. diagonalo, ki izhaja iz levega zgornjega kota.

(T3) V vsaki vrstici in vsakem stolpcu se pojavi vsak element natanko enkrat.

(T4) V tablici si izberimo enoto e in v njeni vrstici oziroma stolpcu še element \(r\) oziroma \(s\). Potem je element, ki leži v isti vrstici kot \(s\) in istem stolpcu kot \(r\), enak \(s\circ r\), glej tabelo 8b.

Tabela 8

\[ \begin{array}{|c|ccccc} \hline \circ & \phantom{aaa} & & \phantom{aaaa} & & \phantom{aaa} \cr \phantom{A} & & & & & \cr \hline \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr & & ? & & s & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr & & r & & e & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr \end{array} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{|c|ccccc} \hline \circ && \phantom{aaa} & x' & \phantom{aaaa} & y & \phantom{aaa} & \cr \phantom{A} && & & & & & \cr \hline \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr y' && & s\circ r & & s & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr x && & r & & e & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr \end{array} \]

Lastnost (T1) je ekvivalentna zaprtosti množice za komponiranje, medtem ko je lastnost (T2) ekvivalentna obstoju enote. Tablicam, ki zadovoljujejo lastnost (T3), pravimo Latinski kvadrati. Le-ta je ekvivalentna zahtevi, da sta za vsaka elementa \(a\) in \(b\) enačbi \(a\circ x=b\) in \(x\circ a=b\) rešljivi, saj v vrstici oziroma stolpcu, ki ustreza elementu \(a\), poiščemo element \(b\), katerega stolpec oziroma vrstica ustreza elementu \(x\). Če si za \(b\) izberemo enoto, potem nam ta pogoj zagotavlja obstoj inverznega elementa za vsak \(a\). Rešljivost zgornjih enačb v grupi sledi iz (G3) in (G4). Prepričajmo se še, da velja lastnost (T4) v vsaki grupi z enoto \(e\), glej tabelo 8b. Iz \(x\circ y=e\), \(x\circ x'=r\) in \(y'\circ y=s\) namreč sledi \(y\circ x=e\) in \[ y'\circ x'= (y'\circ e)\circ x' = y'\circ e\circ x' = (y'\circ (y\circ x))\circ x' = (y'\circ y)\circ (x\circ x') = s\circ r. \] Velja pa tudi obratno, tj. pogoji (T1)-(T4) nam zagotavljajo, da tablica za komponiranje ustreza neki grupi.

Izrek. Tablica za komponiranje zadovoljuje lastnosti (T1)-(T4), če in samo če je tablica neke grupe.

Dokaz. Prepričati se moramo le še, da iz (T1)-(T4) sledi asociativnost. Najprej izpeljemo asociativnost za elemente \(b^{-1}\), \(b\) in \(c\), tj. \(c=(b^{-1}\circ b)\circ c=b^{-1}\circ (b\circ c)\). Seveda lahko privzamemo \(e\ne b\) in \(c\ne b^{-1}\). Če je \(c=b^{-1}\) ali pa \(e\in \{b,c\}\), potem je pogoj (G4) očitno izpolnjen. Izberemo si vrstici \(e\) in \(b\) ter stolpca \(c\) in \(b^{-1}\). Zapišemo njihove produkte in nazadnje dobimo želeno relacijo iz lastnosti (T4), glej tabelo 9a.

Tabela 9a

\[ \begin{array}{|c|ccccc} \hline \circ & \phantom{aa} & c & \phantom{aaa} & b^{-1} & \phantom{aa} \cr \phantom{A} & & & & & \cr \hline \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr e=b^{-1}\circ b & & c=b^{-1}\circ (b\circ c) & & b^{-1} & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr b & & b\circ c & & e & \cr \phantom{A} & & & & & \cr \phantom{A} & & & & & \cr \end{array} \]

Tabela 9b

\[ \begin{array}{|c|ccccc} \hline \circ && \phantom{aa} & b\circ c & \phantom{aaa} & b & \phantom{aa} & \cr \phantom{A} && & & & & & \cr \hline \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr a && & a\circ(b\circ c)=(a\circ b)\circ c & & a\circ b & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr b^{-1} && & b^{-1}\circ (b\circ c) =c & & e & & \cr \phantom{A} && & & & & & \cr \phantom{A} && & & & & & \cr \end{array} \]

Sedaj pa pokažimo asociativnost še za poljubne elemente, tj. \(a\circ (b\circ c)=(a\circ b)\circ c\). Zopet privzamemo \(a\ne b^{-1}\) in \(c\ne e\), kajti sicer želena relacija sledi že iz pravkar obdelanega posebnega primera. Izberemo si vrstici \(a\) in \(b^{-1}\) ter stolpca \(b\circ c\) in \(b\). Želena relacija sledi iz lastnosti (T4), glej tabelo 9b.

6. Isto grupo lahko srečamo v različnih preoblekah. Prepričaj se o tem za grupo \((\mathbb{Z}_4,+_4)\) in množico \(\{1,-1,i,-i\}\), kjer je \(i=\sqrt{-1}\), z običajnim množenjem. Potrebno je najti povratno enolično preslikavo (tj. bijekcijo) iz \(\mathbb{Z}_4\) v \(\{1,-1,i,-i\}\), ki preslika vsoto dveh elementov v produkt njunih slik. Taki preslikavi pravimo izomorfizem.

Končni obseg GF\((p^n)\)

Tokrat se prepričajmo, da tablici 10a in 10b ustrezata nekima grupnima operacijama in da je množica binarnih trojic \(\{ 000, 001,010,011,100,101,110,111\}\) za ti operaciji obseg. Zakon o združevanju (asociativnost) za seštevanje je pravzaprav očiten, saj seštevanje poteka tako, da seštevamo trojice po mestih (prvo, drugo in tretje) po modulu 2, glej tabelo 10a.

Tabela 10a

\[ \begin{array}{|c|cccccccc|} \hline \!\! + & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \cr \hline 000 & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111\cr 001 & 001 & 000 & 011 & 010 & 101 & 100 & 111 & 110\cr 010 & 010 & 011 & 000 & 001 & 110 & 111 & 100 & 101\cr 011 & 011 & 010 & 001 & 000 & 111 & 110 & 101 & 100\cr 100 & 100 & 101 & 110 & 111 & 000 & 001 & 010 & 011\cr 101 & 101 & 100 & 111 & 110 & 001 & 000 & 011 & 010\cr 110 & 110 & 111 & 100 & 101 & 010 & 011 & 000 & 001\cr 111 & 111 & 110 & 101 & 100 & 011 & 010 & 001 & 000\cr \hline \end{array} \]

1. seštevanje,

Tabela 10b

\[ \begin{array}{|c|c|ccccccc|} \hline \!\!\!\! *& 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \cr \hline 000 & 000 & 000 & 000 & 000 & 000 & 000 & 000 & 000 \cr \hline 001 & 000 &{001}& 010 & 011 & 100 & 101 & 110 & 111 \cr 010 & 000 & 010 & 111 & 101 & 011 &{001}& 100 & 110 \cr 011 & 000 & 011 & 101 & 110 & 111 & 100 & 010 &{001}\cr 100 & 000 & 100 & 011 & 111 & 010 & 110 &{001}& 101 \cr 101 & 000 & 101 &{001}& 100 & 110 & 011 & 111 & 010 \cr 110 & 000 & 110 & 100 & 010 &{001}& 111 & 101 & 011 \cr 111 & 000 & 111 & 110 &{001}& 101 & 010 & 011 & 100 \cr \hline \end{array} \]

2. množenje

Zato tudi označimo to grupo z \((\mathbb{Z}_2\times \mathbb{Z}_2\times \mathbb{Z}_2,+_2)\). Zakona o združevanju za množenje in zakona o razčlenjevanju (distributivnost) pa ni tako lahko preveriti. Če v ta namen uporabimo zgornji izrek, potem si pomagamo z zakonom o zamenjavi, kajti takoj lahko opazimo, da sta tablici simetrični glede na glavno diagonalo.

Za konec vključimo v našo zgodbo še polinome stopnje manjše od \(n\), \(n\in\mathbb{N}\), s koeficienti iz obsega \((\mathbb{Z}_p,+_{\scriptsize p},*_{\scriptsize p})\), kjer je \(p\) praštevilo. Te polinome lahko seštevamo na enak načini kot v tabeli 10a (le da tokrat seštevamo enakoležne koeficiente), če pa jih množimo, potem običajni produkt zmanjšamo po modulu nekega polinoma stopnje \(n\), ki se ga ne da razcepiti v obsegu \((\mathbb{Z}_p,+_{\scriptsize p},*_{\scriptsize p})\) (tako kot smo prej računali po modulu praštevila), in zopet dobimo končni obseg.

Matematikom je celo uspelo dokazati, da mora biti vsak končen obseg take oblike in da velja za množenje zakon o zamenjavi (Wedderburnov izrek), a to že presega naš okvir. Omenimo le še, da jih imenujemo Galoisovi obsegi in jih označimo z GF\((p^n)\). Za \(n=1\) dobimo seveda praštevilski obseg.

Primer: Naj bo \(n=3\), \(p=2\), glej tabeli 10a in 10b, za nerazcepen polinom pa si izberemo \(x^3+x^2+1\). Potem v zgornjih binarnih trojicah prvo mesto ustreza koeficientu ob \(x\), drugo koeficientu ob \(x^2\), tretje pa konstantnemu koeficientu.

Osnova za Evklidov algoritem je dejstvo, da lahko za vsak par naravnih števil \(a\) in \(b\), \(a>b\), najdemo taki števili \(q\) in \(r\), da velja \(a=qb+r\), kjer je ostanek \(r\) manjši od \(b\). Za polinoma \(a(x)\) in \(b(x)\) nad končnim obsegom, st\((a)>{\rm st}(b)\) (st je oznaka za stopnjo polinoma) pa velja
\(a(x) = q(x)b(x)+r(x)\), kjer je st\((b)>{\rm st}(r)\). Za zgled pokažimo kako z razširjenim Evklidovim algoritmom poiščemo obratni element polinoma \(x^4+x+1\) v obsegu GF\((2^5)\) z nerazceprnim polinomom \(x^5+x^2+1\). Leva stran ustreza Evklidovemu algoritmu, desna pa razširjenemu delu:

\[ \begin{array}{ccc} x^5 \!+\! x^2 \!+\! 1 &=& x(x^4 \!+\! x \!+\! 1) \!+\! x\!+\!1 \\ x^4 \!+\! x \!+\! 1 &=& (x^3\!+\!x^2\!+\!x\!+\!1)(x \!+\! 1) \!+\! 1 \end{array} \] \[ \begin{array}{ccc} x\cdot 1 \!+\! 0 & = & x \\ (x^3\!+\!x^2\!+\!x\!+\!1) x \!+\! 1 &=& x^4\!+\! x^3 \!+\! x^2 \!+\! 1 \end{array} \]

7. Znano je, da je multiplikativna grupa poljubnega končnega obsega ciklična, tj. v grupi obstaja tak element, da so vsi elementi njegove potence. Prepričaj se, da je ciklična grupa z \(n\) elementi izomorfna grupi \((\mathbb{Z}_n,+_n)\) (element 1 generira s svojimi večkratniki, kakor v aditivnem primeru pravimo potencam, vse elemente). To grupo označimo na kratko s \(C_n\). Namig: najprej preveri trditev na kakšnem konkretnem primeru, npr. primera iz tabel 7b in 10b.

8. Diederska grupa \(D_n\) je grupa simetrij pravilnega \(n\)-kotnika. Prepričaj se, da v grupi \(D_3\) ne velja zakon o zamenjavi (komutativnost) (mimogrede: grupo \(D_3\) lahko predstavimo tudi kot grupo permutacij treh elementov \({\cal S}_3\)).

9. Naslednja grupa, ki je še nismo srečali, je moči 8 in ji pravimo kvaternionka, glej tabelo 11. Poišči njeno tablico množenja.

Tabela 11

\[ \begin{array}{|c|c|} \hline {\rm mo\check{c}} & \ {\rm ime\ grupe} \cr \hline 1 & \ \ C_1 \cr 2 & \ \ C_2 \cr 3 & \ \ C_3 \cr 4 & \ \ C_4, \ \ C_2 \times C_2 \cr 5 & \ \ C_5 \cr 6 & \ \ C_6, \ \ D_3 \cr 7 & \ \ C_7 \cr 8 & \ \ C_8, \ \ C_2 \times C_4, \ \ C_2 \times C_2 \times C_2, \ \ D_8, \ \ Q_8 \cr 9 & \ \ C_9, \ \ C_3 \times C_3 \cr 10 & \ \ C_{10},\ D_{10} \cr \hline \end{array} \]

1. Moč grupe je število njenih elementov. Zgornja tabela vsebuje vse grupe z največ desetimi elementi.

Za nadaljnje branje priporočamo: I. Grossman in W. Magnus, Grupe in njihovi grafovi, Školska knjiga Zagreb, 1975 in internet, npr. http://members.tripod.com/~dogschool//, za zrelejše bralce pa Vidav, Algebra, Mladinska knjiga, 1972.

6.3 Praštevila

Doma (v točki ena) nam postane dolgčas in podamo se na sprehod po številski premici.

Slika 0

Naravna števila, predstavljena na številski premici.

Hitro opazimo, da se večkratniki števil pojavljajo enakomerno. Poglejmo si dva primera.

• Vsako sodo število se pojavi na vsakem drugem koraku (pri tem seveda privzamemo, da je dolžina našega koraka enaka ravno enoti), ali če želite, ob desni nogi (če smo začeli naš sprehod z levo).
• Vsak večkratnik števila tri se pojavlja izmenično enkrat na levi, enkrat na desni nogi, vsakokrat pa na dveh vmesnih korakih manjka.

Kaj pa če opazujemo cela števila, ki niso večkratniki nobenega drugega števila, kakor le samega sebe in enice (s slednjo bi tako ali tako pokrili vsa števila)? Tem številom pravimo praštevila oziroma nerazcepna števila, saj se jih ne da razcepiti v produkt dveh od ena različnih števil.

Ali se tudi praštevila pojavljajo po kakšnem pravilu?

V tem razdelku bomo spoznali, kako bi se s tem lahko ukvarjal F. Gauss, če bi imel na voljo računalnik. Prav on je bil namreč tisti, ki je postavil domnevo o gostoti praštevil.

Eratostenovo rešeto

Gotovo ste v šoli že slišali za Eratostenovo rešeto. To je eden od najstarejših algoritmov, s katerim lahko najdemo praštevila. Sestavimo tabelo števil od \(1\) do npr. \(400\). Za začetek prečrtamo vsa soda števila, z izjemo prvega, nato vse večkratnike števila \(3\), zopet z izjemo prvega. Ker smo število \(4\) že prečrtali, nadaljujemo z večkratniki števila~\(5\). Po tem postopku pridejo na vrsto še večkratniki števil \(7\), \(11\), \(13\), \(17\) in \(19\).

Gotovo veste, zakaj nam v tabeli ostanejo samo še praštevila skupaj z enico?

Naj vam zaupamo, da najmanjši izmed faktorjev sestavljenega števila ni nikoli večji od korena tega števila.

Ni kaj, to je kar učinkovit algoritem. Ko enkrat že poznamo praštevila do \(20\), je morda bolj zabavno opravljati izločanje sestavljenih števil v obratnem vrstnem redu, od večkratnikov števil \(19\), \(17\), \(\ldots\), pa vse do večkratnikov števila \(2\). V pomoč ti je lahko naslednja aplikacija, kjer lahko opazuješ kakšne vzorce naredijo izginjajoča sestavljena števila.

Zabava gor ali dol, a ne zanimajo nas praštevila samo do \(400\). Če hočemo še naprej, si bomo seveda pomagali z računalnikom. Zapišimo kodo, ki opravi to delo namesto nas. To bo psevdo koda, tj. poenostavljena koda, ki ni pisana za noben konkreten programski jezik, temveč skuša predstaviti samo idejo algoritma na čim enostavnejši način.

6.3.0.1 O Eratostenu

Eratosthenes se je rodil leta 276 p.n.š. v severni Afriki (ki je danes del Libije) in študiral v Atenah (bil je tudi tretji glavni knjižničar v Aleksandriji). Poleg svojega rešeta je izračunal tudi obseg Zemlje, pa oddaljenost Sonca in Lune. Gre za briljantnega znanstvenika, ki je bil prijatelj Arhimeda, enega največjih matematikov v zgodovini. Zavistneži so ga morda prav zaradi tega klicali tudi Beta – bil naj bi drugi najboljši med svojimi sodobniki v vsem. Toda zgodovina je pokazala, da je bil prvak na številnih področjih, ki vključujejo astronomijo, geografijo, literaturo, poezijo, filozofijo in matematiko. Celo `biti drugi’ na tolikih področjih in še v času neverjetnega napredka ga postavlja med največje genije vseh časov.

Psevdo koda Eratostenovega rešeta

n := 1000;
p := array[1..n];
for i := 1 to n do
  p[i] := 0
p[1] := 1;
for i := 2 to n do
    if p[i] = 0 then
        for j := 2 to n / i do
            p[j * i] := 1;

Slika1

Poglejmo si, kako koda deluje. V prvi vrstici povemo, da bomo iskali vsa praštevila do \(1000\). To število lahko pri pravilno napisani kodi nadomestimo s poljubnim drugim naravnim številom, ki je večje od \(1\). Nato si v drugi vrstici pripravimo tabelo \({\tt p}\) prvih \(1000\) naravnih števil. V tretji in četrti vrstici se s for zanko sprehodimo po vseh naravnih številih od \(1\) do in postavimo vse vrednosti v tabeli na \(0\), kar naj pomeni, da so še neprečrtane. Za postavljanje vrednosti v tabeli na \(0\) ponavadi poskrbi že operacijski sistem. Črtanje števila \(i\) v tabeli bomo označili tako, da bomo vrednost \({\tt p[i]}\) postavili na \(1\). V peti vrstici tako prečrtamo število \(1\), ki ni ne praštevilo ne sestavljeno število. Nato pa sledimo postopku, ki smo ga opisali zgoraj. Tako se v šesti vrstici s for zanko ponovno sprehodimo po vseh naravnih številih od \(2\) do \({\tt n}\), saj vnaprej ne vemo, katera števila bodo že prečrtana in katera še ne. To ugotovimo v sedmi vrstici, ko z if stavkom preverimo, ali je trenutno število \({\tt p[i]}\) še neprečrtano (\({\tt p[i] = 0}\)), tj. ali je praštevilo. Samo v tem primeru namreč črtamo njegove večkratnike. To naredi for zanka v osmi vrstici, ki nas popelje od drugega pa do \(\lfloor {n/i} \rfloor\)-tega večkratnika. Samo črtanje večkratnikov opravimo v deveti vrstici, ko postavimo ustrezne elemente tabele na \(1\). Ko se postopek konča, imamo v tabeli \({\tt p}\) spravljene podatke o tem katera števila so sestavljena (imajo vrednost \(1\)) in katera ne (vrednost \(0\)). Zgornjo kodo lahko seveda zapišemo v poljubnem programskem jeziku in popravimo tako, da uporabnik sam vpiše zgornjo mejo \({\tt n}\).

Pozoren bralec bo hitro opazil, da se da zgornjo kodo še bistveno izboljšati. V zadnji for zanki smo črtali kar vse večkratnike, ne glede na to, ali so bili že črtani ali ne. Ker je branje precej hitrejše od pisanja, lahko z dodatnim if stavkom, ki preveri ali je večkratnik že prečrtan, ali ga še moramo, naš program precej pohitrimo (za okoli 27%). Nadalje smo že omenili, da je v for zanki v šesti vrstici dovolj gledati le do korena števila \({\tt n}\). Na ta način prihranimo veliko klicev if stavka v sedmi vrstici in s tem pohitrimo naš program še za okoli 37%.

Vsak izkušen programer bi nam tudi povedal, da je deljenje števil v računalniku dosti počasnejše od množenja, ki je tudi počasnejše od seštevanja. Zato bi lahko osmo in deveto vrstico zgornjega programa spremenili tako, da bi začeli z dvakratnikom števila \(i\) in na vsakem koraku prištevali \(i\) namesto \(1\). S tem se znebimo tako deljenja kot množenja in pridobimo še 25%.

Nadalje lahko opazimo, da nam v for zanki iz osme vrstice ni potrebno začeti pri dvakratniku števila \(i\), ampak lahko začnemo šele pri \(i\)-kratniku števila \(i\), torej z \(i^2\). Vsi večkratniki števila \(i\), ki so manjši od \(i^2\), so namreč ravno \(i\)-ti večkratniki števil \(2, \ldots, i-1\). S tem pridobimo še dodatne 4%. Skupno je naš program sedaj trikrat hitrejši. Možne so seveda še nadaljnje izboljšave. Če recimo upoštevamo, da je \(2\) edino sodo praštevilo, bo program kar štirikrat hitrejši od začetnega.

Poglejmo si, kako bi izgledal naš program, vključno z vsemi izboljšavami, v programskem jeziku C. Iskal bo vsa praštevila do \(100.000.000\).

Eratostenovo rešeto v programskem jeziku C

#include <stdio.h>

#define MAX 100000000
#define SQRT 10000

char p[MAX + 1];

int main(void) {
    int i, j;

    for (i = 2; i <= SQRT; i++)
        if (p[i] == 0)
            for (j = i * i; j <= MAX; j += i)
                if (p[j] == 0)
                    p[j] = 1;

    return 0;
}

Gostota praštevil

Označimo s \(p(n)\) število praštevil, ki so manjša ali enaka \(n\). To je ravno število polj v tabeli \({\tt p}\), katerih vrednost je enaka \(1\). Pri različnih vrednostih konstante \({\tt MAX}\) dobimo naslednje rezultate:

\[\begin{array}{|c|c|c|} \hline MAX & p(n) & \displaystyle{\frac{p(n)\ln(n)}{n}} \\[0mm] \hline 100 & 25 & 1.151292546 \\[1mm] 1.000 & 168 & 1.160502887 \\[1mm] 10.000 & 1.229 & 1.131950832 \\[1mm] 100.000 & 9.592 & 1.104319811 \\[1mm] 1.000.000 & 78.498 & 1.084489948 \\[1mm] 10.000.000 & 664.579 & 1.071174789 \\[1mm] 100.000.000 & 5.761.455 & 1.061299232 \\[1mm] \hline \end{array}\]

Gotovo ste opazili, da se v tabeli nahaja tudi logaritemska funkcija \(\ln n\). V srednji šoli pride ta snov na vrsto v drugem letniku. Ali kdo ve, kako bi iz vrednosti \(\log_a b\) dobili dolžino zapisa števila \(b\) v številskem sistemu z osnovo \(a\)? Si predstavljate, da je Gauss prišel do podobnih rezultatov peš (brez računalnika) in pri šestnajstih letih postavil naslednjo domnevo:

Za dovolj veliko število \(n\) je število praštevil do števila \(n\) približno \[ \frac{n}{\ln n}. \]

Sliki

225px-Carl_Friedrich_Gauss.jpg

vega.jpg

Pri tem imejte v mislih, da je bilo v tistih časih že računanje naravnega logaritma povsem netrivialno (oziroma zelo zamudno) opravilo, saj še ni bilo kalkulatorjev. V nekem trenutku so bile na voljo , kot najmodernejši pripomoček za računanje (kateremu bi danes rekli računalnik) tistega obdobja.

Iz zgornje ocene lahko dobite z osnovnim znanjem o limitah tudi oceno za velikost \(n\)-tega praštevila \(p_n\): \[ p_n \ \approx \ n \ln n, \] ki vpelje nekakšen red med dovolj velika praštevila.

6.4 Aritmetika

6.4.1 Predstavitev danega števila:

6.4.2 Iskanje manjših faktorjev danega števila:

6.4.3 Množenje

Vhod naj bosta dva števili \(x\), \(y\) in baza \(b\) (za vhod uporabi “inputbox” ali pa vhod integriraj v sam izpis postopka množenja): - Baza naj bo med 2 do 16. - Za branje števil v izbrani bazi uporabi parseInt(vhodno_stevilo_string, baza).

Izhod naj postopek šolskega množenja korak po koraku.

• Katero obliko uporabiš za izpis postopka množenja se odloči sam (lahko uporabiš tabelo, lahko pa le “monospaced” besedilo).
• Ni ti treba implementirat operacij v posameznih bazah. Le ob izpisu števila uporabi stevilo.toString(baza). Do posamezne števke lahko dostopaš kot

• Interaktivnost, trije gumbi začni z množenjem, naslednji korak in dokončaj vse:
• Gumb začni z množenjem začne z množenjem, tako da izpise prvo vrstico.
• Gumb naslednji korak izvede en korak navadnega množenja (ena dodatna vrstica).
• Gumb dokončaj vse izvede vse korake do konca.

Namigi in dodatne ideje:

• Dodaj možnost sprotnega seštevanja (checkbox). To pomeni, na vsakem koraku trenuten produkt prišteješ trenutni vsoti. Pomeni, da imamo vedno največ 3 vrstice (prva vrstica - faktorja, ki jih množimo, druga vrstica - trenutna vsota delnih produktov, tretja vrstica - začne se z znakom + in predstavlja trenutni produkt).
• Pobarvaj (z eno barvo) aktivne števke v trenutnem koraku (cel prvi faktor, trenutna števka v drugem faktorju, in trenuten zmnožek - glej sliko).
• Za majhne vhode lahko dodaš vizualno predstavitev šolskega množenja long multiplicaton. To je primerno samo za desetiško bazo.
• Zaradi preglednosti lahko dodaš možnost ignoriranja ničelnih vrstic.
• Po potrebi lahko izpišeš dodatno pojasnilo ob vsakem koraku.
• Aplikacijo lahko dogradiš, da dodaš možnost za izbiro druge metode - “metoda ruskih kmetov” (ta metoda deluje za poljubno bazo).

6.4.4 Alternativno množenje

6.5 Aritmetika ure

6.5.1 Računanje s tabelo

Vhod naj število \(n\), ki predstavlja množico \(\mathbb{Z}_n=\{0,1,\dots,n-1 \}\).

Izhod naj bo tabela podane velikosti \((n+1) \times (n+1)\) (prva vrstica in prvi stolpec predstavlja faktorje oz. seštevance).

• Tabela “množenje” - ((a * b) % n) in “seštevaje” - ((a + b) % n), le da tu računamo z ostanki v \(\mathbb{Z}_n\) - aritmetika ure.
• Poleg tabele se izpiši število elementov z inverzom (za “seštevanje” je to kar \(n\), pri “množenju” so pa elementi ki nimajo v vrsticah ničel).
• Poudari polja z enotami (število nič v primeru “seštevanja” in število ena v primeru “množenja”).

• Interaktivnost, ko se uporabnik premakne (ali pa klikne) na polje v tabeli:
• se mu ob tabeli izpiše operacija in rezultat (\(a b \equiv x \pmod{n}\), \(a + b \equiv y \pmod{n}\)),
• če nanj klikneš, se poleg v tabeli označijo vse ponovitve tega rezultata.
• Za element z inverzom izpiši naslednji cikel (podgrupo) za dano operacijo: npr. za \(13\) v \(\mathbb{Z}_{15}\) za operacijo “množenja” je tak cikel naslednji: \(13 \rightarrow 13 \times 13 \equiv 4 \rightarrow 4 \times 13 \equiv 7 \rightarrow 7 \times 13 \equiv 1 \rightarrow 1 \times 13 \equiv 13\). V primeru seštevanja dobimo vsa števila od 0 do \(n-1\).
• Izpiši in inverzni element.

Peskovnik 6.?: Tabeli za seštevanje in množenje

TO-DO:

1. everywhere: Add caption with instructions
2. everywhere: (izboljševal LŽ) Initials of the author and of the one who was improving (output?),
3. everywhere: Is the interaction at the right place?
4. everywhere: English version

Namigi in dodatne ideje:

• Kako odštevamo in delimo z danimi tabelami? (Kako poiščemo inverze v tabeli).
• Naključeni računi (“seštevanje”, “odštevanje”, “deljenje”, “množenje”) z vnosnimi polji za rezultat (Dva gumba: eden za generiranje računov in eden za testiranje rezultata).

6.5.1.1 Grafično prikazano “množenje” oz. “seštevanje” z uro.

6.5.2 Aritmetika v \(\mathbb{Z}_n = \{0, \dots, n-1\}\)

V prejšnji aplikaciji (glej računanje z tabelo) smo si pogledali, kako seštevamo, odštevamo, množimo in delimo z uporabo tabel. Pogledali si bomo, kako izvajamo aritmetične operacije v splošnem, ko nimamo tabel oz. so števila tako velika, da nimamo dovolj prostora (pomnilnika) ter računske moči za izgradnjo takih tabel.

6.5.3 Računanje ostanka

\[ d = a + kn \equiv a \pmod{n} \quad \forall k \in Z \]

Ostanek lahko dobimo kot stranski produkt celoštevilskega deljenja. Tako kot dolgo šolsko množenje se tudi dolgo šolsko deljenje v različnih bazah ne spremeni. Najenostavneje je deliti bazi 2, saj imamo pri posameznem pod-deljenju le dve moznosti – bodisi je deljenec večji od deljitelja, v tem primeru je količnik 1 (+ ostanek), bodisi je deljenec manjši od deljitelja, v tem primeru je količnik 0 (+ostanek).

Interaktivna aplikacija za dolgo šolsko deljenje v različnih bazah

6.5.4 Seštevanje v \(\mathbb{Z}_n\)

6.5.4.1 Osnovna operacija \(+_n: (a,b) \mapsto a +_n b\):

To operacijo lahko izvedemo tako, da najprej števili navadno seštejemo in potem izračunamo ostanek pri deljenju z \(n\) (trivialno, saj je količnik največ 1)

6.5.4.2 Inverzni element \(a_{\text{inverz}}\) elementa \(a\) (tj. nasprotno število)

Za inverzni element \(a_{\text{inverz}}\) elementa \(a\) velja

\[ a +_n a_{\text{inverz}} = a_{\text{inverz}} +_n a = 0. \]

Inverzne elemente v primeru operacije seštevanja označimo kot: \(a_{\text{inverz}} = -a\)

Inverz lahko izračunamo kot: \[ -a \equiv n - a \pmod{n} \]

Če je \(n\) oblike \(n = 2^k\) za \(k \in N\) in imamo števila predstavljena v binarnem zapisu lahko uporabimo kar dvojiški komplement \(-a = \text{NOT}(a) +_n 1\). Tu \(\text{NOT}(a)\) predstavlja negacijo vseh bitov v binarnem zapisu števila \(a\).

Samo v primeru ko je \(n=2\), obstajajo tak inverz, ki ni enota (0), za katerega velja \(-a=a\).

Na prištevanje inverza lahko gledamo kot “odštevanje”.

6.5.4.3 Ponavljanje seštevanja (“množenje”)

\[ a +_n \dots +_n a \equiv k a \pmod{n}, \quad k \in N \]

Vsoto bi lahko izračunali tako, da bi izvedli \(k-1\) seštevanj. To ni primerno saj, je \(k\) lahko zelo velik.

Obstaja boljša metoda, ki uporabi samo logaritmično število korakov v odvisnosti od \(n\). Ta metoda se imenuje podvoji in prištej, ki je podobna metodi ruskih kmetov, le v obratni smeri in na vsakem koraku namesto navadnega seštevanja uporabimo seštevanje v \(\mathbb{Z}_n\).

Ali lahko zmanjšamo \(k\)? Seveda, če je \(k \geq n\), lahko enostavno računamo kar s \(k' = k \mod n\), saj je red vsakega elementa kar \(n\) (tj. \(na \equiv 0 \pmod{n}\)).

Interaktivna aplikacija

• Računamo v \(\mathbb{Z}_n\).
• Primerjava z večkratnim seštevanjem.
• Reduciraj \(k\) (lahko prikažeš obe monžnosti).

6.5.4.4 Inverz ponavljanja seštevanja (“deljenje”)

\[ c \equiv a +_n \dots +_n a \equiv k a \pmod{n}, \quad k \in \mathbb{Z}_n \]

Potemtakem je \(k:= c/a\). Tega ne moremo direktno izračunati, saj ne vemo kolikokrat smo odšteli \(n\) pri računanju ostanka, ko smo seštevali vsoto \(a +_n \cdots +_n a\). V \(\mathbb{Z}_n\) se to prevede na iskanje takega števila \(\ell\), da je operacijo navadnega deljenja možno izvesti z deljenjem brez ostanka.

\[ k = \frac{c + \ell n}{a}\, \text{ za nek }\, \ell \in \mathbb{Z}_n \]

Število \(\ell\) lahko poiščemo s poizkušanjem. Ker je \(\ell\) lahko zelo veliko število, ta metoda ni primerna.

Ali lahko vedno poiščemo tak \(\ell\). Ne (glej 4. Navodila …).

Problem bi znali enostavno rešiti, če bi poznali tako število \(x\), da velja \(xa \equiv ax \pmod{n}\). Potem bi \(k\) izračunali kot:

\[ k \equiv \frac{c}{a} 1 \equiv \frac{c}{a} ax \equiv cx \pmod{n} \] Takemu številu \(x\) pravimo obratno število števila \(a\). Tako število obstaja natanko takrat, ko sta števili \(a\) in \(n\) tuji. Števili sta tuji, ko je največji skupni delitelj enak ena. Izkaže se, da če ne moremo izračunati obratnega števila ne moremo izračunati inverza ponavljanja seštevanja (to je ekvivalentno problemu deljenja z nič v \(\mathbb{Q}\)).

Računanje največjega skupnega deljitelja

Osnovnošolska metoda za računanje največjega skupnega delitelja dveh števil je naslednja:

• Najprej poiščemo multi-množici praštevilskih faktorjev za posamezno število.
• Največji skupni delitelj je produkt preseka faktorjev teh dveh multi-množic.

Problem pri tej metodi je, da je iskanje praštevilskih faktorjev v splošnem računsko zahtevna operacija.

Obstaja računsko učinkovita metoda - Evklidov algoritem.

Psevdokoda:

function gcd_mod(a, n){
  while (n !== 0){
    var t = n
    n = a % n
    a = t
  }
  return a
}

function gcd_sub(a, n){
  while (a !== n){ 
    if (a > n){
      a = a - n
    }else{
      n = n - a
    }
  }
  return a
}

Problem iskanja največjega skupnega delitelja, si lahko predstavljamo kot iskanje največjega kvadrata s katerim je še možno tlakovati mrežo velikosti \(a \times n\) tako, da se izide.

Primer mreže \(24 \times 60\). Največja možna ploščica je velikosti \(12 \times 12\).

Evklidov algoritem lahko grafično prestavimo na naslednji način (primer za \(16 \times 38\).

Interaktivna aplikacija Smiselno prestavi vse tri načine (glej psevdokodo) računanja najmanjšega skupnega večkratnika: - Šolski način. Za izračun faktorjev lahko uporabiš kodo iz 1. Navodila … - Za grafični prikaz omeji globino (lahko pa začneš znova ko prides, do neke globine). - Prikazi vsak korak posebej.

Računaje obratnega elementa \(x\) elementa \(a\)

Predpostavimo, da za \(a\) obrani element obstaja (\(\gcd(a,n)=1\)). Zdaj ga želimo še računsko učinkovito izračunati.

Enačbo \(ax \equiv 1 \pmod{n}\) lahko zapišemo kot:

\[ ax + ny = 1, \quad x, y \in Z \]

Želimo poiskati celoštevilske rešitve zgornje (linearne diofantske) enačbe. Rešitve lahko poiščemo z razširjenim Evklidovim algoritmom. Potek algoritma je enak navadnemu Evklidovemu algoritmu le, da v tem primeru odštevamo med seboj enačbe in ne števila.

Začnemo z dvema očitnima rešitvama: \[ a\cdot 0 + n\cdot 1 = n,\quad(\mbox{tj.}\ x=0, y=1) \\ a\cdot 1 + n\cdot 0 = a,\quad(\mbox{tj.}\ x=1, y=0) \] Zamišljamo si, da izvajamo Evklidov algoritem na prostem členu, le da zraven še vodimo evidenco o spremenljivkah \(x\) in \(y\).

Primer. \[ a\cdot 0 + n\cdot 1 = n,\quad(x=0,\ y=1) \\ a\cdot 1 + n\cdot 0 = a,\quad(x=1,\ y=0) \]

Naslednji korak bo:

\[ a\cdot (-1) + n\cdot 1 = n-a,\quad (x=-1,\ y=1) \] oz.

\[ a\cdot (-\lfloor n/a \rfloor) + n\cdot 1 = n\mod a,\quad (x=\lfloor n/a \rfloor,\ y=1) \]

Na koncu bomo dobili:

\[ ax + ny = \gcd(a,n) = 1 \]

Iz te enačbe lahko razberemo obratno vrednost \(x\) in vernost \(y\), ki je analog vrednosti \(\ell\).

Interaktivna aplikacija

6.5.5 Množenje v \(\mathbb{Z}_n\)

6.5.5.1 Osnovna operacija \(*_n: (a,b) \mapsto a *_n b\):

To operacijo lahko izvedemo tako, da najprej števili navadno zmnožimo in potem izračunamo ostanek pri deljenju z \(n\) ali pa uporabimo algoritem podvoji in prištej (glej seštevanje).

6.5.5.2 Inverzni element \(a_{\text{inverz}}\) elementa \(a\) - (obratno število)

Za inverzni element \(a_{\text{inverz}}\) elementa \(a\) velja \(a *_n a_{\text{inverz}} = a_{\text{inverz}} *_n a = 1\). Inverzne elemente v primeru operacije množenja označimo kot: \(a_{\text{inverz}} = a^{-1}\)

Inverzni elemente (če obstaja) lahko izračunamo z razširjenim Evklidovi algoritmom (glej seštevanje).

V primeru, da je \(n\) praštevilo ima vsako neničelno število svoj inverz.

6.5.5.3 Ponavljanje množenja (“potenciranje”) (Boris)

\[ a *_n \dots *_n a \equiv a^k \pmod{n}, \quad k \in N \]

Produkt bi lahko izračunali tako, da bi izvedli \(k-1\) množenj. To ni primerno saj, je \(k\) lahko zelo velik.

Obstaja boljša metoda, ki uporabi samo logaritmično število korakov v odvisnosti od \(n\). Ta metoda se imenuje kvadriraj in zmnoži ni nič drugega kot metoda podvoji in prištej le, da na vsakem koraku namesto seštevanja v \(\mathbb{Z}_n\) uporabimo množenje v \(\mathbb{Z}_n\).

Ali lahko zmanjšamo \(k\)? Seveda. Če poznamo red elementa \(a\) (\(a^r \equiv 1 \pmod{n}\)), potem lahko enostavno računamo kar z \(k' = k \mod r\). V splošnem red elementa v naprej ne vemo. Če slučajno poznamo število elementov od \(0\) do \(n-1\), ki so tuji z \(n\) - (n)$, potem lahko enostavno računamo kar z $k’ = k (n) $, saj \(r | \varphi(n)\).

Če ne poznamo praštevilske faktorizacije števila \(n\), je izračun t.i. Eulerjeve funkcije \(\varphi\) računsko zahteven problem.

Interaktivna aplikacija algoritem kvadriraj in zmnoži.

Relevantni izreki: Eulerjev izrek, Lagrangeov izrek.

6.5.5.4 Inverz ponavljanja množenja (“logaritmiranje”)

\[ c \equiv a *_n \dots *_n a \equiv a^k \pmod{n}, \quad k \in \mathbb{Z}_{\varphi(n)} \]

Potemtakem je \(k:= \log_a c\). Tega ne moremo direktno izračunati, saj ne vemo kolikokrat smo odšteli \(n\) pri računanju ostanka, ko smo računali produkt $a +_n +_n a $ (in drugi razlogi). Temu problemu pravimo problem diskretnega logaritma. Trenutno ni zna noben računsko učinkovit algoritem (v splošnem, za poljuben \(n\)), kot ga imamo za računanje obratnega elementa (REA).

Kdaj je računaje logaritma $ k:= _a c$ sploh smiselno? Kadar \(a\) lahko regenerira \(c\) v \(\mathbb{Z}_n\). Za splošen \(n\) ni trivialnega odgovora. Smiselno je, da velja vsaj \(a \neq 1, \gcd(a,n) =1\) in \(\gcd(c,n)=1\).

Nekaj metod za izračun diskretnega algoritma:

• Naivna metoda: preiščemo vse možnosti oz. generiramo logaritemsko tabelo.
• Malo bolj učinkovita metoda: majhen korak - velik korak.

Interaktivna aplikacija

Interaktivna aplikacija računaje diskretnega logartma pri različnih osnovah \(\tilde a\) z eno logaritemsko tabelo.

• Uporaba množenja in obratnega števila v \(\mathbb{Z}_{\varphi(n)}\).

\[ \log_{\tilde a} c = (\log_a c) *_{\varphi(n)} (\log_a \tilde a)^{-1} \]

6.5.6 Uporaba aritmetičnih operacij v \(\mathbb{Z}_n\) v kriptografiji.

• Afina šifra
• RSA (zelo osnovno)

6.6 Kitajski izrek o ostankih

V tem sestavku bomo predstavili starodavni kitajski izrek o ostankih, v drugem delu pa še nekaj konkretnih zgledov uporabe, ki kažejo na to, da je izrek aktualen še danes. Videli bomo, kako lahko iz obrobnih informacij sestavimo celotno sliko, podobno kot če bi iz tlorisa, narisa in stranskega risa (torej posameznih projekcij) ugotovili, za kakšno telo gre.¹

–>

V daljni Kitajski je Sun Tsu Suan-Ching v četrtem stoletju postavil naslednje vprašanje:

Poišči število, ki da pri deljenju s 3 ostanek 2, pri deljenju s 5 ostanek 3 in pri deljenju s 7 ostanek 2.

Odgovor na to vprašanje iščite najprej sami in šele nato nadaljujte branje. Že kukate? Pa vam dam namig: na list napišite nekaj začetnih števil, ki dajejo ostanek 2 pri deljenju s 3: \[ 53,56,59,62,65,68,71,74,77,80,83,86,89,92,95,98. \] Ste se že utrudili? Pa saj ni tako težko, prvo število je že sam ostanek, potem pa samo še prištevate 3. Preostali množici pa poiščite sami in premislite, kaj bi počeli z njimi prebrisami presekovci. Koliko rešitev ste pa našli? Eno? Dve? Gotovo jih lahko najdete več!

Poglejmo, kako smo nalogo ugnali mi. Če iskano število \(n\) pomanjšamo za 2, potem je deljivo tako s 3 kot tudi s 7. Če upoštevamo še, da sta si ti števili tuji, lahko zapišemo \[ n=21\, m+2 \ \ (m\in \mathbb{Z}). \] Po drugi strani pa \(5\,|\,(21\, m +2) - 3=21\,m-1\) oziroma, če odštejemo večkratnik števila pet, \(5\,|\,21\, m-1-5\times 4 \, m=m-1\). Zaključimo \(m-1=5\,\ell\) za neko celo število \(\ell\) oziroma \[ m=5\,\ell+1 \] in zato \[ n=21\, (5\, \ell+1)+2=105\,\ell+23. \] Število \(n\), ki je oblike \(n=105\,\ell+23\) oziroma \[ n=3\,(35\,\ell+7)+2 =5\,(21\,\ell+4)+3 =7\,(15\,\ell+3)+2, \] očitno zadovoljuje vse tri začetne pogoje, kar pomeni, da je rešitev neskončno: \(\dots\), \(-82\) (za \(\ell=-1\)), \(23\) (za \(\ell=0\)), \(128\) (za \(\ell=1\)),eratostenovo_sito \(\dots\)

Morda pa vas pritegne tudi nekoliko mlajša, a po drugi strani še zanimivejša zgodba iz Brahma-Sphuta-Siddhanta, ki jo je pripovedoval Brahmagupta (rojen konec 6. stoletja):²

–>

Ženica gre na trg prodajat jajca. Ravno, ko zloži jajca na stojnico, podivja konj in podre stojnico. Jajca se strejo in ženica je vsa obupana. Jezdec galantno ponudi poravnavo, a ženica ne zna povedati, koliko jajc je bilo na stojnici. Potarna, da je bilo s temi jajci že od samega začetka vse narobe. Spomni se, da je pri zbiranju jajc prosila hčer, da zleze v kurnik in ji podaja jajca. Dajala je po dve jajci neankrat in nazadnje ji je dala še eno jajce. Ko je sama zlagala jajca v škatlo, jih je jemala po tri in tudi njej je nazadnje ostalo ravno eno jajce. Škatlo je razmočil dež in jajca je bilo potrebno preložiti. Tokrat je hči z vsako roko prijela po dve jajci in jih z obema rokama hkrati podajala materi, na koncu pa ji je dala še eno jajce. Ko je oče kuhal zajca, je v posodo dal po pet jajc naenkrat in tudi on je na koncu moral seči še po eno samo jajce. Ta nesrečna dejavnost se je nadaljevala, saj so jajca zložili v škatle po šest in za zadnjo škatlo je ostalo eno samo jajce. Tedaj pa se oglasi njen sin in pove, da je pri barvanju jajca postavil v vrsto po sedem in se je ravno izšlo ter, da se gotovo da izračunati, koliko jajc je potrebno plačati. Nekemu možu se ženica zasmili in ji prišepne, naj zahteva od jezdeca plačilo za 721 jajc. Število 721 res daje ostanek 1 pri deljenju z 2, 3, 4, 5, 6 in je deljivo s 7, vendar pa se je zdelo jezdecu premalo strtih jajc in preveč denarja.

Pomagajte jezdecu in ugotovite, če je mu je res potrebno plačati toliko jajc.

–>

Ste že našli pravi odgovor? Tule je naša rešitev, ki je kar nekoliko podobna prejšnji. Očitno je dovolj iskati število \(n\), ki daje pri deljenju s \(60=3\times 4 \times 5\) ostanek 1 (saj sta bila podatka o deljivosti z 2 in 6 pravzaprav popolnoma odveč - po drugi strani pa si lahko mislimo, da je možnosti, da si je ženica vse skupaj izmislila, nekoliko manj), hkrati pa je deljivo s 7, tj. \[ n=60\,m+1 \ \ (m\in \mathbb{Z}) \quad\quad \mbox{in} \quad\quad 7\,|\,60\,m+1. \] Zopet se spomnimo, da lahko zadnjo relacijo še nekoliko preoblikujemo, saj lahko po mili volji dodajamo ali odvzemamo večkratnike števila sedem: \[ 7\,|\,(60-7\times 8)\,m+1+7=4\,m+8=4\,(m+2). \] Od tod zaključimo \(7\,|\,m+2\), tj. \[ m=7\,\ell-2 \ \ (\ell \in \mathbb{Z}) \] in končno \[ n=60\,(7\,\ell-2)+1=420\,\ell-119. \] Torej lahko jezdec plača tudi le \(1\times 420-119=301\) jajc (namesto prvotno predlaganih \(2\times 420-119=721\) jajc), čeprav je naklonjen ženici.

Precej logično je, da smo število \(60\,m\) nadomestili s \(4\,m\), saj daje število 60 ostanek 4 pri deljenju s 7. Nato pa smo samo še prišteli eno sedmico in že smo lahko izpostavili 4.

Če želimo ugnati vsako nalogo takega tipa, se moramo vprašati, ali nam uspe končno izpostavljanje v vsakem primeru ali pa gre samo za naključje - začetniško srečo.

Recimo, da bi prišli do relacije \(7\,|\,a\,m+b\), kjer sta \(a\) in \(b\) ostanka pri deljenju s 7. Sedaj je potrebno prišteti \(x\) sedmic, da bo \(a\,|\,b+7\,x\) oziroma za dani števili \(a\) in \(b\) v celih številih rešiti enačbo \(b=a\,y-7\,x\). Grški filozof Diophantus iz tretjega stoletja je napisal številne knjige o problemih, ki iščejo celoštevilske rešitve. Po njem imenujemo take enačbe diofantske. Se da torej vedno rešiti pravkar dobljeno diofantsko enačbo? Tablica za množenje po modulu 7, glej tabelo 1(b), ima to lastnost, da v stolpcu večkratnikov števila \(a\) (ali pa v kateremkoli drugem stolpcu) nastopajo prav vsi od nič različni ostanki pri deljenju s sedem, torej tudi število \(b\). Le-to pa ustreza ravno večkratniku \(a\,y\). Glej A. Jurišić, Računala nove dobe, Presek 30 (2002-03), str. 226–231 (1. del) in 291–296 (2. del).

\[ \begin{array}{|c|c|c|c|c|} \hline *_{5} & 1 & 2 & 3 & 4 \\ \hline 1 & 1 & 2 & 3 & 4 \\ \hline 2 & 2 & 4 & 1 & 3 \\ \hline 3 & 3 & 1 & 4 & 2 \\ \hline 4 & 4 & 3 & 2 & 1 \\ \hline \end{array} \ \ \ \ \ \ \ \ \begin{array}{|c|c|c|c|c|c|c|} \hline *_{7} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline 2 & 2 & 4 & 6 & 1 & 3 & 5 \\ \hline 3 & 3 & 6 & 2 & 5 & 1 & 4 \\ \hline 4 & 4 & 1 & 5 & 2 & 6 & 3 \\ \hline 5 & 5 & 3 & 1 & 6 & 4 & 2 \\ \hline 6 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{array} \]

\[ \begin{array}{lr} (a) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (b) \end{array} \]

Tabela 1: tablici za množenje po modulu 5 (a) oziroma 7 (b).

Če bi delali z veliko večjimi števili, bi bili hočeš nočeš prisiljeni uporabiti kaj bolj učinkovitega (kot sestavljanje tabele). V resnici iščemo v splošnem rešitev diofantske enačbe \(a\,y-p\,x=b\), kjer smo število 7 nadomestili s \(p\). Za obstoj rešitve je očitno potrebno, da je število \(b\) večkratnik največjega skupnega delitelja števil \(p\) in \(a\), tj. \(D(p,a)\,|\,b\). Ni pa to samo potreben, temveč tudi zadosten pogoj za obstoj rešitve (glej M. Juvan, O Evklidovem algoritmu, Presek 21 (1993-94), str. 116–121). Če je torej \(p\) praštevilo, \(a\) pa ni njegov večkratnik, potem velja \(D(p,a)=1\) in je ta pogoj vedno izpolnjen. Za iskanje rešitve pa je najbolj primerno uporabiti razširjni Evklidov algoritem iz že omenjenega Presekovega članka, ki je do današnjih dni ostal najbolj učinkovit.

Zgled: Evklidov algoritem (levo) in razširjeni Evklidov algoritem (desno). Rešujemo (linearno) diofantsko enačbo \(4864x + 3458y = 38\) in postavimo \(p_0 = 0\) in \(p_1 = 1\):

\[\begin{equation} \begin{array}{lr} 4864 = {\bf 1} \cdot 3458+1406 & p_2 := p_1-{\bf 1} \cdot p_0 = 1 \\ 3458 = {\bf 2} \cdot 1406+646 & p_3 := p_2-{\bf 2} \cdot p_1 = -2 \\ 1406 = {\bf 2} \cdot 646+114 & p_4 := p_3-{\bf 2} \cdot p_2 = 5 \\ 646 = {\bf 5} \cdot 114+76 & p_5 := p_4-{\bf 5} \cdot p_3 =-27 \\ 114 = {\bf 1} \cdot 76+38 & p_6 := p_5-{\bf 1} \cdot p_4 = 32 \\ 76 = {\bf 2} \cdot 38+0 & p_7 := p_6-{\bf 2} \cdot p_5 =-91 \end{array} \end{equation}\]

Ko pridemo do \(x = p_7 = -91\), lahko dobimo \(y = 128\) kot rešitev linearne enačbe. Končno imamo: \[ 4864 \cdot (-91) + 3458 \cdot (128) = 38. \]

Zdi se, da smo zbrali vse začimbe, potrebne za okusno jed. Na koncu izpopolnimo našo tehniko do te mere, da bo primerna za večkratno uporabo.

Izrek o ostankih

V rubriki Matematično razvedrilo je kitajski izrek o ostankih omenil že E. Rusjan, Kako “uganeš” število, Presek 4/4 (1976-77) , str. 237–239. Za tiste, ki jih je pričel zanimati ta izrek, je članek zelo primeren, saj govori o čarovniških sposobnostih (priporočam pregled članka še pred nadaljnjim branjem).³

Izrek 6.1 (Kitajski izrek o ostankih) Naj bodo \(a_1, a_2, \dots , a_r\) cela števila, \(m_1, m_2, \dots, m_r\) pa naravna števila, ki so paroma tuja, tj. \(D(m_i, m_j) = 1\) za \(i \ne j\). Naj bo \(M = m_1 \cdot m_2 \cdot \ldots \cdot m_r\) in število \(x \in \{0,1,\dots,M-1\}\) tako, da ima pri deljenju z \(m_i\) ostanek \(a_i\) za \(i \in \{1,2,\dots,r\}\), tj. \[\begin{equation} \begin{array}{cc} x \equiv a_1 && \pmod{m_1},\\ x \equiv a_2 && \pmod{m_2},\\ &\vdots&\\ x \equiv a_r && \pmod{m_r}. \end{array} \tag{6.1} \end{equation}\] Potem je \(x\) natančno določeno število. Izračunamo ga na naslednji način: za \(M_j = M/m_j\) poiščemo \(y_j = M_j^{-1}\!\!\mod m_j\), za \(j=1,\ldots, r\) in nato sestavimo \[\begin{equation} x = a_1 \cdot M_1 \cdot y_1 + \cdots + a_r \cdot M_r \cdot y_r \!\!\mod M. \tag{6.2} \end{equation}\]

Zaradi angleškega imena Chinese Remainder Theorem se za ta izrek pogosto uporablja kratica CRT. Relacijam v (6.1) pravimo kongruence in jih beremo na naslednji način: \(x\) je kongruenten \(a_i\) po modulu \(m_i\), njihov pomen pa je v tem, da imajo števila na obeh straneh relacije enak ostanek pri deljenju z ustreznim modulom. V zadnji enakosti pa mod na desni strani označuje ostanek dane vsote pri deljenju z modulom \(M\). Sedaj pojasnimo še oznako \(M_j^{-1}\) oziroma \(M_j^{-1}\!\!\mod{m_j}\). Le-ta je rešitev kongruence \(M_j\cdot y_j \equiv 1\pmod{m_j}\) (tj. multiplikativni inverz števila \(M_j\) po modulu \(m_j\)) oziroma linearne diofantske enačbe \[ M_j\cdot y_j +m_j \cdot z_j = 1. \]

Dokaz. Število \(M_i^{-1}\) oziroma \(y_i\) izračunamo s pomočjo razširjenega Evklidovega algoritma. To lahko storimo vedno, ker so si števila \(m_1,m_2,\dots,m_r\) paroma tuja in sta si zato tudi števili \(M_j\) in \(m_j\) tuji. Izraz (6.2) res zadovoljuje vse pogoje iz (6.1) saj je vsak njegov seštevanec, z izjemo \(i\)-tega \(a_i\,M_i\,y_i\) deljiv z \(m_i\), v \(i\)-tem seštevancu pa sta števili \(M_i\) in \(y_i\) obratni po modulu \(m_i\) in zato res dobimo ostanek \(a_i\). Tudi dokaz enoličnosti rešitve ni dosti težji. Če obstajata dve rešitvi \(x\) in \(x'\) v množici \(\{0,1,\dots,M-1\}\), potem velja \(m_i\,|\,(x-x')\) za \(i\in \{1,2,\dots,r\}\) in od tod (ker so števila \(m_1,m_2,\dots,m_r\) paroma tuja) tudi \(M\,|\,(x-x')\) oziroma \(x=x'\).

Primer 6.1 Poiščimo tako naravno število \(x\), ki daje ostanek \(2\) pri deljenju s \(3\), ostanek \(3\) pri deljenju s \(4\) in ostanek 1 pri deljenju s \(5\) in je manjše od \(3\cdot 4\cdot 5=60\). Z uporabo razširjenega Evklidovega algoritma za

• \(m_1=3\) in \(M_1=4\cdot 5 = 20\), pridemo do \(20 \cdot 2 + 3\cdot (-13) =1\) in \(M_1\cdot y_1 = 40\),

• \(m_2=4\) in \(M_2=3\cdot 5 = 15\), dobimo \(15 \cdot 3 +4\cdot (-11) =1\) in \(M_2\cdot y_2=45\),

• \(m_3=5\) in \(M_3=3\cdot 4 =12\), zaključimo še \(12 \cdot (-2) +5 \cdot 5 = 1\) in \(M_3\cdot y_3 = -24\).

Tako je rešitev \(x=2\cdot 40 +3\cdot 45 +1\cdot (-24) =191 \bmod{60}=11\).

Ko enkrat izračunamo produkte \(M_1\cdot y_1,\dots,M_r\cdot y_r\), lahko hitro postrežemo z odgovori za različne \(a_1,\dots,a_r\).

Peskovnik 6.?: KIO primer za \(r=2\) in vse možne ostanke (\(a_i\))

TO-DO:

1. everywhere: Add caption with instructions (what is the reader expected to do and what to expect from this interaction)

• we do not want to search for this in text. Poseben primer KIO za \(r=2\). \(x \cong a \pmod{m_1}\) in \(x \cong b \pmod{m_2}\)

2. everywhere: (LŽ) Initials of the author and of the one who was improving (output?),
3. vnesi prvo število –> izberi modul \(m_1\) (ali kar je ustrezno glede na članek) vnesi drugo število –> izberi modul \(m_2\)
4. Generiraj tabelo (česa?) Postavi M v prazni kvadrant in bo morda bralec ugotovil, da gre za tabelo M-jev. Še bolje tja postaviti: a
5. everywhere: Is the interaction at the right place?
6. everywhere: English version

Še nakaj interaktivnih aplikacij v povezavi z kitajskim izrekom o ostankih.

---

---

Preden zaključimo prvi del, naj omenimo bralcem, da smo o kongruencah v Preseku že pisali:

• F. Forstnerič, O kongruencah, Presek 7/3 (1979/80), str. 145–152;

• B. Lavrič, Ogrejmo se za kongruence in D. Pagon, Kongruence in Eulerjev izrek, Presek 15/4 (1987/88), str. 193 in str. 194–196.

6.7 Eliptične krivulje

6.8 Generatorji psevdonaključnih števil

6.8.1 Linearni kongruenčni generator

6.8.2 Blum-Micali algoritem

---

1. Taka lastnost je res nekaj izjemnega, saj v ravnini recimo sploh ne ločimo sence kroga in kvadrata - v obeh primerih gre za daljico. Morda pa bralca bolj zanima geometrija kakor algebra, o kateri bomo govorili v nadaljevanju. V tem primeru je zanj primerna naloga, ki jo je avtor tega sestavka reševal v osmem razredu osnovne šole na šolskem tekmovanju. Poiščite ključ, katerega omenjene projekcije so krog, kvdarat ter enakostranični trikotnik.↩

2. Zgodbo smo za naše potrebe priredili, glejte pa tudi V. Batagelj, Bistrovidec: Razbita jajca, Presek 11/2, str. 130.↩

3. Glej ga zlomka! Sprva je avtor mislil, da se o izreku v Preseku še ni pisalo. Časa, da bi prelistal 30 letnikov in več, v vsakem povprečno po 6 številk, torej čez 180 zvezkov, povprečno po 60 strani, tj. skoraj 11.000 strani, pa ni bilo. Vendar je to danes, ko smo spravili vse Preseke v digitalno obliko, precej lažje preveriti. Da pa vam prihranimo pot v knjižnico, vas bomo lahko kmalu napotili kar na internet. ↩