Algebarske strukture: vježbe (prema predlošku i zadacima Martine Balagović Marcele Hanzer) [PDF]

Zitiervorschau

Algebarske strukture vjeˇ zbe prema predloˇsku i zadacima Martine Balagovi´c i Marcele Hanzer

natipkali, proˇsirili i uredili

´ Matija Baˇ sic ´ Aleksandar Milivojevic ´ Sanjin Ruˇ zic

ˇiliˇ Sveuc ste u Zagrebu ˇki fakultet Prirodoslovno-matematic ˇki odsjek Matematic

(skripta ne moˇze zamijeniti vjeˇzbe)

Sadrˇ zaj 1 Grupe

1

1.1

Motivacija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Definicija grupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Osnovni primjeri grupa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.4

Podgrupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5

Homomorfizmi grupa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.6

Cikliˇcke i konaˇcnogenerirane grupe . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7

Strukturni teorem za konaˇcno generirane Abelove grupe . . . . . . . . . . . . . . 22

1.8

Grupe permutacija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.9

Lijeve/desne klase i Lagrangeov teorem . . . . . . . . . . . . . . . . . . . . . . . 28

1.10 Kvocijentne grupe i normalne podgrupe . . . . . . . . . . . . . . . . . . . . . . . 29 1.11 Automorfizmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.12 Sylowljevi teoremi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.13 Podsjetnik iz teorije brojeva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

i

Poglavlje 1 Grupe 1.1

Motivacija

Pojam grupe jedan je od najznaˇcajnijih u modernoj matematici. Primjene teorije grupa pojavljuju se u raznim granama matematike, a od kljuˇcnog su znaˇcaja i u fizici i kemiji. Simetrije Grupe se pojavljuju kao simetrije geometrijskih objekata. Promotrimo kvadrat u ravnini i transformacije ravnine koje preslikavaju taj kvadrat u njega samog. Takve transformacije zovemo simetrijama. Medu tim transformacijama su npr. rotacija za 90◦ u pozitivnom smjeru ili zrcaljenje preko pravca koji prolazi poloviˇstima dvaju nasuprotnih stranica kvadrata. Primjetimo da je kompozicija dviju simetrija ponovno simetrija, da je kompozicija asocijativna, da postoji simetrija (identiteta) koja ne ˇcini niˇsta s ravninom (djeluje kao neutralni element obzirom na kompoziciju), te da svaka simetrija ima inverz. Kaˇzemo da simetrije kvadrata ˇcine grupu i da ta grupa djeluje na kvadratu. Op´cenito, grupe simetrija pravilnih mnogokuta nazivamo diedarskim grupama. Grupe simetrije kristala u prostoru su vrlo vaˇzne u kemije, a simetrije fizikalnih sustava vaˇzne su u kvantnoj fizici pri odreˇzivanju degeneracija stanja. Grupe simetrija ploha (npr. sfere) su posebni primjeri Liejeve grupe, njihovo prouˇcavanje ˇcini posebnu granu matematike koju je 1884. godine utemeljio Sophus Lie. Prouˇcavanje veza izmedu geometrije, fizike i teorija grupa seˇze do danaˇsnjih dana. Primjeri gdje se na odredeni naˇcin koristi interakcija ovih podruˇcja su baˇzdarna teorija, teorija struna, rjeˇsenje Poincar´eove hipoteze. Grupe u kombinatorici Jedan od osnovnih objekata koje prouˇcavamo u kombinatorici su permutacije. Obzirom na kompoziciju permutacije ˇcine grupu Sn (moˇzemo ju smatrati grupom simetrija sustava od n objekata bez ikakve dodatne geometrijske strukture). Prisjetite se ˇsto znate o permutacija s 1

Algebarske strukture

1.1. Motivacija

kolegija Linearna algebra 1 i Diskretna matematika. Razni problemi u kombinatorici mogu se rijeˇsiti koriste´ci algebarske metode. Jedan primjer je Burnsideova lema koja nam daje odgovor na pitanje o broju mogu´cih bojanja nekog objekta uzimaju´ci u obzir da bojanja koja se mogu dobiti koriˇstenjem simetrija smatramo jednakima. Mnoge igraˇcke, poput Rubikove kocke i Slagalice s 15 polja (Fifteen-Puzzle), imaju netrivijalne simetrije te promatraju´ci takve objekte moˇzemo takoder zakljuˇciti da su grupe vrlo prirodni koncept koji se pojavljuje svugdje oko nas. Povijesni razvoj Povijesni razvoj pojma grupe usko je vezan uz rjeˇsavanje problema odredivanja nultoˇcaka polinoma koriste´ci samo osnovne raˇcunske operacije i korjenovanje (radikalima). Pokazuje se da ´ je radikalima mogu´ce rijeˇsiti svaku grupu reda manjeg ili jednog 4, a Evariste Galois (1811.1832.) je pokazao da postoje jednadˇzbe petog stupnja koje nisu rjeˇsive radikalima koriste´ci grupe. Neka je p polinom s racionalnim koeficijentima, a K = Q[x1 , ..., xn ] najmanji podskup kompleksnih brojeva koji sadrˇzi racionalne brojeva i sve nultoˇcke x1 , ..., xn polinoma p te je zatvoren na zbrajanje i mnoˇzenje. Skup svih bijekcija f : K → K koje poˇstuju zbrajanje i mnoˇzenje, a fiksiraju racionalne brojeve oznaˇcimo s Gal(p). Sve takve bijekcije permutiraju nultoˇcke polinoma, tj. Gal(p) je podgrupa grupe permutacija Sn . Galois je pokazao da za svaki polinom p koji je rjeˇsiv radikalima grupa Gal(p) ima posebno svojstvo (koje danas zovemo rjeˇsivost grupe), te pokazao da postoji polinom p takav da Gal(p) nema to svojstvo. To su samo zaˇceci mnogo ˇsire teorije koju nazivamo Galoisova teorija. Vrlo vaˇzan doprinos u razvoju teorije grupa u njenim poˇcecima, posebice u prouˇcavanju grupa permutacija, dali su Joseph Louis Lagrange, Augustin Louis Cauchy i Arthur Cayley. Grupe u teoriji brojeva Vrlo netrivijalne primjene algebarskih metoda moˇzemo prona´ci u teoriji brojeva. Zapravo, koncept grupe se razvio i zahvaljuju´ci nekim ranim pokuˇsajima da se rijeˇsi Veliki Fermatov teorem. U kolegiju ´cemo koristiti neke osnovne pojmove vezane uz proste brojeve i djeljivost (vidite podsjetnik na kraju ove skripte), a ponekad ´cemo i koriste´ci teoriju grupa izvesti neke poznate teoreme (poput Eulerovog teorema). Danas je algebarska teorija brojeva jedno od najplodnijih podruˇcja matematike koje obiluje mnogim joˇs uvijek otvorenim pitanjima, ali i raznim primjenama (poput primjena u kriptografiji ). Grupe u topologiji Algebarska topologija bavi se prouˇcavanjem algebarskih invarijanti topoloˇskih prostora. Jedna takva invarijanta je fundamentalna grupa. Za topoloˇski prostor X s istaknutom toˇckom x0 promatramo homotopske klase puteva u X koji poˇcinju i zavrˇsavaju u x0 . Nadovezivanje ˇ petlji daje binarnu operaicju i skup homotopskih klasa π1 (X, x0 ) postaje grupa. Zelimo li pokazati da preslikavanje topoloˇskih prostora f : (X, x0 ) → (Y, y0 ) nije homotopska ekvivalencija, dovoljno je pokazati da preslikavanje f∗ : π1 (X, x0 ) → π1 (Y, y0 ) nije izomorfizam grupa.

2

1.2. Definicija grupe

1.2

Algebarske strukture

Definicija grupe

U ovom poglavlju ´cemo promatrati parove koji se sastoje od skupa i binarne operacije definirane na tom skupu. Za binarnu operaciju kaˇzemo da je dodatna algebarska struktura na skupu. Op´cenitije, algebarska struktura se sastoji od skupa i konaˇcnog broja binarnih operacija. Prisjetite se definicije vektorskog prostora. Vektorski prostor je varijanta algebarske strukture (dana skupom te operacijama zbrajanja i mnoˇzenja skalarima). Topoloˇski prostor je takoder dan skupom i dodatnom strukturom (topologijom), ali u tom sluˇcaju se ne radi o algebarskoj strukturi. Matematiˇcka struktura na skupu moˇze imati razliˇcita svojstva (npr. asocijativnost, komutativnost, rjeˇsivost, kompaktnost, povezanost). Kroz sljede´cih nekoliko definicija i primjera obradit ´cemo najjednostavnije, ali vrlo vaˇzne algebarske strukture: grupoide, polugrupe, monoide i grupe. Definicija 1.2.1. Uredeni par (S, ·), pri ˇcemu je · : S × S → S binarna operacija, zovemo grupoid. Napomena 1.2.2. Vrijednost ·(x, y) piˇsemo x · y ili jednostavno xy (ako je jasno o kojoj se operaciji radi). Budu´ci da je S kodomena preslikavanja · za sve x, y ∈ S vrijedi x · y ∈ S. Da bismo to naglasili kaˇzemo joˇs da je binarna operacija zatvorena ili da je dobro definirana. Primjer 1.2.3. Oduzimanje prirodnih brojeva nije zatvorena operacija. Naime, oduzimanje moˇzemo definirati kao operaciju − : N × N → Z, ali struktura (N, −) nije grupoid. Na primjer, 1 − 2 6∈ N, iako vrijedi 1, 2 ∈ N. Definicija 1.2.4. Polugrupa je grupoid (S, ·) u kojem vrijedi asocijativnost, za sve x, y, z ∈ S (x · y) · z = x · (y · z). Primjer 1.2.5. Grupoid (Z, −) nije polugrupa. Zaista, (1 − 2) − 3 6= 1 − (2 − 3), pa ne vrijedi asocijativnost operacije −. Definicija 1.2.6. Monoid je polugrupa (S, ·) u kojoj postoji neutralni element (ili jedinica), tj. postoji e ∈ S takav da za sve x ∈ S vrijedi e · x = x · e = x. Primjer 1.2.7. Polugrupa (N, +) nije monoid. Naime, kad bi postojao neutralni element e ∈ N s obzirom na operaciju zbrajanja, posebno bi moralo vrijediti 1 + e = 1. No, nijedan prirodan broj nema to svojstvo (Nula nije prirodan broj!). Napomena 1.2.8. Neka je (S, ·) grupoid. Za element el kaˇzemo da je lijeva jedinica ako za svaki x ∈ S vrijedi el · x = x. Analogno definiramo desnu jedinicu kao element ed za koji vrijedi x · ed = x, za svaki x ∈ S. 3

Algebarske strukture

1.2. Definicija grupe

Ako u grupoidu (S, ·) postoje lijeva i desna jedinica, tada su one nuˇzno jednake. Zaista, oznaˇcimo s el lijevu jedinicu i s ed desnu jedinicu. Tada vrijedi el = el · ed = ed , pri ˇcemu smo u prvoj jednakosti iskoristili da je ed desna jedinica, a u drugoj smo iskoristili da je el lijeva jedinica. Ovo pokazuje da je jedinica u svakom monoidu jedinstvena. Primjer 1.2.9. Neka je S skup i definirajmo binarnu operaciju na tom skupu na sljede´ci naˇcin: x · y = y, ∀x, y ∈ S. Budu´ci da za sve x, y, z ∈ S vrijedi (x · y) · z = y · z = x · (y · z), struktura (S, ·) je polugrupa. Uoˇcimo da je svaki element skupa S lijeva jedinica. Dakle, u ovoj strukturi imamo viˇse lijevih jedinica, a prema prethodnoj napomeni onda znamo da nema desnih jedinica. 1 Zadatak 1.2.10. Neka je (S, ·) komutativna polugrupa i a ∈ S takav element da za svaki x ∈ S postoji yx ∈ S takav da x = a · yx . Pokaˇzite da je tada G monoid. Rjeˇ senje. Zbog komutativnosti je dovoljno pokazati da postoji lijeva jedinica. Za x = a postoji ya ∈ G takav da je a = a · ya . Zbog komutativnosti vrijedi a = ya · a. Tvrdimo da je ya lijeva jedinica. Zaista, ako je x ∈ G proizvoljan, onda je x = a · yx = (ya · a)yx = ya · (a · yx ) = ya · x.

