i
i
“1524-Jurisic-Racunala” — 2010/8/25 — 10:52 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 30 (2002/2003)
Številka 5
Strani 290–296
Aleksandar Jurišíc:
RAČUNALA NOVE DOBE, 2. del
Ključne besede: matematika, algebra, grupa, obseg, seštevanje, mno-
ženje.
Elektronska verzija: http://www.presek.si/30/1524-Jurisic.pdf
c© 2003 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.
Matematika I
RAČUNALA NOVE DOBE, 2. del
A1atem at iko lahko definiramo kot predmet , pri katerem nikoli ne vemo, o čem
govorimo, niti nikoli ne vemo, ali j e tisto, kar pravimo, resnično .
Bertrand Russell
V pr ejšnji šte vilki Preseka smo z analizo seštevanj a in mn oženj a naravnih ,
celih oziroma racionalnih šte vil vp eljali po jma grupe in obseg, ki imata
pomembno vlogo v algebri. Ponovimo:
V grupi (G,o) velja:
(G I) za vsaka elementa a, bEG je a o bE G;
(G2) obs taja tak element e E G, da za vsak element 9 E G velja e o 9 =
= g o e = g ;
(G3) za vsak element 9 E G obstaja t ak element f E G, da je g o f =
= f o g = e;
(G4) za vse elemente a, b,c E G velja (a o b) o c = a o (b o c).
V obsegu (O ,+,*) pa velja :
(Ol ) par (0 ,+) je grupa z enoto O;
(02) par (O\{O}, *) je grupa z enoto 1;
(03) za vse elemente a, b,c E O je a * (b+ c) = a *b+a *c in (b+ c) *a =
= b *a + c *a.
V tem sestavku bomo odgovorili na vprašanja o najmanjših gru pah in
obsegih t er na še nekatera sorodna vprašanja, naš cilj pa so končni obsegi,
t. j . končne st rukt ur e, v katerih bomo znali ne sa mo seštevati in mn ožiti ,
pač pa tudi odštevati in deliti .
Gotovo ste hitro ugotovili , da mora imeti grupa zaradi aksioma (G2)
vsaj en element, enot o e namreč, obseg pa vsaj dva, enoto za operacijo "+"
in enoto za operacijo "*" . Nad alje se ni te žko prepričati , da en element v
primeru grupe že zadošča, sa j eoe = e izpolnjuje vse aksiome (G1)-(G4) .
V primeru obsega z dvema eleme ntoma enako velja za multiplikativno
gru po: 1 * 1 = 1 izpolni aksiom (02) .
Ne pozabite, da operacij i "+" in "*" ne predstavljata (nujno) obi-
čajnega sešt evanj a in množenj a . V tem sestavku bomo spoz nali kar nekaj
takih obsegov. V vsakem obsegu je pr odukt poljubnega elementa a z
adit ivno enoto Oenak O, saj je O*a = (0+0) * a = O*a +O*a (upoštevali
smo (G2) in (03)) . Če odšt ejemo 0 * a, res dobimo 0 * a = O. Podobno
dobimo, da je t udi a * O = O. V primeru najmanj šega obsega zato velja
O* O= O in O* 1 = O= 1 * O, kjer je 1 mul tiplikativna enota.
Matematika
Kako pa je z gru po, ki ima dva elementa , npr. enot o e in a? Poleg
eoe = e in eo a = a = a o e mora zaradi (G3) in e =1= a veljati še a c a = e
in že so izpolnj eni vsi aksiomi (G1)-(G4) . Tor ej velja za obseg z dvem a
elementoma in pravkar odkrito adit ivno gru po t udi aksiom (0 1). Zlahka
preverimo še (03), torej smo že našli najmanj ši obseg.
Vrnimo se k vp rašanju , koliko informacij potrebujemo za določitev
gru pe kot matematičnega objekta . Na to vprašanje je let a 1854 odgo-
voril Arthur Cayley. Po analogij i s tabe lo množenj a je vp eljal t abelo
za poljubno binarno operacijo, ki j i bomo rekli komponiranje. Elemente
mn ožice C , v kateri je definirano komponiranje, razpor edimo v zgornjo
vrstico tabe le in v enakem vrst nem redu še v levi stolpec tabele (imenovali
ju bomo koordinatna vrstica in stolpec). V polja tabele pa vpi šemo
ustrezn e kompozitume (t ab eli 6a in 6b) .
+ O 1
O O 1
1 1 O
(a)
* O 1
O O O
1 O 1
(b)
Tabela 6. Naj manjši obs eg im a dva element a, tab e li za nj ego vi o peracij i pa sta (a) za
seštevanje in (b ) za m no ženje.
Gotovo ste opazili, da je 1+1= O. 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 nism o imeli izbire pri določanju t abele,
pri gru pi s št ir imi elementi pa obstajata že natanko dve različni gru pi (ena
ustreza grupi sim etrij pravokotnika, drugo pa bos te spo znali v naslednjem
raz de lku) .
P raštevilski obseg ~p
Namesto s celimi števili bomo tokrat računali
z ostanki pri deljenju s 13, t .j . z eleme nti iz
mn ožice ~ 13 = {O, 1, .. . , 12}. Računamo na
naslednji način : šte vili sešt ejemo ali zmnož imo
t ako, da običajni rezul t at nadomestimo z nje-
govim ostankom pri deljenju z m odulom 13,
npr. 7 + 13 9 = 7 + 9 mod 13 = 3 in 5 *13 4 =
= 5 . 4 mod 13 = 7, saj ima pr i deljenju s 13
vsota 16 ostanek 3, produkt 20 pa ostanek 7
(tabe la 7 in slika 1) .
!J _--~
S lika 1. Prika z računanja po
modulu 13.
+ 13 O 1 2 3 4 5 6 7 8 9 10 11 12
O O 1 2 3 4 5 6 7 8 9 10 11 12
1 1 2 3 4 5 6 7 8 9 10 11 12 O
2 2 3 4 5 6 7 8 9 10 11 12 O 1
3 3 4 5 6 7 8 9 10 11 12 O 1 2
4 4 5 6 7 8 9 10 11 12 O 1 2 3
5 5 6 7 8 9 10 11 12 O 1 2 3 4
6 6 7 8 9 10 11 12 O 1 2 3 4 5
7 7 8 9 10 11 12 O 1 2 3 4 5 6
8 8 9 10 11 12 O 1 2 3 4 5 6 7
9 9 10 11 12 O 1 2 3 4 5 6 7 8
10 10 11 12 O 1 2 3 4 5 6 7 8 9
11 11 12 O 1 2 3 4 5 6 7 8 9 10
12 12 O 1 2 3 4 5 6 7 8 9 1011
(a)
Matematika I
*13 O 1 2 3 4 5 6 7 8 9 10 11 12
O O O O O O O O O O O O O O
1 O ~ 2 3 4 5 6 7 8 9 10 11 12
2 O 2 4 6 8 10 120 3 5 7 9 11
3 O 3 6 9 12 2 5 8 11 0 4 7 10
4 O 4 8 12 3 711 2 6 10 0 5 9
5 O 5 10 2 7 12 4 9 0 6 11 3 8
6 O 6 12 5 11 4 10 3 9 2 8 0 7
7 O 7 0 8 2 9 3 10 4 11 5 12 6
8 O 8 3 11609 4 12 7 2 10 5
9 O 9 50 10 6 2 11 7 3 12 8 4
10 O 10 7 40 11 8 5 2 12 9 6 3
11 O 11 9 7 5 3012 108 6 4 2
12 O 12 11 10 9 8 7 6 5 4 3 2 0
(b)
Tabela 7. Seš tevanje po modulu 13 (a) , množenje po modulu 13 (b) .
Če želimo sešte t i ali zmnožit i več št evil iz ~13 , lahko pridemo do pr avega
rezultat a t udi tako, da šte vila najprej sešteje mo oziroma zmnožimo kot
običajna cela števila in šele nato poiščemo ost anek pri deljenju s 13. To
pomeni , da iz zakonov o združevanju celih števil za seštevanje in mn oženj e
(asociativnost) ter zakona o razčlenjevanju (distributivnost) sledi veljav-
nos t zakonov o združevanj u za seštevanje in mn oženje ter razčlenjevanju
po modulu .
Pozoren br alec bo opazil, da se v vsakem stolpc u in v vsaki vrstici
t ab ele za seštevanje nahajajo prav vsi element i iz ~1 3' Podobno velja
t udi za tabelo mn oženj a , če odmis limo vse ničle . (Če bi 13 nadomestili s
14, bi vide li, da t ab ela množenja po modulu 14 nima te lastnost i; le-t a je
rezerviran a sa mo za prašte vila. ) Torej lahko s pomočjo tabe l 7(a) in 7(b)
najdemo tudi razlike in kvociente. Če želimo izračunati 2 : 13 7, iščemo
odgovor na vprašanje, 7 krat koliko je 2. V tabe li 7(b) izberemo vrstico,
ki ustreza šte vilu 7, in ugotovimo, da se šte vilo 2 nah aj a v stolpc u, ki
pripad a številu 4. Zato zaklj učimo, da je 2 :13 7 = 4. Do enakega
zaklj učka bi pr išli tudi , če bi št evilu 2 pri št eli šte vilo 13 to likokrat , da bi
dobljena vsot a postala deljiva s 7 in bi nato izračunali kvocient . Povejmo,
da ne moremo izračunati 2 :1 4 7, torej 2 : 7 v množici ~14 ' Zakaj ne?
S pomočjo tabe l se ni tež ko prepričati , da je trojica (~13 , +13 , *13)
obseg. Prav tako hitro ugotovim o, da je (~n , +n) grupa za poljubn o
naravno število 11. Z razširjenim Evklidovim algori t mom (glej članka
I Matematika
M. Juvana, o Evklidovem algoritmu , P resek 21 (1993-94), str . 116-121 ,
ter A. Juri š i ča, Kako deliti skrivnost?, Presek 29 (2001-02), str. 356-
364) , pa lahko enako pokažemo tudi za (~p \ {O}, *p) , kjer je p po ljubno
praštevilo. Tako pridemo do praštevilskega obsega (~p , +p,*p).
Tab ele in grupe
Sedaj si oglejmo tabele nekoliko pobliže. Vprašali se bomo, kako lahko
iz tabele ugot ovimo, ali gre za grupo. Pri tem bomo opazovali naslednje
last nosti:
(TI) V tabeli se lahko po javijo samo tisti elementi, ki jih komp oniram o.
(T2) Ena vrstica in en stolp ec morata biti element za elementom enaka
koordinatni vrstici in koordinatnemu stolpcu , množica enot v tabeli
pa j e simetrična glede na glavno diagonalo, t .j. diagonalo, ki izhaja
iz levega zgornj ega kota.
(T3) V vsaki vrstici in vsakem stolpcu se pojavi vsak element natanko
enkrat.
(T4) V tabeli si izberimo enoto e in v njeni vrstici oziroma stolpcu še
elem ent r oziroma s . Potem je elem ent , ki leži v isti vrstici kot s in
istem stolp cu kot r , enak s or, (tabela 8(b)).
o o x' Y
? S yi s or s
r e x r e
(a) (b)
Tabela 8.
Lastnost (TI) je ekvivalent na zaprtosti množice za komponiranje, med tem
ko j e la s t n o s t (T2) e k v iva len t n a obstoju e n o te . Tablicam, ki z a d ov o lj u jejo
last nost (T3) , pravimo latin ski kvadrati . Lastnost (T3) je ekvivalent na
zahtevi, da sta za polj ubna elementa a in b enačbi a o x = b in x o a =
= b rešljivi, saj v vrstici oziroma stolpcu, ki ust reza elementu a, poiščemo
element b, katerega stolpec oziroma vrstica ustreza elementu x . Če si
za b izberemo enoto, potem nam ta lastnost zagotavlja obstoj inverznega
elementa za vsak a. Prepričajmo se še, da velja last nost (T4) v vsaki
Matematika I
grupi z enoto e (tabela 8(b)). Iz x o y = e, x o x' = r in yi o y = s namreč
sled i y o x = e in
yi OX' = (yi oe) OX' = yi oeox' = (yi o (yox)) ox' = (yi oy) o (xox') = s c r.
Velja pa tudi obratno: pogoji (T1)-(T4) nam zagotavljajo, da tabela za
komponiranje ustreza neki grupi .
Izrek. Tabela za komponiranje ustreza lastnostim (T1)-(T4) natanko
takrat, ko je tabela neke grupe.
Dokaz. Prepričati se moramo le še, da iz (T1)-(T4) sledi asociativnost.
Najprej izpeljemo asociativnost za elemente b-l, bin c, t.j. c = (b- 1 o b) o
c = b- 1 o (b o c). Seveda lahko privzamemo e -=1= b in c -=1= b-l, saj je tedaj
pogoj (G4) očitno izpolnjen. V tabeli izberemo vrstici e in b ter stolpca
cin b- 1 . Zapišemo ustrezne produkte, uporabimo (T4) in dobimo želeno
relacijo (tabela 9(a)) .
o e b- 1 o boe b
e = b- 1 ob e = b- 1 o (b o e) b- 1 a ao(boe)=(aob)oe aob
b boe e b-
1 b- 1 o (boe) = e e
(a) (b)
Tabela 9.
Sedaj pokažimo asociativnost še za poljubne elemente, t .j. ao(boc) =
= (a ob) o C. Privzamemo a -=1= b- 1 in c -=1= e, kajti sicer sledi želena relacija
iz pravkar obdelanega posebnega primera. Izberemo si vrstici a in b- 1 ter
stolpca bo cin b ter uporabimo lastnost (T4) (tabela 9(b)) .
Končni obseg GF(pn)
Pokažimo, da tabeli 10(a) in 10(b) ustrezata grupnima operacijama in
da je množica binarnih trojic {OOO, 001, 010, 011,100,101,110 , 111} za ti
operaciji obseg.
Zakon o združevanju (asociativnost) za seštevanje je pravzaprav oči­
ten, saj seštevanje poteka tako, da seštevamo trojice po mestih (prvo,
drugo in tretje) po modulu 2 (tabela 6(a)). Zato označimo to grupo
z (lZ2 x lZ2 X lZ2, +2) ' Zakona o združevanju za množenje in zakona o
razčlenjevanju (distributivnost) pa ni tako lahko neposredno preveriti. Če
pa v ta namen uporabimo zgornji izrek, si lahko pomagamo z zakonom o
zamenjavi, saj sta tabeli simetrični glede na glavno diagonalo.
IMatematika
+ 000 001 010 011 100 101 110 111
000 000 001 010 011 100 101 110 111
001 001 000 011 010 101 100 111 110
010 010 011 000 001 110 111 100 101
011 011 010 001 000 111 110 101 100
100 100 101 110 111 000 001 010 011
101 101 100 111 110 001 000 011 010
110 110 111 100 101 010 011 000 001
111 111 110 101 100 011 010 001 000
* 000 001 010 011 100 101 110 111
000 000 000 000 000 000 000 000 000
001 000 @QI] 010 011 100 101 110 111
010 000 010 111 101 011 @QI] 100 110
011 000 011 101 110 111 100 010 @QI]
100 000 100 011 111 010 110 @QI] 101
101 000 101 @QI] 100 110 011 111 010
110 000 110 100 010 @QI] 111 101 011
111 000 111 110 @QI] 101 010 011 100
(a) (b)
Tabela 10. Seš tevanje (a) , množen je (b ).
Za konec vključimo v našo zgodbo še pol ino me s stopnjo, rnanjso od
n, n E lN, in s koeficient i iz obse ga (~p , +p, *p), kjer je p prašt evilo.
Te po linome seštevamo na enak način kot števila v tabeli l O(a), le da
tokrat seštevamo enakoležne koeficiente. Množi mo jih tako, da običajni
produkt zmanjš amo po modulu nekega pol inoma stopnje n , ki ga ne
moremo razcepit i v obsegu ( ~p, +p,*p). Tako zopet dobimo končni obseg .
Matematikom je celo usp elo dokazati, da mora biti vsak končni obseg t ake
oblike in da velja za množenj e zakon o zamenjavi (Wedderburn ov izrek), a
to že presega okvir našega razmišljanja . Omenimo le še, da ji h imenujemo
Galoisovi obsegi in ji h označimo z GF(pn). Za n = 1 dobimo seveda
praštevilsk i obseg.
Primer. Naj bo n = 3, p = 2 (tabeli 6(a) in 6(b)), za nerazcepni polinom
pa si izb erem o x 3 +x 2 +1. Po tem v zgornj ih binarn ih trojicah prvo mesto
ustreza koeficientu ob x 3 , drugo koefic ientu ob x 2 , t retje pa konstant nemu
koeficientu.
Opomba. Osnova za Evklidov algoritem je last nost , da lahko za vsak par
naravnih šte vil a in b, a > b, najdemo natanko določeni števili q in r , da
velj a a = qb + r , kjer je ost anek r manjši od b. Za polinoma a(x ) in b(x )
nad končnim obseg om, st( a) > st(b) (st je oznaka za stopnjo po linoma) pa
velja a(x ) = q(x )b(x)+r(x) , kjer je st(b) > st(r) . Za zgled po kažimo, kako
z razširj enim Evklidovim algori tmom poiščemo obratni element polinom a
x 4 + x + 1 v obsegu GF(25 ) z nerazcepnim po linomom x 5 + x 2 + 1. Leva
stran ustreza Evklidovemu algoritmu, desn a pa razširj enemu delu :
x5+x2 + 1 = x(x4 +x+ l)+x+ l
x4+x+ l = (x3+x2+x+ l)(x+ l)+ 1
x · l+0= x
(x3+x2+x+ l}x+ l = x4+x3 +x2 + 1
Matematika I
N aloge
1. Isto grupo lahko srečamo v različnih preoblekah. Prepričaj se
o tem za grupo ( ~4, +4) in množico {1, -1, i, -i}, kjer je i =
= R , z običajnim množenjem. Potrebno je najti bijekcijo iz ~4
v {1, - 1, i , -i}, ki preslika vsoto dveh elementov v produkt njunih
slik. Taki preslikavi pravimo izom orfizem .
2. Znano je, da je mu ltiplikativna grupa polj ubnega končnega obsega
ciklična, kar pomeni, da v grupi obstaja tak element, da so vsi
elementi grupe njegove potence. Prepričaj se, da je ciklična grupa z
n elementi izomorfna grupi (~n, +n) (element 1 generira s svojimi
večkratniki, kakor vaditivnem pr imeru pravimo potencam, vse
elemente) . To grupo označimo na kratko s On'
Trditev preveri najprej na pr imeru (tabela 7(b) in 10(b)).
3. Diederska grupa Dn je grupa simetrij pravilnega n-kotnika. Do-
kaži, da v grupi D 3 ne velja zakon o zamenjavi (komutativnost)
(grup o D 3 lah ko predstavimo t udi kot grupo permutacij t reh ele-
mentov 53)'
4. Nas led nja zanimiva grupa ima 8 elementov in ji pravimo kveiemi-
onka (tabela 11) . Poišči njeno tabelo množenja.
moč ime grupe
1 Cl
2 C2
3 C3
4 C4 , C2 X C2
5 C5
6 C6 , D3
7 C7
8 Cs , C2 X C4 , C2 X C2 X C2 , o«; o,
9 Cg , C3 X C3
10 ClO, D lO
Tabela 11 . Moč gru pe je število njenih elementov. Zgornja tabela vsebuje vse grupe
z največ desetimi elementi.
Za nadaljnje branje priporočamo: 1. Grossman in W. Magnus, Grupe
in njihovi grafovi, Školska knjiga Zagreb, 1975 in internet, npr .
ht tp : //members . trip od . co m/ dogschoo l ii, za zrelejše bralce pa
Vidav, Algebra, Mladinska knjiga, 1972.
Aleksandar Jurišič.