Definicija 1.2.11. Grupa je monoid (G, ·) u kojem za svaki element x ∈ S postoji y ∈ S takav da vrijedi x · y = y · x = e. Kaˇzemo da je element y inverzni element elementa x. Primjer 1.2.12. Monoid (Q, ·) nije grupa. Zaista, neutralni element je 1, a za element 0 ∈ Q ne postoji inverz, tj. ne postoji q ∈ Q takav da bi vrijedilo q · 0 = 1. Napomena 1.2.13. Neka je (S, ·) monoid s jedinicom e i neka je x ∈ S. Za yl ∈ S kaˇzemo da je lijevi inverz od x ako vrijedi yl · x = e. Analogno definiramo desni inverz od x kao element yd za koji vrijedi x · yd = e. Ako u monoidu (S, ·) neki element x ima lijevi i desni inverz, tada su oni jednaki. Zaista, yl = yl · e = yl · (x · yd ) = (yl · x) · yd = e · yd = yd . Zato je u grupi inverz elementa x jedinstven i oznaˇcavamo ga s x−1 . 1

Primjetite da je postojanje lijeve/desne jedinice svojstvo, a odabir lijeve/desne jedinice dodatna struktura. No, za neutralni element u monoidu nemamo mogu´cnost odabira jer je jedinstven, pa odabir jedinice nije dodatna struktura.

4

1.2. Definicija grupe

Algebarske strukture

Napomena 1.2.14. Neka su a, b elementi grupe G. Tada je (ab)−1 = b−1 a−1 . Zaista, budu´ci da vrijedi b−1 a−1 ab = b−1 eb = b−1 b = e zakljuˇcujemo da je b−1 a−1 inverz elementa ab, pa tvrdnja slijedi zbog jedinstvenosti inverza. Primjer 1.2.15. Neka je G grupa, i a, b, c ∈ G. Tada je a = b ako i samo ako je ca = cb. Definicija 1.2.16. Ako u grupoidu (S, ·) za sve x, y ∈ S vrijedi x · y = y · x, onda kaˇzemo da je ta struktura komutativna (ili Abelova), pa tako moˇzemo govoriti o komutativnoj polugrupi, komutativnom monoidu ili komutativnoj grupi. Primjer 1.2.17. Neka je (G, ·) grupa u kojoj za svaki element a vrijedi a2 = e. Tvrdimo da je tada G komutativna grupa. Naime, (ab)(ab) = e = aa = aea = a(bb)a = (ab)(ba) / · (ab)−1 slijeva ⇒ ab = ba. D.Z. Neka je G polugrupa u kojoj postoji lijeva jedinica i lijevi inverz obzirom na tu lijevu jedinicu za svaki element, tj. vrijedi (∃e ∈ G)(∀x ∈ G) ex = x,

(∀x ∈ G)(∃y ∈ G) yx = e.

Dokaˇzite da je tada G grupa. Primjer 1.2.18. U ovom primjeru komentiramo potenciranje u grupi. Neka je (G, ·) grupa i a ∈ G. Definiramo a0 = e, a1 = a, a2 = a · a. Uoˇcite da zbog asocijativnost (a · a) · a = a · (a · a) ne moˇze do´ci do zabune ako piˇsemo a3 = a · a · a. Induktivno za n ∈ N definiramo an := an−1 · a. Nadalje, za n ∈ N definiramo a−n := (an )−1 . D.Z. Dokaˇzite da vrijedi a−n = (a−1 )n i an · am = an+m za sve n, m ∈ Z. Zadatak 1.2.19. Na skupu S = N0 × N0 definiramo operaciju ∗ formulom (x1 , y1 ) ∗ (x2 , y2 ) = (x1 + x2 , 2x2 y1 + y2 ). Kakva struktura je (S, ∗)? 5

Algebarske strukture

1.2. Definicija grupe

Rjeˇ senje. Lako se vidi da je ∗ dobro definirana operacija, budu´ci da za x1 , y1 , x2 , y2 ∈ N0 slijedi da je x1 + x2 , 2x2 y1 + y2 ∈ N0 . Provjerimo asocijativnost. Imamo
(x1 , y1 ) ∗ (x2 , y2 ) ∗ (x3 , y3 ) = (x1 + x2 , 2x2 y1 + y2 ) ∗ (x3 , y3 )
= (x1 + x2 ) + x3 , 2x3 (2x2 y1 + y2 ) + y3 = (x1 + (x2 + x3 ), 2x2 +x3 y1 + 2x3 y2 + y3 ) = (x1 , y1 ) ∗ (x2 + x3 , 2x3 y2 + y3 )
= (x1 , y1 ) ∗ (x2 , y2 ) ∗ (x3 , y3 ) , pri ˇcemu smo u tre´coj jednakosti iskoristili da je (N0 , +) polugrupa. U ostalim jednakostima smo jednostavno koristili definiciju operacije ∗. Ispitajmo sada postoji li neutralni element. Za poˇcetak, traˇzimo lijevu jedinicu. Da bi element (x0 , y0 ) bio lijeva jedinica, mora za svaki (x2 , y2 ) vrijediti (x0 , y0 ) ∗ (x2 , y2 ) = (x0 + x2 , 2x2 y0 + y2 ) = (x2 , y2 ), odakle slijedi x0 = 0 i 2x2 y0 = 0, tj. y0 = 0. Dakle, (0, 0) je lijeva jedinica. Provjerimo joˇs da je to i desna jedinica. Za svaki (x1 , y1 ) vrijedi (x1 , y1 ) ∗ (0, 0) = (x1 + 0, 20 y1 + 0) = (x1 , y1 ), pa zakljuˇcujemo da je (0, 0) i desna jedinica. Neka je sad (x1 , y1 ) ∈ N0 × N0 i ispitajmo postoji li njemu inverzni element. Ako je (x2 , y2 ) desni inverz od (x1 , y1 ), onda vidimo da mora vrijediti x1 + x2 = 0 i 2x2 y1 + y2 = 0. No, ako je x1 > 0, onda je nemogu´ce da postoji x2 ∈ N0 takav da x1 + x2 = 0, pa zakljuˇcujemo da je dana struktura monoid koji nije grupa. ♦ D.Z. Odredite kakva je struktura (R × R, ∗) pri ˇcemu je ∗ definirano a) formulom (x1 , y1 ) ∗ (x2 , y2 ) = (x1 , y1 y2 sin x2 ). b) formulom (x1 , y1 ) ∗ (x2 , y2 ) = (x1 , y1 y2 (x31 − 3x1 + 3)). Zakljuˇcimo ovo poglavlje definicijom navode´ci sve aksiome koje je potrebno provjeriti da bismo utvrdili da binarna operacija na skupu definira strukturu grupe. Definicija 1.2.20. Za skup G s binarnom operacijom · kaˇzemo da je grupa ako vrijedi (G0) (∀x, y ∈ G)(x · y ∈ G) (zatvorenost) (G1) (∀x, y, z ∈ G)((x · y) · z) = x · (y · z)) (asocijativnost) (G2) (∃e ∈ G)(∀x ∈ G)(x · e = x = e · x) (unitalnost) (G3) (∀x ∈ G)(∃y ∈ G)(x · y = e = y · x) (invertibilnost) 6

1.3. Osnovni primjeri grupa

1.3

Algebarske strukture

Osnovni primjeri grupa

Primjer 1.3.1. Na kolegijima Matematiˇcka analiza 1 i Teorija skupova formalno se definiraju skup prirodnih brojeva N i skup realnih brojeva R, te operacije zbrajanja i mnoˇzenja na njima. Na ovom kolegiju ´cemo pretpostavljati te definicije, kao i ˇcinjenice da su (N, +) i (N, ·) komutativne polugrupe (koji postaju monoidi ako skupu N dodamo nulu), a (R, +) i (R× , ·) komutativne grupe (ovdje R× oznaˇcava R \ {0}). Nadalje, na spomenutim kolegijima konstruira se skup Z cijelih brojeva, skup Q racionalnih brojeva i skup C kompleksnih brojeva. Koriste´ci konstrukciju tih skupova brojeva te definiciju algebarskih struktura (N, +, ·), odnosno (R, +, ·), moˇze se na prirodan naˇcin definirati zbrajanje i mnoˇzenje na skupovima Z, Q i C i pokazati da je je (Z, ·) komutativni monoid, a (Z, +), (Q, +), (C, +), (Q× , ·) i (C× , ·) komutativne grupe. Primjer 1.3.2. Ako je (V, +, ·) vektorski prostor, onda je (V, +) Abelova grupa. Primjer 1.3.3. Neka je S = {e} jednoˇclan skup te definirajmo binarnu operaciju na S formulom e · e = e. Tada je ({e}, ·) grupa koju nazivamo trivijalna grupa. Primjer 1.3.4. Promatramo (S 1 , ·), pri ˇcemu je S 1 = {z ∈ C : |z| = 1} jediniˇcna kruˇznica u kompleksnoj ravnini, a · operacija mnoˇzenja kompleksnih brojeva. Operacija · je zatvorena na S 1 . Zaista, za z1 , z2 ∈ S 1 vrijedi |z1 | = |z2 | = 1, pa je i |z1 · z2 | = |z1 | · |z2 | = 1 · 1 = 1. Dakle, z1 · z2 ∈ S 1 , pa je (S 1 , ·) grupoid. Provjerimo je li ova struktura polugrupa, tj. vrijedi li asocijativnost. Uoˇcimo da za z1 , z2 , z3 ∈ S 1 posebno vrijedi i z1 , z2 , z3 ∈ C, jer je S 1 ⊂ C. Kako u (C, ·) vrijedi asocijativnost, zakljuˇcujemo da je (z1 · z2 ) · z3 = z1 · (z2 · z3 ). Kaˇzemo da se asocijativnost u (S 1 , ·) nasljeduje iz (C, ·). Nadalje, (S 1 , ·) posjeduje neutralni element. To je upravo 1 = 1 + 0 · i. Ostaje provjeriti da za svaki z ∈ S 1 postoji inverzni element z −1 ∈ S 1 . Uoˇcimo da za proizvoljni z ∈ S 1 kompleksni broj z −1 = z1 zadovoljava z · z1 = 1. Moramo provjeriti da je z −1 ∈ S 1 . No, 1 1 |z −1 | = z = |z| = 11 = 1, dakle z −1 ∈ S 1 . Uoˇcimo i da je ova struktura komutativna. Dakle, (S 1 , ·) je Abelova grupa. D.Z. Pokaˇzite da za z1 , z2 ∈ C vrijedi |z1 z2 | = |z1 | · |z2 | i |z1 /z2 | = |z1 | / |z2 | (ako je z2 6= 0). Napomena 1.3.5. Ovdje smo se susreli s primjerom podgrupe (S 1 je podgrupa od C) i konceptom nasljedivanja asocijativnosti s ve´ceg skupa na njegov podskup. O podgrupama ´cemo govoriti neˇsto kasnije i vidjet ´cemo da su ova razmatranja vaˇzna kod kreiranja kriterija za provjeru kad je neki podskup podgrupa. Primjetite da nema smisla govoriti o nasljedivanju zatvorenosti, nasljedivanju neutralnog elementa ili invertibilnosti nekog elementa iz (C, ·) ve´ceg skupa. Naime, iako znamo da postoji z −1 ∈ C, treba dodatno provjeriti je li vrijedi z −1 ∈ S 1 . Sa stanoviˇsta teorije modela, razlika je u tome ˇsto aksiom asocijativnosti zapisujemo koriste´ci samo univerzalne kvantifikatore (∀, ”za svaki”), dok se u aksiomima o postojanju neutralnog elementa i inverza pojavljuju tvrdnje koje zapisujemo koriste´ci i egzistencijalni kvantifikatore (∃, ”postoji”). 7

Algebarske strukture

1.3. Osnovni primjeri grupa

S D.Z. Za n ∈ N definiramo Kn = {z ∈ C | zn = 1}. Zatim, definiramo K = n∈N Kn . Dokaˇzite da su (Kn , ·) i (K, ·) grupe. (Kn , ·) zovemo grupom n-tih korijena jedinice, a (K, ·) grupom korijena jedinice. D.Z. Neka je S skup. Odredite o kojoj se strukturi radi za (P(S), ∩), (P(S), ∪), (P(S), 4), gdje P(S) oznaˇcava partitivni skup od S, a 4 simetriˇcnu razliku (za skupove A, B je A4B = (A ∪ B) \ (A ∩ B)). Primjer 1.3.6. Neka je S skup. Oznaˇcimo li sa B(S) = {f : S → S | f je bijekcija}, onda je (B(S), ◦) grupa (pri ˇcemu ◦ oznaˇcava komponiranje). Ako je S = {1, 2, . . . , n}, onda je B(S) = Sn skup permutacija n-ˇclanog skupa. D.Z. Dokaˇzite da je kompozicija bijekcija bijekcija, da je kompozicija funkcija asocijativna i da je neutralni element obzirom na komponiranje identiteta. Pokaˇzite da komponiranje nije komutativna operacija. Primjer 1.3.7. Neka je V vektorski prostor. Definirajmo GL(V ) = {A : V → V | A je regularan linearni operator} . Tada je (GL(V ), ◦) grupa. Asocijativnost, postojanje jedinice i postojanje inverza su dokazane na Linearnoj algebri 1 i 2. Na Linearnoj algebri 1 i 2 je takoder dokazano da je kompozicija linearnih operatora ponovo linearan operator. Dakle, za A, B ∈ GL(V ) znamo da je A ◦ B linearan operator, pa preostaje pokazati da je regularan. Poznato je da je linearan operator regularan ako i samo ako mu je determinanta razliˇcita od nule, pa imamo det(A ◦ B) = det(A) det(B) 6= 0, gdje smo u prvoj jednakost iskoristili Binet-Cauchyev teorem. Zakljuˇcujemo da je i A ◦ B regularan operator, tj. A ◦ B ∈ GL(V ). Primjer 1.3.8. Za n ∈ N promatramo GL(n, R) = {A invertibilna realna matrica reda n}. Uz matriˇcno mnoˇzenje GL(n, R) ima strukturu grupe. Na Linearnoj algebri 2 je uspostavljen izomorfizam vektorskih prostora izmedu GL(V ) i GL(n, R) za realan n-dimenzionalan vektorski prostor V , a pri tom izomorfizmu kompozicija linearnih operatora odgovara matriˇcnom mnoˇzenju pridruˇzenih matrica, tj. grupe (GL(V ), ◦) i (GL(n, R), ·) su izomorfne (ˇstoviˇse, ovdje se radi o izomorfnim algebrama (GL(V ), +, ·, ◦) i (GL(n, R), +, ·, ·)). D.Z. Za n ∈ N promatramo SL(n, R) = {A ∈ GL(n, R) | det A = 1} , O(n, R) = {A ∈ GL(n, R) | AAτ = Aτ A = I} , SO(n, R) = {A ∈ O(n, R) | det A = 1} . Provjerite da je svaki od ta tri skupa grupa uz operaciju matriˇcnog mnoˇzenja. 8

1.3. Osnovni primjeri grupa

Algebarske strukture

Napomena 1.3.9. Grupa O(n, R) je grupa simetrija prostora Rn , a SO(n, R) grupa rotacija prostora Rn . Uvjerite se u to za n = 2. Primjer 1.3.10. Oznaˇcimo sa mZ = {mn | n ∈ Z} skup viˇsekratnika prirodnog broja m. Tada je (mZ, +) grupa. Primjer 1.3.11. Na skupu cijelih brojeva Z definiramo relaciju ∼m tako da x ∼m y ako m | x − y. Lako se provjeri da je to relacija ekvivalencije (D.Z.). Oznaˇcimo s [k] klasu ekvivalencije reprezentiranu s k ∈ Z. Kvocijentni skup je skup Zn = {[0] , [1] , . . . , [n − 1]} te definiramo operaciju +m zbrajanja modulo m na sljede´ci naˇcin [x] +m [y] = [x + y] . Tada je (Zm , +m ) grupa. Primjer 1.3.12. Ilustrirajmo to primjerom na (Z4 , +4 ). Napravit ´cemo tablicu mnoˇzenja”, ” tzv. Cayleyjevu tablicu, odakle moˇzemo iˇsˇcitati je li dana struktura grupa. +4 0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

Napomena 1.3.13. U ovoj skripti ´cemo koristiti oznaku Zn za skup {[0] , [1] , . . . , [n − 1]}, no naglasimo da je op´cenito preciznije taj skup oznaˇcavati s Z/nZ. Konstrukciju koju smo upravo vidjeli upamtite kao osnovni primjer kvocijentne grupe o kojima ´cemo priˇcati kasnije tokom semestra. D.Z. Neka je F = {f1 , f2 , f3 , f4 , f5 , f6 }, gdje su fi : R \ {0, 1} → R \ {0, 1}, i = 1, 2, ..., 6 definirane s f1 (x) = x, f2 (x) = 1 − x, f3 (x) =

x−1 x 1 1 , f4 (x) = , f5 (x) = , f6 (x) = . x x x−1 1−x

Dokaˇzite da je (F, ◦) grupa (kako biste provjerili zatvorenost napravite Cayleyevu tablicu te koriste´ci tablicu utvrdite da svaki element ima inverz). D.Z. Odredite sve mogu´ce (bitno razliˇcite) Cayleyjeve tablice za grupu od 4 elementa. Primjer 1.3.14. Na skupu Zm moˇzemo definirati binarnu operaciju ·m mnoˇzenja modulo m na sljede´ci naˇcin [x] ·m [y] = [xy]. Op´cenito, monoid (Zm , ·m ) nije grupa (ˇcak i ako izbacimo [0]). Na primjer, [2] nema inverz u Z4 . Zaista, kad bi postojao [x] ∈ Z4 takav da je [2] ·4 [x] = [1], imali bismo [2] ·4 [x] = [2x] = [1] . No, klasa [2x] se sastoji od parnih brojeva, pa ne sadrˇzi broj 1. Zakljuˇcujemo da [2] nema inverz u monoidu (Z4 , ·4 ). 9

Algebarske strukture

1.3. Osnovni primjeri grupa

Promatrajmo sad (Z× p , ·p ), gdje je p prost. Tada za svaki n ∈ {1, 2, . . . , p − 1} vrijedi (n, p) = 1 (gdje (n, p) oznaˇcava najve´cu zajedniˇcku mjeru od n i p), tj. n i p su relativno prosti. Prema rezultatu iz teorije brojeva (koji je dokazan na Elementarnoj matematici 1 ) postoje a, b ∈ Z takvi da je an + bp = 1. Odavde slijedi [n] ·p [a] = [1] , × pa zakljuˇcujemo da je [n] invertibilan u (Z× p , ·p ). Dakle, (Zp , ·p ) je grupa.

Na isti naˇcin moˇzemo pokazati da je [n] invertibilan element u monoidu (Zm , ·m ) ako i samo ako vrijedi (m, n) = 1. Oznaˇcimo sa Z× m (ponekad se koristi i oznaka Um ) skup svih invertibilnih elemenata u monoidu (Zm , ·m ). Tada je (Z× m , ·m ) grupa.

Zadaci za vjeˇ zbu 1. Dokaˇzite da je (R, ∗) Abelova grupa, gdje je operacija ∗ definirana na sljede´ci naˇcin: 9 x∗y =x+y+ . 7 2. Na Q je zadana binarna operacija na sljede´ci naˇcin: x ◦ y = x − y + xy. Kakva je (Q, ◦) struktura? 3. Dokaˇzite da je G = Q∗ × Q × Q uz operaciju definiranu na naˇcin (a1 , a2 , a3 ) ◦ (b1 , b2 , b3 ) = (a1 b1 , a2 b1 + b2 , a3 b1 + b3 ) Abelova grupa. 4. Neka je (G, ◦) grupa, a g ∈ G fiksiran. Na G definiramo novu operaciju ∗ na sljede´ci naˇcin: x ∗ y = x ◦ g ◦ y. Dokaˇzite da je i uz tu novu operaciju G grupa. 5. Neka je G konaˇcna polugrupa u kojoj vrijedi kra´cenje (tj. za sve a, b, c iz G je ekvivalentno: a = b i ac = bc i ca = cb). Dokaˇzite da je onda G grupa! Zatim, dokaˇzite da je uvjet konaˇcnosti bitan! (Uputa: promotrite (N0 , +)) 6. Neka je G polugrupa u kojoj vrijede zakoni kra´cenja. Ako za svaki a ∈ G postoji na > 1 takav da je ana = a, dokaˇzite da je G grupa. 7. Neka je G grupa sa svojstvom da za svake a, b, c, d, e, f iz G iz abc = dbf slijedi ac = df . Dokaˇzite da je grupa G Abelova. 10

1.4. Podgrupe

Algebarske strukture

8. Neka je G grupa i fiksirajmo a, b ∈ G. Nadite jedno rjeˇsenje jednadˇzbe xax = b2 a−1 . 9. Dokaˇzite da jednadˇzba x2 ax = a−1 ima rjeˇsenje po x u G ako i samo ako postoji b ∈ G takav da je b3 = a. 10. Neka je S konaˇcan skup s n elemenata; znamo da je tada (P(S), 4) grupa u kojoj je e = ∅ i A−1 = A. Ispitajte jesu li sljede´ci podskupovi podgrupe: (a) {A ⊂ S|card A 6 n2 } (b) {A ⊂ S|card A je paran } (c) {A ⊂ S|card A je neparan } (d) {A ⊂ S|card A > n2 }

1.4

Podgrupe

Definicija 1.4.1. Neka je (G, ·) grupa i H podskup od G. Kaˇzemo da je H podgrupa od G (oznaka: H 6 G) ako je (H, ·) takoder grupa. Propozicija 1.4.2. Neka je (G, ·) grupa i H podskup od G. Ekvivalentno je: (i) H 6 G; (ii) (∀a, b ∈ H)(ab ∈ H) i (∀a ∈ H)(a−1 ∈ H); (iii) (∀a, b ∈ H)(ab−1 ∈ H). Napomena 1.4.3. Dokaz prethodne propozicije zapravo govori da se asocijativnost nasljeduje te ju ne moramo provjeravati, a neutralni element od G ´ce biti u H ˇcim je zadovoljen uvjet (ii) (ili ekvivalentno uvjet (iii)). Primjetite da je uvjet (ii) efektivni kriterij za provjeravanje je li neki podskup podgrupa i koristit ´cemo ga u daljnjim primjerima. Primjer 1.4.4. Svaka grupa ima barem 2 podgrupe: {e} i G. Podgrupe razliˇcite od ove dvije nazivamo pravim podgrupama. Primjer 1.4.5. Imamo sljede´ci niz podgrupa (Z, +) 6 (Q, +) 6 (R, +) 6 (C, +). Definicija 1.4.6. Neka su S, T ⊆ G. Uvedimo sljede´ce oznake • S −1 := {a−1 | a ∈ S}, • ST := {ab | a ∈ S, b ∈ T }. Napomena 1.4.7. Neka je (G, ·) grupa i H podskup od G. Uz oznake prethodne definicije i prema kriteriju za podgrupe vrijedi: H 6 G ako i samo ako HH −1 ⊆ H. 11

Algebarske strukture

1.4. Podgrupe

D.Z. Dokaˇzite da je relacija ”biti podgrupa” relacija parcijalnog uredaja na skupu svih podgrupa od G. T D.Z. Neka je G grupa i {Hi }i∈I proizvoljna familija podgrupa od G. Dokaˇzite da je i∈I Hi takoder podgrupa od G. Primjer 1.4.8. Pokaˇzimo da se niti jedna grupa G ne moˇze napisati kao unija svoje dvije prave podgrupe. Pretpostavimo suprotno da postoje H1 , H2 6 G takvi da G = H1 ∪ H2 ,

i Hi 6= {e}, G, i = 1, 2.

Tada postoji a ∈ H1 \ H2 i postoji b ∈ H2 \ H1 (jer H1 6= G, H2 6= G i H1 ∪ H2 = G). Budu´ci da je a · b ∈ G = H1 ∪ H2 razlikujemo dva sluˇcaja: 1. Neka je a · b ∈ H1 . Budu´ci da je H1 zatvorena na invertiranje a−1 ∈ H1 , a budu´ci da je zatvorena na mnoˇzenje |{z} a−1 · (a · b) = e · b = b ∈ H1 , ˇsto je kontradikcija s b ∈ H2 \ H1 . | {z } ∈H1

∈H1

2. Sluˇcaj a · b ∈ H2 analogno vodi na kontradikciju s a ∈ H1 \ H2 . Budu´ci da svi sluˇcajevi vode na kontradikciju, poˇcetna pretpostavka je bila pogreˇsna i vrijedi tvrdnja koju smo htjeli dokazati. √ Zadatak 1.4.9. Neka je G = {a + b 2 | a, b ∈ Q , a2 + b2 > 0}. Dokaˇzite (G, ·) 6 (R× , ·). √ Rjeˇ senje. Prvo uoˇcimo da za x = a + b 2 uvjet a2 + b2 = 0 vrijedi ako i samo ako√a = 0 i b = 0, tj. ako i samo ako je x = 0 (primjetite da x = 0 povlaˇci a = 0 i b = 0 jer 2 nije racionalan broj). Koristimo kriterij√za podgrupe. Neka su x, y ∈ G. Tada postoje a, b, c, d ∈ Q √ takvi da je x = a + b 2, y = c + d 2 i x 6= 0, y 6= 0. • Zatvorenost na mnoˇzenje. Primjetimo da je √ √ √ xy = (a + b 2)(c + d 2) = (ac + 2bd) + (ad + bc) 2. Budu´ci da su a, b, c, d ∈ Q, a Q je zatvoren na mnoˇzenje i zbrajanje slijedi da je ac + 2bd, ad + bc ∈ Q. Joˇs bismo trebali provjeriti da je (ac + 2bd)2 + (ad + bc)2 > 0, ˇsto je ekvivalentno ˇcinjenici da je xy 6= 0. No primjetimo da to moˇzemo zakljuˇciti koriste´ci svojstva realnih brojeva - budu´ci da je x 6= 0 i y 6= 0, slijedi da je xy 6= 0. • Zatvorenost na invertiranje. Primjetimo da je x

−1

√

−1

= (a + b 2)

√ 1 a−b 2 a −b √ √ = 2 = = + 2. a − 2b2 a2 − b2 a2 − 2b2 a+b 2

Koriste´ci zatvorenost racionalnih brojeva na mnoˇzenje i zbrajanje zakljuˇcujemo da su a −b i 2 racionalni brojevi. Budu´ci da ne postoji x ∈ R takav da je x−1 = 0, 2 2 a −b a − 2b2 zakljuˇcujemo da je x−1 ∈ G. ♦ 12

1.4. Podgrupe

Algebarske strukture

Zadatak 1.4.10. Neka je (G, ·) grupa, a H, K 6 G. Dokaˇzite da je HK 6 G ako i samo ako HK = KH. Napomena 1.4.11. Jednakost skupova HK = KH ne znaˇci da za svaki h ∈ H i svaki k ∈ K vrijedi hk = kh. Ona znaˇci samo da postoje h0 ∈ H i k 0 ∈ K takvi da je hk = k 0 h0 . Rjeˇ senje. Pretpostavimo prvo da je HK podgrupa. Neka je x ∈ HK. Budu´ci da je HK zatvoreno na invertiranje vrijedi x−1 ∈ HK, tj. postoje h1 ∈ H i k1 ∈ K takvi da je x−1 = h1 k1 . Zato je x = (x−1 )−1 = (h1 k1 )−1 = k1−1 h−1 1 ∈ KH. Dakle, HK ⊆ KH. Neka je x ∈ KH. Tada postoje k2 ∈ K, h2 ∈ H takvi da je x = k2 h2 , pa je x−1 = (k2 h2 )−1 = −1 h−1 ∈ HK. Budu´ci da je HK zatvoreno na invertiranje slijedi da je x ∈ HK. Dakle, 2 k2 HK ⊇ KH. Time smo pokazali da je HK 6 G povlaˇci HK = KH. Pretpostavimo da je HK = KH i neka su x, y ∈ HK. Tada postoje k1 , k2 ∈ K, h1 , h2 ∈ H takvi da je x = h1 k1 i y = h2 k2 te imamo xy = (h1 k1 )(h2 k2 ) = h1 (k1 h2 )k2 . Zbog pretpostavke HK = KH postoje k3 ∈ K, h3 ∈ H takvi da je k1 h2 = h3 k3 . Zato je xy = h1 (k1 h2 )k2 = (h1 h3 )(k3 k2 ) ∈ HK. Nadalje x−1 = k1−1 h−1 ci ⇒ HK 6 G. 1 ∈ KH = HK. Dakle, pokazali smo i da HK = KH povlaˇ ♦ D.Z. Neka je (G, ·) grupa od 8 elemenata sa svojstvom da za svaki x ∈ G vrijedi x2 = e. Dokaˇzite da G ima podgrupu od 4 elementa. Konaˇcno dolazimo do jednog od prvih netrivijalnih rezultata - teorema o klasifikaciji svih podgrupa grupe cijelih brojeva. Teorem 1.4.12. Grupe (nZ, +) za n ∈ N0 su jedine podgrupe od (Z, +). Dokaz. Prvo dokaˇzimo (koriste´ci kriterij za podgrupe) da za n ∈ N0 vrijedi (nZ, +) 6 (Z, +). Neka su a, b ∈ nZ. Tada postoje x, y ∈ Z takvi da a = nx, b = ny. Budu´ci da je a + b = nx + ny = n(x + y) slijedi da je a + b ∈ nZ, a budu´ci da je −a = n · (−x) slijedi da je −a ∈ nZ. ˇ Nadalje, neka je H 6 Z proizvoljna podgrupa. Zelimo pokazati da postoji n ∈ N0 takav da je H = nZ. Ako je H = {0} trivijalna grupa onda moˇzemo uzeti n = 0. Pretpostavimo da je H 6= {0}. Tada je H ∩ N 6= ∅. (Zaista, u H postoji neki element x 6= 0 te je −x takoder u H. Toˇcno jedan od brojeva x i −x mora biti pozitivan, tj. element od H ∩ N.) Zbog toga ima smisla definirati n0 := min N ∩ H. Tvrdimo da je H = n0 Z. Pokaˇzimo obje inkluzije. Prvo pokazujemo H ⊇ n0 Z. Indukcijom po m dokazujemo da je n0 m ∈ H za svaki m ∈ N. Baza, m = 1, vrijedi zbog definicije broja n0 . Pretpostavimo li da je n0 m ∈ H za neki m, zbog zatvorenosti od H na zbrajanje vrijedi n0 (m + 1) = n0 m + n0 ∈ H. Za m = 0 vrijedi n0 · 0 = 0 ∈ H jer svaka podgrupa sadrˇzi neutralni element. Za m ∈ N vrijedi n0 (−m) = −(n0 m) ∈ H jer je H zatvoreno na invertiranje. Time smo pokazali da je n0 m ∈ H za svaki m ∈ Z. 13

Algebarske strukture

1.4. Podgrupe

Ostaje pokazati da je H ⊆ n0 Z. Neka je x ∈ H. Prema teoremu o dijeljenju s ostatkom postoje q ∈ Z i r ∈ Z takvi da je x = n0 q + r, 0 6 r 6 n0 − 1 Tada je r = x − n0 q ∈ H jer je H podgrupa i ve´c smo pokazali da je n0 q ∈ H. Ako bi bilo r > 0, onda bi vrijedilo r ∈ N ∩ H i r < n0 ˇsto je kontradikcija s ˇcinjenicom da je n0 minimalni takav broj. Dakle, r = 0 ˇsto znaˇci da x = n0 q ∈ n0 Z. 

Zadaci za vjeˇ zbu 1. Neka je (G, ·) grupa, a H njen konaˇcni podskup sa svojstvom da ako su x, y iz H, onda je i x · y opet iz H. Dokaˇzite da je H podgrupa od G. 2. Neka je G grupa i H 6 G. Uvedimo CG (H) = {g ∈ G|gh = hg, ∀h ∈ H}. Ovaj skup se naziva centralizator od H u G. Je li CG (H) grupa? 3. Neka je G grupa i H 6 G. Uvedimo NG (H) = {g ∈ G|gH = Hg}. Ovaj skup se naziva normalizator od H u G. Dokaˇzite da je NG (H) podgrupa od G. 4. Neka je (G, ·) grupa i Hi , i ∈ N niz njezinih podgrupa takvih da je Hi ⊂ Hi+1 . Dokaˇzite da je tada i ∪∞ i=1 Hi 6 G. 5. Dokaˇzite da je Kn 6 Km ako i samo ako n dijeli m. 6. Dokaˇzite da je skup matrica   x x { : x ∈ R× } 0 0 grupa u odnosu na matriˇcno mnoˇzenje. 7. Ako je skup S, koji je podskup skupa matrica Mn (R), grupa u odnosu na matriˇcno mnoˇzenje, tada su ili sve matrice tog skupa regularne ili su sve matrice tog skupa singularne. Dokaˇzite! 14

1.5. Homomorfizmi grupa

1.5

Algebarske strukture

Homomorfizmi grupa

Definicija 1.5.1. Neka su (G, ·), (H, ∗) grupe. Preslikavanje f : G → H je homomorfizam grupa ako za sve a, b ∈ G vrijedi f (a · b) = f (a) ∗ f (b). Monomorfizam je injektivan homomorfizam, epimorfizam je surjektivni homomorfizam, a izomorfizam je bijektivni homomorfizam. Endomorfizam je homomorfizam kojem su domena i kodomena iste grupe. Automorfizam je bijektivni endomorfizam. Propozicija 1.5.2. Neka su G, H grupe, eG i eH jedinice u G i H te f : G → H homomorfizam grupa. Tada vrijedi f (eG ) = eH . Dokaz. Neka je a ∈ G. Vrijedi eH · f (a) = f (a) = f (eG · a) s f (a) dobivamo eH = f (eG ).

f homo-

=

f (eG ) · f (a). Mnoˇze´ci zdesna 

Propozicija 1.5.3. Neka su G i H grupe, f : G → H homomorfizam grupa. Tada za svaki x ∈ G vrijedi f (x)−1 = f (x−1 ). Dokaz. Budu´ci da vrijedi f (x) · f (x)−1 = eH = f (eG ) = f (x · x−1 ) = f (x) · f (x−1 ) Mnoˇzenjem s f (x)−1 slijeva dobivamo f (x)−1 = f (x−1 ).  Napomena 1.5.4. Budite oprezni s oznakama.

f −1 (a) | {z }

inverz funkcije

6=

f (a)−1 | {z }

.

inverz elementa f (a)

Definicija 1.5.5. Neka su G, H grupe i f : G → H homomorfizam. Skup Kerf := {x ∈ G | f (x) = eH } zovemo jezgra od f . Skup Im f := {f (x) | x ∈ G} zovemo slika od f . Propozicija 1.5.6. Neka su G i H grupe, f : G → H homomorfizam grupa, L 6 G, K 6 H. Tada vrijedi: (i) f (L) = {f (l) | l ∈ L} 6 H, (ii) f −1 (K) = {g ∈ G | f (g) ∈ K} 6 G. Posebno, Ker f = f −1 ({eH }) 6 G i Im f = f (G) 6 H. Dokaz. (i) Neka su x, y ∈ f (L). Tada postoje l1 , l2 ∈ L takvi da vrijedi f (l1 ) = x, f (l2 ) = y. Slijedi da je f homoxy = f (l1 ) · f (l2 ) = f (l1 · l2 ) ∈ f (L). Nadalje, x−1 = f (l1 )−1

P rop.

=

f ( l1−1 ) ∈ f (L), ˇsto pokazuje da je f (L) zatvoreno na |{z} ∈L

mnoˇzenje i invertiranje, pa prema kriteriju za podgrupe zakljuˇcujemo da je f (L) 6 H. 15

Algebarske strukture

1.5. Homomorfizmi grupa

(ii) Neka su x, y ∈ f −1 (K), tj. f (x), f (y) ∈ K. Tada je homo-

f (xy) = f (x) f (y) ∈ K ⇒ xy ∈ f −1 (K). |{z} |{z} ∈K

∈K

Ako je x ∈ f −1 (K), onda je f (x−1 ) = f (x)−1 ⇒ f (x)−1 ∈ K ⇒ f (x−1 ) ∈ K ⇒ x−1 ∈ f −1 (K). |{z} ∈K

Vidimo da je kriterij za podgrupu zadovoljen, pa zakljuˇcujemo f −1 (K) 6 G.  D.Z. Neka su G, H grupe i f : G → H homomorfizam. Dokaˇzite da je f monomorfizam ako i samo ako je Kerf trivijalna grupa. Definicija 1.5.7. Kaˇzemo da su grupe G i H izomorfne ako postoji izomorfizam f : G → H. Tada piˇsemo G ∼ = H. D.Z. Dokaˇzite da je relacija “biti izomorfan” relacija ekvivalencije (na familiji svih grupa).1 D.Z. Neka je G grupa, a Aut G skup svih automorfizama od G. Dokaˇzite da je (Aut G, ◦) grupa. Zadatak 1.5.8. Dokaˇzite da grupe (R× , ·) i (C× , ·) nisu izomorfne. Rjeˇ senje. Pretpostavimo suprotno, tj. da postoji izomorfizam f : C× → R× . Budu´ci da svaki homomorfizam ˇcuva jedinicu vrijedi f (1) = 1. Neka je a := f (i). Uoˇcimo a 6= 1 jer je f bijekcija. Slijedi f (−1) = f (i · i) = f (i)f (i) = a2 , 1 = f (1) = f (−1)f (−1) = a2 a2 = a4 ⇒ a4 = 1

a∈R× , a6=1

⇒

a = −1.

No tada je f (−1) = a2 = 1 = f (1), ˇsto je u kontradikciji s pretpostavkom da je f bijekcija. Dakle, poˇcetna je pretpostavka bila pogreˇsna, tj. takav izomorfizam ne postoji. ♦ Zadatak 1.5.9. Dokaˇzite da su grupe (Z4 , +4 ) i (Z5 \{0}, ·5 ) izomorfne. Rjeˇ senje. Definirajmo f : Z4 → Z5 \{0} na sljede´ci naˇcin s namjerom da f bude homomorfizam. Tada moramo staviti f (0) = 1 (neutralni element se preslikava u neutralni element). Stavimo f (1) = 2. Slijedi f (2) = f (1 +4 1) = f (1) ·5 f (1) = 2 ·5 2 = 4 f (3) = f (2 +4 1) = f (2) ·5 f (1) = 4 ·5 2 = 3 1

U teoriji skupova ne postoji skup svih skupova, pa tako ne postoji niti skup svih grupa. Familija svih grupa je ”prevelika” da bismo ju nazivali skupom.

16

1.5. Homomorfizmi grupa

Algebarske strukture

Na ovaj naˇcin smo definirali bijekciju f . Ostaje provjeriti da je f homomorfizam (D.Z.).

♦

D.Z. Neka je H = ({−1, 1}, ·). a) Dokaˇzite da je H 6 (R× , ·). b) Odredite sve homomorfizme f : R× → H. D.Z. Neka je (G, ∗) konaˇcna grupa i f : G → (C× , ·) homomorfizam grupa sa svojstvom da (∃x0 ∈ G) f (x0 ) 6= 1. a) Dokaˇzite da je g : G → G definiran sa g(x) = x0 ∗ x bijekcija (ne nuˇzno izomorfizam! ). X X b) Koriˇstenjem (a) odredite f (x) i f (x). x∈G

x∈G\{eG }

Zadatak 1.5.10. Dokaˇzite da postoje barem dvije razliˇcite (neizomorfne) grupe reda 4. Rjeˇ senje. Pogledajmo (Z4 , +4 ) i (Z2 × Z2 , +2 ), pri ˇcemu je Z2 × Z2 = {(x, y) | x, y ∈ Z2 } i (x1 , y1 ) +2 (x2 , y2 ) = (x1 +2 x2 , y1 +2 y2 ). Tvrdimo da ove dvije grupe nisu izomorfne. Pretpostavimo suprotno, tj. da postoji izomorfizam f : Z4 → Z2 × Z2 . Odmah uoˇcimo da onda mora biti f (0) = (0, 0). Oznaˇcimo f (1) = (x1 , y1 ), pa dobijemo f (2) = f (1 +4 1) = f (1) +2 f (1) = (x1 , y1 ) +2 (x1 , y1 ) = (x1 +2 x1 , y1 +2 y1 ) = (0, 0) = f (0), ˇsto je kontradikcija sa pretpostavkom da je f bijekcija.

♦

Napomena 1.5.11. Do na izomorfizam, postoje toˇcno dvije grupe reda 4 (i one su reprezentirane grupama iz prethodnog zadatka). U prethodnom zadatku smo vidjeli grupu Z2 × Z2 koja je poseban sluˇcaj sljede´ce konstrukcije. Definicija 1.5.12. Neka su (G, ·G ) i (H, ·H ) grupe. Definirajmo binarnu operaciju na G × H na sljede´ci naˇcin (g1 , h1 ) · (g2 , h2 ) = (g1 ·G g2 , h1 ·H h2 ). D.Z. Provjerite da je (G × H, ·) grupa. Ovu grupu nazivamo direktan produkt grupa G i H i oznaˇcavamo joˇs s G ⊕ H. Za direktan produkt imamo prirodne projekcije πG : G ⊕ H → G i πH : G ⊕ H → H koje su homomorfizmi grupa. Napomena 1.5.13. Dosad smo vidjeli da su grupe objekti s odredenom matematiˇckom strukturom i u teoriji grupa prouˇcavamo njihove podobjekte, morfizme koji poˇstuju tu strukturu i razne konstrukcije (poput jezgre, kvocijenta, produkta). Kompozicija homomorfizama je ponovno homorfizam, pa kaˇzemo da grupe i homomorfizmi grupa ˇcine kategoriju. Sigurno uoˇcavate da ste na sliˇcan

17

Algebarske strukture

1.5. Homomorfizmi grupa

naˇcin na drugim kolegijima prouˇcavali kategoriju vektorskih prostora i linearnih operatora, kategoriju topoloˇskih prostora i neprekidnih preslikavanja, kategoriju grafova i morfizama grafova, kategoriju skupova i funkcija i joˇs mnoge druge. Kategorija se sastoji od klase objekata i klase morfizama koje moˇzemo komponirati na asocijativan naˇcin pri ˇcemu identitete djeluju kao neutralni elementi. U svakoj kategoriji postoji pojam izomorfizma (morfizma koji ima inverz), a klasificiraju´ci problemi unutar teorije se bave prouˇcavanjem struktura do na izomorfizam. Na primjer, skupove moˇzemo klasificirati prema broju elemenata, vektorske prostore prema dimenziji, grafove prema relaciji incidencije, a grupe prema njihovim Cayleyevim tablicama. Razvoj teorije kategorija bio je motiviran potrebama u algebarskoj topologiji za sistematizacijom naˇcina na koji probleme iz topologije moˇzemo svesti na probleme iz algebre. Zato se teorija kategorija bavi prouˇcavanjem raznih konstrukcija unutar kategorije na univerzalan naˇcin te odnosima izmeˇzu razliˇcitih kategorija. D.Z. Dokaˇzite da direktan produkt grupa G i H ima sljede´ce svojstvo: ako je K grupa, a g : K → G i h : K → H homomorfizmi grupa, onda postoji jedinstveno preslikavanje f : K → G ⊕ H takvo da vrijedi πG ◦ f = g i πH ◦ f = h, tj. tako da sljede´ci dijagram komutira 5; G

g f

K

πG

/G⊕H πH h

)#

H

Napomena 1.5.14. Prethodni zadatak pokazuje da direktan produkt (G⊕H, πG , πH ) ima univerzalno svojstvo produkta. Na sliˇcan naˇcin moˇzemo definirati produkt objekata u bilo kojoj kategoriji te se moˇze dokazati da su bilo koja dva prdukta izomorfna.

Zadaci za vjeˇ zbu 1. Neka je  A=

  a b 2 2 |a, b ∈ R, a + b 6= 0 . −b a

Dokaˇzite da je skup A, uz uobiˇcajeno mnoˇzenje matrica kao binarnu operaciju, podgrupa   a b × od GL(2, R). Ispitajte je li skup A izomorfan s (C , ·). (Uputa: a + ib 7→ ). −b a 2. Dokaˇzite da je (R, +) ∼ = (R× , ·). (Uputa: x 7→ ex ). 3. Promotrimo grupu GL(2, Z2 ) uz uobiˇcajeno mnoˇzenje matrica. Dakle, elementi su joj 2 × 2 matrice s matriˇcnim elementima 0 i 1 ali s kojima operiramo po pravilima iz Z2 : 0 + 0 = 1 + 1 = 0. Je li je ta grupa izomorfna s S3 ? 18

1.6. Cikliˇcke i konaˇcnogenerirane grupe

Algebarske strukture

Uputa: pokaˇzite prvo da GL(2, Z2 ) ima ˇsest elemenata. Ako je mogu´ce, pokuˇsajte na´ci u toj grupi element reda 2 i element reda 3 koji ju generiraju. Moˇzete li takvo ˇsto napraviti u S3 ? 4. Neka je G = {2n 3m : n, m ∈ Z} i H = {2n : n ∈ Z}. Dokaˇzite (i) (G, ·) je grupa, (ii) H 6 G, (iii) Postoji homomorfizam f : G → (Z, +) takav da je Kerf = H. 5. Neka je G grupa, f : G → G preslikavanje definirano s f (a) = a−1 . Dokaˇzite da je f izomorfizam ako i samo ako je G Abelova. 6. Neka su G i H grupe. Definiramo Hom(G, H) = {f : G → H|f je homomorfizam}. Neka su φ, ψ ∈ Hom(G, H). Oznaˇcimo E(φ, ψ) = {g ∈ G|φ(g) = ψ(g)}. Dokaˇzite (i) E(φ, ψ) 6 G, (ii) Za svaki φ iz Hom(G, H) postoji ψ iz Hom(G, H) takav da je E(φ, ψ) = Kerφ. Ovu univerzalnu konstrukciju nazivamo ujednaˇcitelj morfizama φ i ψ.

1.6

Cikliˇ cke i konaˇ cnogenerirane grupe

Definicija 1.6.1. Neka je G grupa i S ⊆ G proizvoljan podskup. Tada je (prema zadatku iz poglavlja o podgrupama) \ hSi := H H6G S⊆H

podgrupa od G za koju kaˇzemo da je generirana podskupom S i elemente skupa S zovemo generatorima. Ako je S konaˇcan skup i G = hSi kaˇzemo da je G konaˇ cnogenerirana grupa. Za grupu G kaˇzemo da je cikliˇ cka ukoliko je generirana jednim elementom, tj. ako postoji a ∈ G takav da je G = h{a}i. Za h{a}i koristimo joˇs i oznaku hai. Propozicija 1.6.2. Neka je G grupa i S ⊆ G. Tada je hSi = {xni11 · xni22 · . . . · xnikk : k ∈ N, xi1 , xi2 , . . . , xik ∈ S, n1 , n2 , . . . , nk ∈ Z}. Dokazat ´cemo sljede´cu jednostavniju verziju ove propozicije jer ´cemo u dokazu vidjeti glavne ideje. Sami dokaˇzite gornju propoziciju. Propozicija 1.6.3. Neka je G grupa i a ∈ G. Tada je hai = {an : n ∈ Z}. 19

Algebarske strukture

1.6. Cikliˇcke i konaˇcnogenerirane grupe

Dokaz. Uvedimo oznaku A := {an : n ∈ Z}. Prema definiciji, hai je presjek svih podgrupa od G koje sadrˇze element a. Budu´ci da je A takoder podgrupa (provjerite) i sadrˇzi a, slijedi da je hai ⊆ A. S druge strane, indukcijom pokazujemo da je an ∈ hai za sve n ∈ N, pa budu´ci da je hai zatvorena na invertiranje slijedi da a−n ∈ hai za sve n ∈ N, tj. A ⊆ hai.  Oznaˇcimo Z(a) := {n ∈ Z | an = eG }. Tada je Z(a) 6 (Z, +) (uoˇcite da je f : Z → G, f (n) = an homomorfizam grupa i Z(a) = Kerf ). Prema teoremu o klasifikaciji svih podgrupa grupe (Z, +) slijedi da postoji n0 ∈ N0 takav da je Z(a) = n0 Z. Definicija 1.6.4. Neka je G grupa i a ∈ G. Red |a| elementa a definiramo na sljede´ci naˇcin  n0 , ako je Z(a) = n0 Z |a| = +∞, ako je Z(a) = {0}. Napomena 1.6.5. Moˇzemo pobliˇze opisati grupu hai. • Ako je |a| = ∞, onda je an 6= am za sve n, m ∈ Z, n 6= m. Tada vrijedi hai = {. . . , a−2 , a−1 , e, a1 , a2 , . . .} ∼ = (Z, +) • Ako je |a| = n0 ∈ N, onda je ak = an0 +k za sve k ∈ Z i vrijedi hai = {e, a, a2 , a3 , . . . , an0 −1 } ∼ = (Zn0 , +n0 ) Dakle, vrijedi |a| = | hai |. Ako je red elementa a konaˇcan, onda je to najmanji prirodan broj n takav da je an = e, tj. |a| = min{n : an = e}. Primjer 1.6.6. Promotrimo grupu simetrija kvadrata. Tada je element koji predstavlja rotaciju za 90◦ reda 4, a element koji predstavlja zrcaljenje obzirom na dijagonalu reda 2. Zadatak 1.6.7. Pokaˇzite da (Q, +) nije cikliˇcka grupa.   p = Q, za p ∈ Z, q ∈ N, p i q relativno prosti. Rjeˇ senje. Pretpostavimo suprotno, tj. da je q 1 1 p Promotrimo ∈ Q. Prema pretpostavci = n · , za neki n ∈ Z, tj. 1 = 2np. Ovo je 2q 2q q nemogu´ce, ˇsto znaˇci da je poˇcetna pretpostvka bila pogreˇsna. Dakle, vrijedi tvrdnja zadatka. D.Z. Dokaˇzite da (Q, +) nije konaˇcnogenerirana grupa. D.Z. Dokaˇzite da (Z ⊕ Z, +) nije cikliˇcka grupa. Zadatak 1.6.8. Dokaˇzite da je podgrupa cikliˇcke grupe takoder cikliˇcka. 20

1.6. Cikliˇcke i konaˇcnogenerirane grupe

Algebarske strukture

Rjeˇ senje. Neka je G cikliˇcka grupa i a ∈ G takav da je G = hai. Neka je H proizvoljna podgrupa od G. Ako je H = {e}, onda je H cikliˇcka. Zato pretpostavimo da H nije trivijalna grupa. Tada je skup M = {m ∈ N | am ∈ H} neprazan, pa postoji minimum tog skupa m0 = min M . Tvrdimo da je ham0 i = H. Budu´ci da je H zatvoreno na mnoˇzenje i am0 ∈ H, indukcijom slijedi da je anm0 ∈ H za sve n ∈ N. Budu´ci da je H zatvoreno na invertiranje slijedi da je anm0 ∈ H za sve n ∈ Z. Dakle, ham0 i ⊆ H. Neka je x ∈ H proizvoljan. Budu´ci da je x ∈ G = hai postoji n ∈ Z takav da je x = an . Prema teoremu o dijeljenju s ostatkom postoje q, r ∈ Z, 0 6 r 6 m0 −1 takvi da je n = q·m0 +r. Tada je ar = an−qm0 = an · a−qm0 . Budu´ci da je an ∈ H te smo ve´c u prvom dijelu dokaza pokazali da je a−qm0 za sve q ∈ Z, slijedi da je ar ∈ H. Budu´ci da je r 6 m0 −1, a m0 je najmanji prirodni broj takav da je am0 ∈ H, mora vrijediti r = 0. Dakle, n = m0 q i x = am0 q ∈ ham0 i. Lema 1.6.9. Neka je G grupa i a ∈ G element konaˇcnog reda. Za k ∈ Z vrijedi ak = eG ako i samo ako |a| dijeli k. Dokaz. Za k ∈ Z vrijedi ak = e ako i samo ako je k ∈ Z(a), ˇsto vrijedi ako i samo ako n0 dijeli k gdje je n0 = |a|.  Zadatak 1.6.10. Neka su G i H konaˇcne cikliˇcke grupe takve da su |G| i |H| relativno prosti. Dokaˇzite da je grupa G ⊕ H cikliˇcka. Rjeˇ senje. Neka je |G| = m i |H| = n, te neka su a ∈ G, b ∈ H takvi da je G = hai = {e, a, a2 , . . . , am−1 } i H = hbi = {e, b, b2 , . . . , bn−1 }. Tvrdimo da (a, b) generator grupe G ⊕ H. Budu´ci da je |G ⊕ H| = mn dovoljno je pokazati da je |(a, b)| = mn. Budu´ci da je (a, b)mn = (amn , bmn ) = (enG , em H ) = (eG , eH ) prema Lemi slijedi da |(a, b)| dijeli mn. S druge strane (a, b)|(a,b)| = (eG , eH ), ˇsto povlaˇci a|(a,b)| = eG i b|(a,b)| = eH . Prema Lemi slijedi da m = |a| i n = |b| dijele |(a, b)|. Budu´ci da je (m, n) = 1, zakljuˇcujemo da mn dijeli |(a, b) odakle slijedi tvrdnja. ♦ Primjer 1.6.11. Prethodni zadatak pokazuje da je grupa Z2 ⊕ Z3 izomorfna s grupom Z6 . Op´cenito, Zn ⊕ Zm je izomorfno sa Znm ako i samo ako je M (n, m) = 1. D.Z. Dokaˇzite smjer koji nismo pokazali u prethodnom primjeru. Zadatak 1.6.12. Odredite sve generatore konaˇcne cikliˇcke grupe G reda n. Rjeˇ senje. Neka je a generator grupe G. Promotrimo na primjeru n = 12 koliki je red elementa k a , tj. koji je najmanji eksponent na koji moramo potencirati ak kako bismo dobili potenciju od a1 2 = e. Imamo sljede´ci niz vrijedosti |a0 | = 1, |a1 | = 12, |a2 | = 6, |a3 | = 4, |a4 | = 3, |a5 | = 12, |a6 | = 2, |a7 | = 12, |a8 | = 3, |a9 | = 4, |a10 | = 6, |a11 | = 12. 21

Algebarske strukture

1.7. Strukturni teorem za konaˇcno generirane Abelove grupe

Vidimo da su generatori oblika ak za k ∈ {1, 5, 7, 11}, tj. za one k koji su relativno prosti s 12. Na temelju ovoga moˇzemo naslutiti da je |ak | =

n . M (n, k)

Dokaˇzimo ovu tvrdnju. Neka je k ∈ {1, ..., n} fiksiran te oznaˇcimo d = M (n, k), n = dn1 , k = ˇ dk1 . Tada je M (n1 , k1 ) = 1 i kn1 = k1 n. Zelimo pokazati da je |ak | = n1 . k

Zbog (ak )n1 = (an )k1 = e, Lema povlaˇci da |ak | dijeli n1 . Budu´ci da je (ak )|a | = e, Lema ˇ povlaˇci da n = |a| dijeli k · |ak |, tj. n1 dijeli k1 |ak |. Cinjenica da je M (n1 , k1 ) = 1 povlaˇci da n1 k dijeli |a |. Dakle, svi generatori su oblika ak pri ˇcemu je M (n, k) = 1. Takvih elemenata ima ϕ(n). D.Z. Odredite sve podgrupe cikliˇcke grupe reda n. Propozicija 1.6.13. Neka je G grupa, a ∈ G element reda n, te f : G → H monomorfizam grupa. Tada je |f (a)| = n. Dokaz. Budu´ci da je f (a)n = f (an ) = f (eG ) = eH , Lema povlaˇci da |f (a)| dijeli n. S druge strane f (eG ) = eH = f (a)|f (a)| = f (a|f (a)| ). Budu´ci da je f injekcija mora vrijediti a|f (a)| = eG , pa Lema povlaˇci da n dijeli |f (a)|.  Korolar 1.6.14. Ako je f : G → H izomorfizam konaˇcnih cikliˇckih grupa, onda f preslikava generator u generator.

1.7

Strukturni teorem za konaˇ cno generirane Abelove grupe

U daljnim razmatranjima vrlo je vaˇzno voditi raˇcuna o rezultatu koji smo naveli u prethodnom poglavlju: Zn ⊕ Zm ∼ (1.1) = Znm ⇔ M (m, n) = 1. Teorem 1.7.1. Neka je G konaˇcno generirana Abelova grupa. Tada: (1) ∃!s, t ∈ N0 , ∃m1 , m2 , . . . , mt ∈ N takvi da m1 | m2 | . . . | mt i vrijedi ⊕ Zm2 ⊕ . . . ⊕ Zmt G∼ = |Z ⊕ Z ⊕ {z. . . ⊕ Z} ⊕ Z | m1 {z } s puta - “slobodan dio”

torzija

(2) ∃!s, k ∈ N0 , p1 , p2 , . . . , pk prosti (ne nuˇzno razliˇciti) , s1 , s2 , . . . , sk takvi da s1 ⊕ Zp s2 ⊕ . . . ⊕ Zp sk G∼ = Z 2 k {z. . . ⊕ Z} ⊕ Z | ⊕Z⊕ | p1 {z }

s puta - “slobodan dio”

torzija

22

1.7. Strukturni teorem za konaˇcno generirane Abelove grupe

Algebarske strukture

Zadatak 1.7.2. Odredite do na izomorfizam sve Abelove grupe reda: a) 100 b) 1500 c) 16. Rjeˇ senje. a) Prvo rastavimo 100 na proste faktore, 100 = 22 ·52 . Sad, po Teoremu (2), ovisno o tome kako grupiramo faktore 2, 2, 5, 5, dobivamo razliˇcite (tj. medusobno neizomorfne) grupe (uoˇcimo usput da slobodnog dijela ne´ce biti, jer promatramo konaˇcne grupe). Na primjer, 2 · 2 · 52 (dakle p1 = 2, s1 = 1, p2 = 2, s2 = 1, p3 = 5, s3 = 2) daje Z2 ⊕ Z2 ⊕ Z52 = Z2 ⊕ Z2 ⊕ Z25 , a 22 · 52 (dakle p1 = 2, s1 = 2, p2 = 5, s2 = 5) daje Z22 ⊕ Z52 = Z4 ⊕ Z25 . Tako dobivamo sljede´cu tablicu svih Abelovih grupa reda 100 (do na izomorfizam): 22 · 52 2 · 2 · 52 22 · 5 · 5 2·2·5·5

Z4 ⊕ Z25 Z2 ⊕ Z2 ⊕ Z25 Z4 ⊕ Z5 ⊕ Z5 Z2 ⊕ Z2 ⊕ Z5 ⊕ Z5

Dakle svaka Abelova grupa G reda 100 je izomorfna toˇcno jednoj od gornjih grupa u drugom stupcu. Pogledajmo sad ˇsto daje prikaz pomo´cu Teorema (1). Na primjer, za Z2 ⊕Z2 ⊕Z5 ⊕Z5 ˇzelimo prona´ci m1 , m2 . . . , mt za koje vrijedi m1 | m2 | · · · | mt koriste´ci 1.1. Tako iz Z2 ⊕ Z2 ⊕ Z5 ⊕ Z5 uzmemo Z2 ⊕ Z5 ∼ = Z10 (jer je M (2, 5) = 1) i dobijemo m1 = 10, m2 = 10, dakle m1 | m2 , pa je Z2 ⊕ Z2 ⊕ Z5 ⊕ Z5 ∼ = Z10 ⊕ Z10 . Dalje, za Z4 ⊕ Z5 ⊕ Z5 sparimo prva dva sumanda u Z20 pa dobijemo Z4 ⊕ Z5 ⊕ Z5 ∼ = Z5 ⊕ Z20 (m1 = 5, m2 = 20). Za Z2 ⊕Z2 ⊕Z25 iskoristimo Z2 ⊕Z25 ∼ = Z50 pa je Z2 ⊕Z2 ⊕Z25 ∼ = Z2 ⊕Z50 ∼ (m1 = 2, m2 = 50). I na kraju, Z4 ⊕ Z25 = Z100 (m1 = 100). Dodajmo i ove prikaze u gornju tablicu: Zapis (2) 2 2 2 · 5 Z4 ⊕ Z25 2 · 2 · 52 Z2 ⊕ Z2 ⊕ Z25 22 · 5 · 5 Z4 ⊕ Z5 ⊕ Z5 2 · 2 · 5 · 5 Z2 ⊕ Z2 ⊕ Z5 ⊕ Z5

∼ = ∼ = ∼ = ∼ = ∼ =

Zapis (1) Z100 Z2 ⊕ Z50 Z5 ⊕ Z20 Z10 ⊕ Z10

Prikazi (tj. grupe) u pojedinom retku su izomorfni, a grupe u razliˇcitim retcima su medusobno neizmorfne. 23

Algebarske strukture

1.7. Strukturni teorem za konaˇcno generirane Abelove grupe

b) 1500 = 22 · 3 · 53 . Dakle, kao i u a) dijelu, imamo za poˇcetak sljede´cu tablicu:

22 · 3 · 53 2 · 2 · 3 · 53 22 · 3 · 52 · 5 2 · 2 · 3 · 52 · 5 22 · 3 · 5 · 5 · 5 2·2·3·5·5·5

Zapis (2) Z4 ⊕ Z3 ⊕ Z125 Z2 ⊕ Z2 ⊕ Z3 ⊕ Z125 Z4 ⊕ Z3 ⊕ Z5 ⊕ Z25 Z2 ⊕ Z2 ⊕ Z3 ⊕ Z25 ⊕ Z5 Z4 ⊕ Z3 ⊕ Z5 ⊕ Z5 ⊕ Z5 Z2 ⊕ Z2 ⊕ Z3 ⊕ Z5 ⊕ Z5 ⊕ Z5

Na temelju zakljuˇcivanja u a) dijelu, opiˇsimo postupak za prevodenje zapisa (2) u zapis (1): - Uzmimo ˇsto viˇse sumanada u zapisu (2) sa medusobno relativno prostim indeksima i spojimo ih u jedan sumand za zapis (1). - Ponovimo gornji korak, ali zanemaruju´ci sumande u zapisu (2) koje smo prethodno uzeli. Ponavljamo dok ne nestane sumanada u zapisu (2). U prvom koraku odredujemo sumand Zmt iz zapisa (1). Zato za njega uzimamo ˇsto viˇse sumanada s medusobno relativno prostim indeksima, jer bi u suprotnom za neki Zmt−i vrijedilo mt−i - mt . Pokaˇzimo postupak na primjeru Z2 ⊕ Z2 ⊕ Z3 ⊕ Z5 ⊕ Z5 ⊕ Z5 : - Uzmemo Z2 ⊕ Z3 ⊕ Z5 i kako je Z2 ⊕ Z3 ⊕ Z5 ∼ = Z30 dobijemo sumand Z30 u zapisu (1). - Od zapisa (2) dalje promatramo samo Z2 ⊕ Z5 ⊕ Z5 . Opet uzmemo ˇsto viˇse sumanada s medusobno relativno prostim indeksima – to su Z2 i Z5 , pa kako je Z2 ⊕ Z5 ∼ = Z10 dobijemo sumand Z10 u zapisu (1). - Od zapisa (2) nam je ostalo samo Z5 , dakle Z5 je sumand u zapisu (1). Dobili smo Z2 ⊕ Z2 ⊕ Z3 ⊕ Z5 ⊕ Z5 ⊕ Z5 ∼ = Z5 ⊕ Z10 ⊕ Z30 . Tako dobijemo sljede´cu tablicu:

2

3

2 ·3·5 2 · 2 · 3 · 53 22 · 3 · 52 · 5 2 · 2 · 3 · 52 · 5 22 · 3 · 5 · 5 · 5 2·2·3·5·5·5

Zapis (2) Z4 ⊕ Z3 ⊕ Z125 Z2 ⊕ Z2 ⊕ Z3 ⊕ Z125 Z4 ⊕ Z3 ⊕ Z5 ⊕ Z25 Z2 ⊕ Z2 ⊕ Z3 ⊕ Z25 ⊕ Z5 Z4 ⊕ Z3 ⊕ Z5 ⊕ Z5 ⊕ Z5 Z2 ⊕ Z2 ⊕ Z3 ⊕ Z5 ⊕ Z5 ⊕ Z5

∼ = ∼ = ∼ = ∼ = ∼ = ∼ = ∼ =

Zapis (1) Z1500 Z2 ⊕ Z750 Z5 ⊕ Z300 Z10 ⊕ Z150 Z5 ⊕ Z5 ⊕ Z60 Z5 ⊕ Z10 ⊕ Z30

c) 16 = 24 . Uoˇcimo da ´ce zapis (1) biti isti kao zapis (2), jer u zapisu (2) ne´cemo imati ˇsto sparivati:

24

1.7. Strukturni teorem za konaˇcno generirane Abelove grupe Zapis (2) 2 Z16 23 · 2 Z2 ⊕ Z8 22 · 22 Z4 ⊕ Z4 2 2 · 2 · 2 Z4 ⊕ Z2 ⊕ Z2 2 · 2 · 2 · 2 Z2 ⊕ Z2 ⊕ Z2 ⊕ Z2 4

∼ = ∼ = ∼ = ∼ = ∼ = ∼ =

Algebarske strukture

Zapis (1) Z16 Z2 ⊕ Z8 Z4 ⊕ Z4 Z4 ⊕ Z2 ⊕ Z2 Z2 ⊕ Z2 ⊕ Z2 ⊕ Z2

Zadaci za vjeˇ zbu 1. Dokaˇzite da sljede´ci elementi grupe G imaju isti red (a) a i a−1 (b) a i bab−1 (c) ab i ba Uputa: posebno razmotrite sluˇcaj |a| < ∞ i |a| = ∞. 2. Neka su G i H grupe, te f : G → H homomorfizam. Ako je |a| = n, koje sve vrijednosti moˇze poprimiti |f (a)|? 3. Neka je G konaˇcna grupa, |G| = p, gdje je p prost. Dokaˇzite da je g cikliˇcka. 4. Neka je G Abelova grupa. Dokaˇzite da je skup svih elemenata konaˇcnog reda podgrupa od G. 5. Koje su od sljede´cih grupa cikliˇcke? (a) Kn = {z ∈ C : z n = 1}. n

p (b) P∞ = 1}, gdje p prost p = {z ∈ C| postoji n ∈ N takav da z S (c) K = n Kn .

(d) S 1 = {z ∈ C : |z| = 1}. 6. Promatrajmo (Q, +). Promatrajmo nadalje podgrupu H 6= {0} od Q generiranu s dva elementa, tj. H =< {a, b} >, za neke a, b ∈ Q. Dokaˇzite da je H beskonaˇcna cikliˇcka. 7. Neka su Gi , i = 1, 2, . . . S podgrupe grupe G sa svojstvom Gi ⊂ Gi+1 , Gi 6= Gi+1 za sve i = 1, 2, . . .. Dokaˇzite da i Gi nije cikliˇcka. 25

Algebarske strukture

1.8

1.8. Grupe permutacija

Grupe permutacija

Definicija 1.8.1. Permutacija skupa od n elemenata je bijekcije skupa {1, 2, . . . , n} u sebe samog. Permutacije zapisujemo tradicionalno na sljede´ci naˇcin :   1 2 3 ··· n σ= . σ(1) σ(2) σ(3) · · · σ(n) Ukupno ih ima n!, a skup svih permutacija skupa od n elemenata oznaˇcavamo s Sn . Kao ˇsto smo ve´c spomenuli u ranijim poglavljima, (Sn , ◦) je grupa (pri ˇcemu ◦ oznaˇcava komponiranje, odnosno “mnoˇzenje” permutacija). Napomena 1.8.2. Mnoˇzenje permutacija nije   1 2 3 1 2 1 3 2 2 1   1 2 3 1 2 2 1 3 1 3

komutativno;   3 1 2 = 3 3 1   3 1 2 = 2 2 3

npr.  3 , 2  3 . 1

Definicija 1.8.3. Neka su i, j ∈ {1, 2, . . . , n}. Ako je i < j i σ(i) > σ(j), par (i, j) ˇcini inverziju permutacije σ. Ukupan broj inverzija u permutaciji σ oznaˇcava se s I(σ); obzirom na broj inverzija permutacije dijelimo na parne i neparne. Predznak permutacije σ se definira kao i(σ) = (−1)I(p) . Propozicija 1.8.4. Vrijedi i(σ) =

Y σ(i) − σ(j) i−j

i 4 slijedi da je |N | = 6. Dakle, N = S3 . ♦ Napomena 1.10.11. Za n > 4 grupa An nema netrivijalnih normalnih podgrupa, tj. An je prosta grupa. D.Z. Neka je H = {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)} 6 S4 . Odredite S4 /H. Teorem 1.10.12. (Prvi teorem o izomorfizmu) Neka je f : G → H homomorfizam grupa. Tada je Kerf normalna podgrupa i f inducira izomorfizam iz G/Kerf na Im f . Primjer 1.10.13. Primjenimo li teorem na homomorfizam i : Sn → {−1, 1} dobivamo izomorfizam izmedu Sn /An i Z2 . Primjer 1.10.14. Primjenimo li teorem na homomorfizam exp : (R, +) → (C× , ·), exp(t) = e2πit dobivamo izomorfizam izmedu (R/Z, +) i (S 1 , ·). 30

1.10. Kvocijentne grupe i normalne podgrupe

Algebarske strukture

Zadaci za vjeˇ zbu 1. Dokaˇzite da je presjek normalnih podgrupa (neke grupe) opet normalna podgrupa (te grupe). 2. Neka su H i K podgrupe grupe G i neka su x, y dva elementa iz G takva da vrijedi Hx = Ky. Dokaˇzite da je tada H = K. 3. Dana je podgrupa H grupe G. Tada vrijedi: H je normalna podgrupa grupe G ako i samo ako za svaka dva elementa iz G vrijedi: ab ∈ H ⇔ ba ∈ H. 4. Neka je H podskup od G, a x element iz G. Dokaˇzite: xHx−1 6 G ⇔ H 6 G. 5. Neka je H konaˇcna podgrupa grupe G. Dokaˇzite da za svaki x iz G vrijedi |H| = |xHx−1 |. 6. Neka je G grupa. Oznaˇcimo s [G, G] podgrupu generiranu elementima oblika xyx−1 y −1 (takve elemente nazivamo komutatorima). Grupu [G, G] nazivamo komutatorska podgrupa. Dokaˇzite da je [G, G] normalna podgrupa od G i dokaˇzite da je G/[G, G] komutativna grupa. 7. Neka su G1 i G2 grupe, te N1 E G1 i N2 E G2 . Dokaˇzite da je N1 ⊕ N2 E G1 ⊕ G2 . 8. Neka je N = {0, 4, 8} ⊂ Z12 . Je li N normalna podgrupa od Z12 ? Ako jest, odredite Z12 /N . 9. Je li kvocijentna grupa cikliˇcke grupe ponovno cikliˇcka? 10. Kako izgleda kvocijentna grupa (R, +)/(Z, +)? A (C, +)/(R, +)? 11. Smislite po 1 primjer za svaki od tri teorema o izmorfizmu. 12. U grupi G = Z3 ⊕ Z4 definiramo skup H = {(a, b) ∈ G : a = 0}. Dokaˇzite da je H normalna podgrupa od G, ispiˇsite sve klase u G/H i odredite ˇcemu je izomorfna grupa G/H. Pokuˇsajte poop´citi ovaj primjer; dakle promatrajmo direktnu sumu dvije grupe, i formirajmo skup analogan skupu H iz primjera. Je li to podgrupa? Je li normalna? Ako jest, kako izgleda pripadna kvocijentna grupa? 31

Algebarske strukture

1.11

1.11. Automorfizmi

Automorfizmi

Prisjetimo se, Aut G = {f : G → G | f izomorfizam grupa}, a ◦ je kompozicija funkcija, te je (Aut G, ◦) grupa jer je kompozicija homomorfizama ponovno homomorfizam i inverz svakog izomorfizma je takoder homomorfizam. Zadatak 1.11.1. Neka je G cikliˇcka grupa. Pokaˇzite da je Aut(G) komutativna grupa. Rjeˇ senje. U poglavlju o cikliˇckim grupama smo vidjeli da izomorfizam cikliˇckih grupa preslikava generator u generator. Nadalje, svaki homomorfizam ˇcija domena je cikliˇcka grupa je jedinstveno odreden djelovanjem na generatoru. Neka je G = hai. Neka su f, g ∈ Aut(G) i f (a) = ak , g(a) = al . Tada je (f ◦ g)(a) = f (al ) = f (a)l = akl = g(a)k = g(ak ) = (g ◦ f )(a). Budu´ci da su automorfizmi f ◦g i g ◦f jedinstveno odredeni djelovanjem na generatoru a, slijedi da je f ◦ g = g ◦ f . ♦ Primjer 1.11.2. Prema prethodnom zadatku znamo da je grupa Aut Zn komutativna. Ranije smo vidjeli da izomorfizam cikliˇckih grupa preslikava generator u generator, te je odreden djelovanjem na generator. Dakle, svaki automorfizam grupe Aut Zn je odreden svojim djelovanjem na 1. Oznaˇcimo te automorfizme s fi , pri ˇcemu je fi (1) = i. Tada je (Z× n , ·n ) → (Aut, ◦), i 7→ fi izomorfizam grupa (D.Z.). Zadatak 1.11.3. Odredite kojoj Abelovoj grupi je izomorfna grupa Aut Z15 . Rjeˇ senje. Prema prethodnom primjeru ta grupa je izomorfna grupi (Z× 15 , ·15 ), koja ima φ(15) = 8 elemenata (reprezentirani s 1,2,4,7,8,11,13,14). Prema strukturnom teoremu za konaˇcnogenerirane Abelove grupe, Z× cno jednoj 15 je izomorfno toˇ od sljede´ce tri grupe Z2 ⊕ Z2 ⊕ Z2 , Z2 ⊕ Z4 , Z8 . Uoˇcimo da je najve´ci red elemenata u Z2 ⊕ Z2 ⊕ Z2 jednak 2, u Z2 ⊕ Z4 je 4, a u Z8 je 8. Pogledajmo redove elemenata u Aut Z15 : |1| = 1, |2| = 4 (jer 2 ·15 2 ·15 2 ·15 2 = 24 = 1), |4| = 2, |7| = 4, |8| = 4, |11| = 2, |13| = 4, |14| = 2. Zakljuˇcujemo Aut Z15 ∼ ♦ = Z2 ⊕ Z4 . D.Z. Odredite kojoj je grupi izomorfna grupa Aut(Aut(Z8 )). Primjer 1.11.4. Neka je (G, ·) grupa i g ∈ G. Tada je preslikavanje fg : G → G zadano s fg (x) = gxg −1 automorfizam. Naime, • fg (xy) = gxyg −1 = gxg −1 gyg −1 = fg (x)fg (y) ⇒ fg je homomorfizam. • fg (x) = fg (y) ⇒ gxg −1 = gyg −1 ⇒ x = y ⇒ fg je injekcija. 32

1.12. Sylowljevi teoremi

Algebarske strukture

• Neka y ∈ G. Traˇzimo x takav da fg (x) = y. fg (x) = y ⇔ gxg −1 = y ⇔ x = g −1 yg. Dakle, fg je surjekcija. Takvi automorfizmi se nazivaju unutraˇ snji automorfizmi. Promotrimo preslikavnje ϕ : G → Int G, g 7→ fg . Pokaˇzimo da je ovo preslikavanje homomorfizam grupa. Neka su g, h ∈ G. Tada je fg ◦ fh (x) = fg (hxh−1 ) = ghxh−1 g −1 = (gh)x(gh)−1 = fgh (x) za sve x ∈ G. Dakle, fg ◦ fh = fgh , tj. ϕ(g) ◦ ϕ(h) = ϕ(gh). Oznaˇcimo li s Int(G) skup svih unutraˇsnjih automorfizama, onda je Int(G) = Im ϕ, pa zakljuˇcujemo da unutraˇsnji automorfizmi ˇcine podgrupu grupe svih automorfizama. Odredimo joˇs jezgru homomorfizma ϕ. Vrijedi g ∈ Kerϕ ⇔ fg (x) = x, ∀x ∈ G ⇔ gxg −1 = x, ∀x ∈ G ⇔ gx = xg, ∀x ∈ G. Dakle, Ker ϕ = {g ∈ G : gx = xg, ∀x ∈ G}. Ovaj skup joˇs nazivamo i centar od G i oznaˇcavamo s Z(G). Prema prvom teoremu o izomorfizmu slijedi da je Z(G) normalna podgrupa od G i G/Z(G) je izomorfno s Int(G). Ako je G komutativna grupa, onda je Z(G) = G i Int(G) je trivijalna grupa. Moˇzemo re´ci da Int(G) mjeri ”koliko je G nekomutativna”. Zadatak 1.11.5. Neka G/Z(G) cikliˇcka. Dokaˇzite da je G Abelova. Rjeˇ senje. Neka je G/Z(G) = haZ(G)i, gdje je a ∈ G. Neka su x, y ∈ G proizvoljni. Tada postoje n, m ∈ Z takvi da je x ∈ an Z(G), y ∈ am Z(G), tj. postoje u, vinZ(G) takvi da x = an u i y = am v. Slijedi xy = an uam v = an am uv = an+m vu = am an vu = am van u = yx. ♦

1.12

Sylowljevi teoremi

Prema Lagrangeovom teoremu red podgrupe dijeli red grupe. Obrat op´cenito ne vrijedi, npr. grupa A4 parnih permutacija reda 4 je grupa reda 12 koja nema podgrupu reda 6. Za grupu u kojoj je red svakog elementa oblika pr , r > 1 (za fiksiran prost broj p) kaˇzemo da je p-grupa. Ako je G grupa i H podgrupa od G koja je p-grupa, kaˇzemo da je H p-podgrupa od G. Prvi Sylowljev teorem Neka je G grupa reda pn · m pri ˇcemu je p prost broj,n > 1 i M (p, m) = 1. Tada G sadˇzi podgrupu reda pi za svako i = 1, 2, ...m, te je svaka podgrupa reda pi normalna u nekoj podgrupi reda pi+1 za i < m. Za podgrupu P grupe G kaˇzemo da je Sylowljeva p-podgrupa (za p prost) ako je P maksimalna p-podgrupa od G, tj. P 6 H 6 G, H p-podgrupa povlaˇci da je H = P ili H = G.

33

Algebarske strukture

1.12. Sylowljevi teoremi

Drugi Sylowljev teorem Ako je H p-podgrupa konaˇcne grupe G i P bilo koja Sylowljeva p-podgrupa od G, onda postoji x ∈ G takav da je xHx−1 6 P . Posebno, svake dvije Sylowljeve p-podgrupe su konjugirane. Tre´ ci Sylowljev teorem Ako je G konaˇcna grupa i p prost broj, onda broj Sylowljevih p-podgrupa od G dijeli red grupe G i oblika je kp + 1 za neki cijeli broj k > 0. Zadatak 1.12.1. Svaka podgrupa reda 17 u grupi reda 255 je normalna. Rjeˇ senje. Budu´ci da je 255 = 3 · 5 · 17, prema 3. ST je broj Sylowljevih 17-podgrupa je oblika 1 + 17k pri ˇcemu 1 + 17k|255. Kako za k > 0 broj 1 + 17k ne dijeli 17, a ni 3 · 5 = 15 slijedi da je k = 0. Sylowljeva 17-podgrupa je jedinstvena, pa prema 2. ST slijedi da je ta grupa sama sebi konjugirana ˇsto povlaˇci normalnost. ♦ D.Z. Neka su p, q prosti (ne nuˇzno razliˇciti) brojevi, a G grupa reda pq. Dokaˇzite da G sadrˇzi netrivijalnu normalnu podgrupu. Lema 1.12.2. Neka su H i K podgrupe grupe G ˇciji redovi su relativno prosti brojevi. Tada je H ∩ K = {eG }. Dokaz. Neka je |H| = h, |K| = k. Budu´ci da su h i k relativno prosti postoje cijeli brojevi a, b takvi da je ah + bk = 1. Za proizvoljan element x ∈ H ∩ K vrijedi x = x1 = xah+bk = (xh )a · (xk )b = eG .  Zadatak 1.12.3. Dokaˇzite da je svaka grupa reda 77 cikliˇcka. Rjeˇ senje. Primjetimo da je 77 = 7 · 11. Broj Sylowljevih 7-podgrupa je oblika 7k + 1 pri ˇcemu taj broj dijeli 77, tj. mora dijeliti 11. To je mogu´ce samo ako je k = 0. Kao i u 1. primjeru zakljuˇcujemo da je Sylowljeva 7-podgrupa P7 jedinstvena i normalna u ˇcitavoj grupi. Podgrupa P7 je cikliˇcka reda 7. Analogno zakljuˇcujemo da je Sylowljeva 11-pogrupa P11 jedinstvena i normalna u ˇcitavoj grupi. Podgrupa P11 je cikliˇcka grupa reda 11. Prema lemi zakljuˇcujemo da je presjek P7 ∩ P11 trivijalan, pa je njihov direktan produkt sadrˇzan u poˇcetnoj grupi. Budu´ci da je broj elemenata tog direktnog produkta upravo 77 zakljuˇcujemo da je jednak ˇcitavoj grupi. Kako je Z7 ⊕ Z11 ∼ = Z77 , zakljuˇcujemo da se radi o cikliˇckoj grupi. ♦ Zadatak 1.12.4. Grupa G reda pn , gdje je p prost broj, ne moˇze imati trivijalan centar Z(G). Rjeˇ senje. Na grupi G definiramo relaciju: x ∼ y ako postoji g ∈ G takav da je gxg −1 = y. Provjerite da je to relacija ekvivalencije! Klase ekvivalencije ove relacije nazivamo konjugacijske klase. Broj elemenata klase reprezentirane elementom x (u oznaci [x]) jednak je [G : CG (x)] pri ˇcemu je CG (x) = {g ∈ G : gx = xg} centralizator elementa x u G (provjerite da je gCG (x) 7→ gxg −1 dobro definirana bijekcija!). Budu´ci da je centarlizator elementa podgrupa od G prema Lagrangeovom teoremu [G : CG (x)]|CG (x)| = |G|, pa broj elemenata klase [x] dijeli |G| i oblika je pr , r > 0.

34

1.13. Podsjetnik iz teorije brojeva

Algebarske strukture

Primjetimo da klasa konjugacije [x] ima jedan elementa ako i samo ako je x = gxg −1 za svako g ∈ G, tj. ako i samo ako je x ∈ Z(G). Grupa G je disjunktna unija klasa konjugacija, G = K1 ∪ ... ∪ Kk . Ako bi centar Z(G) bio trivijalan tada bi postojala samo jedna klasa s jednim elementom i imali bismo pn = |G| = |K1 | + ... + |Kk | = 1 + pr2 + ... + prk , uz ri > 1, ˇsto je nemogu´ce jer je lijeva strana djeljiva s p, a desna nije. Dakle, centar ne moˇze biti trivijalan. ♦ P U dokazu smo izveli jednakost |G| = |Z(G)|+ ki=1 [G : CG (xi )], pri ˇcemu su xi , i = 1, ..., k predstavnici razliˇcitih klasa konjugacija s viˇse od jednog elementa. Tu jednakost nazivamo jednadˇ zba klasa. D.Z. Dokaˇzite da grupa reda p2 , za p prost broj, mora biti Abelova. Uputa: koristite prethodni primjer i ˇcinjenicu koju smo dokazali na vjeˇzbama: ako je G/Z(G) cikliˇcka grupa, onda je G Abelova. Zadatak 1.12.5. Odredite (do na izomorfizam) sve grupe reda 45. Rjeˇ senje. Kao u primjeru 2. zakljuˇcujemo da je ˇcitava grupa direktan produkt Sylowljeve 5-podgrupe koja je cikliˇcka i Sylowljeve 3-podgrupe, koja je reda 9, pa je prema prethodnom zadatku Abelova. Koriste´ci strukturni teorem za konaˇcnogenerirane Abelove grupe, zakljuˇcujemo da su jedine grupe reda 45 Z3 ⊕ Z3 ⊕ Z5 , Z9 ⊕ Z5 . ♦ Zadatak 1.12.6. Podsjetimo se, diedarska grupa Dn je grupa simetrija pravilnog n-terokuta. Oznaˇcimo li rotaciju oko srediˇsta za kut 2π/n s a, a osnu simetriju kroz neki fiksirani vrh s b onda imamo prezentaciju grupe Dn = ha, b|an = e, b2 = e, aba = bi. Koliko Sylowljevih 2-podgrupa ima diedarska grupa Dn za n neparan? Rjeˇ senje. Budu´ci da je red grupe Dn jednak 2n, a pretpostavili smo da je n neparan, svaka Sylowljeva 2-podgrupa je cikliˇcka reda 2. Broj Sylowljevih 2-podgrupa je neparan djelitelj broja n. Budu´ci da imamo osnu simetriju ai b, i = 1, ..., n kroz svaki vrh n-terokuta, imamo n elemenata reda 2 u Dn , pa je broj Sylowljevih 2-podgrupa upravo n. ♦

1.13

Podsjetnik iz teorije brojeva

1

Definicija 1.13.1. Neka su a 6= 0 i b cijeli brojevi. Kaˇzemo da a dijeli b (u oznaci a|b) ako postoji cijeli broj k takav da je b = ak. Teorem 1.13.2. (o dijeljenju s ostatkom) Za proizvoljan prirodan broj a i cijeli broj b postoje jedinstveni cijeli brojevi q i r takvi da je b = aq + r, 0 6 r < a. 1

Izdvojeno iz skripte prof. Dujelle ( http://web.math.hr/~duje/utb/utblink.pdf)

35

Algebarske strukture

1.13. Podsjetnik iz teorije brojeva

Napomena 1.13.3. U dokazu ove ˇcinjenice koristimo ˇcinjenicu da je (N, 1 prost ako ima toˇcno 2 pozitivna djelitelja. Ako prirodan broj a > 1 nije prost kaˇzemo da je sloˇ zen. Broj 1 nije ni prost ni sloˇzen. Teorem 1.13.8. (osnovni teorem aritmetike) Svaki se prirodan broj moˇze prikazati kao produkt prostih faktora. Slijedi da se svaki prirodan broj n moˇze zapisati u kanonskom obliku kao produkt potencija prostih brojeva n = pα1 1 pα2 2 · · · pαk k . Faktorizacija na proste faktore je jedinstvena do na poredak faktora. Definicija 1.13.9. Eulerova funkcija. Za prirodan broj n s ϕ(n) oznaˇcavamo broj elemenata skupa {1, 2, ..., n} koji su relativno prosti s n. Eulerova funkcija ϕ je multiplikativna, tj. za relativno proste brojeve m, n vrijedi ϕ(mn) = ϕ(m)ϕ(n). Ako je dana kanonska faktorizacija prirodnog broja n iz osnovnog teorema aritmetike onda imamo formulu      1 1 1 1− ··· 1 − . ϕ(n) = n 1 − p1 p2 pk Definicija 1.13.10. Ako cijeli broj m 6= 0 dijeli a − b kaˇzemo da je a kongruentno b modulo m i oznaˇcavamo a ≡ b (mod m). Napomena 1.13.11. Relacija ’biti kongruentan modulo m’ je relacija ekvivalencije na skupu cijelih brojeva. Propozicija 1.13.12. (svojstva kongruencija) • Ako je a ≡ b( mod m) i c ≡ d( mod m) onda vrijedi a + c ≡ b + d( mod m), ac ≡ bd( mod m) i ka ≡ kb( mod m) za svaki cijeli broj k. • Neka su a, b cijeli brojevi te k, m prirodni brojevi takvi da je (k, m) = d. Ako je ka ≡ kb( mod m), onda vrijedi a ≡ b( mod m/d). • Ako je a ≡ b( mod m) i n prirodan broj, onda je an ≡ bn ( mod m). • Neka je f polinom s cjelobrojnim koeficijentima. Ako je a ≡ b( mod m), onda vrijedi f (a) ≡ f (b)( mod m). 36