This is an old version of the compendium, written May 4, 2014, 11:33 a.m. Changes made in this revision were made by trmd. View rendered version.

TMA4150: Algebra og tallteori

# Introduksjon ## Forord Kompendiet vil bli strukturert nesten regelrett etter oppbygningen til [John B. Fraleigh, A First Course in Abstrct Algebra] Under vil en kjapp repitisjon av mengder og relasjoner bli gitt. ## Mengde

`>Det er umulig å definere alle konsepter`

"En ku er et pattedyr". Men hva er et pattedyr? "Et pattedyr er en undergruppe av virveldyrene". Men hva er et virveldyr? "Virveldyr er dyr med et indre skjelett" Men hva er dyr?... ... Og slik kan du holde på til du ikke har flere ord igjen i ordboken, og må definere dine tidligere definisjoner med ord du allerede har brukt, og ender opp med sirkulære definisjoner. Dette gjelder også i matematikken. Dermed må vi ha et _udefinert, primitivt_ konsept som et startsted for videre definisjoner. I matematikken er dette konseptet en __mengde__. En mengde er en veldefinert samling av unike __elementer__, også kalt __objekter__. Hvis et element $a$ er i en mengde $S$, skriver vi dette $a \in S$. Det er en og bare en mengde uten elementer, kalt den __tomme mengden__, $\emptyset$. Det er flere måter å beskrive en mengde. En vanlig notasjon er klammeparenteser, for eksempel: $$ \{1, 2, 3, 4\} $$ Hvis vi vil ha en mengde med elementer som tilfredstiller et vilkårlig kriterie, $ P(x) $, skriver vi $$ \{x \>|\> P(x)\} $$ lest "mengden av alle x slik at P(x) er tilfredstilt". Vi kan også beskrive en mengde direkte, som "Mengden av alle røde biler i Oppdal", eller "Alle primtall". Beskrivelsene $$ \{1, 2, 3, 4, 5\} $$ $$ \{x \>|\> x \in \mathbb{Z^+} \>\text{and}\> x < 6\} $$ $$ \text{Alle positive heltall mindre enn 6} $$ beskriver samme mengde. En mengde må være __veldefinert__. Det vil si at beskrivelser som "Mengden av noen tall over 10" ikke kan brukes om en mengder. På en annen side må vi ikke kjenne til alle elementer i en mengden for å beskrive mengden. Selv om vi ikke kjenner til alle primtall, kan vi uten problemer definere mengden "Alle primtall". En mengde som ikke er av uendelig størrelse, kalles en __endelig mengde__. ### Delmengde Vi sier at en mengde $B$ er en __delmengde__ av en mengde $A$, hvis alle elementer i B også er i A. Dette skrives $$ B \subseteq A $$ Hvis A inneholder elementer ikke i B, er B en __ekte delmengde__ av A, og skrives $$ B \subset A $$ B er en ekte delmengde av A hvis og bare hvis $B \subseteq A$ og $B \neq A $. For en hver mengde $A$ er $A$ den __uekte delmengden__ til A. En hver annen delmengde til $A$ er en ekte delmengde __Eksempel__ Finn alle delmengdene til $S = \{5, 4, 3\}$. Settet har åtte delmengder: $$ \emptyset, \{3\}, \{4\}, \{5\}, \{3, 4\}, \{3, 5\}, \{4, 5\}, \{3, 4, 5\} $$ Merk at rekkefølgen på elementene er uten betydning. ## Kartesisk produkt For to mengder $A$ og $B$ er det kartesiske produktet definert ved $$ A \times B = \{(a, b) | a \in A\> \text{and}\> b \in B\} $$ Altså alle mulige tupler dannet ved et element fra $A$ og ett fra $B$. __Eksempel__ La $A = \{1, 2\}, B = \{3, 4\}$. Finn $ A \times B$. $$ A \times B = \{(1,3), (1,4), (2,3), (2,4)\} $$ ## Viktige tallmengder || $\mathbb{Z}$ || Mengden av alle heltall|| || $\mathbb{Q}$ || Mengden av alle rasjonale tall|| || $\mathbb{R}$ || Mengden av alle reelle tall|| || $\mathbb{C}$ || Mengden av alle komplekse tall|| Mengden $\mathbb{Z}^+$ er mengden av alle positive heltall. Tilsvarende gjelder for de andre tallmengdene. Mengden $\mathbb{Z}^*$ er mengden av alle heltall utenom $0$. Tilsvarende gjelder for de andre tallmengdene. Mengden $R \times R$ er det to-dimensjonale euklidiske plan. ## Relasjoner En relasjon mellom to mengder er en delmengde $\mathscr{R}$ av $A \times B$. Vi sier for hvert element $(a, b)$ i denne delmengden, så er $a$ relatert til $b$, og skriver $a \>\mathscr{R}\> b$. Enhver relasjon mellom en mengde $A$ og seg selv er en __relasjon på__ $A$. Et eksempel på en relasjon er funksjonen $f(x) = x$, som kan skrives som delmengden $\{(x,x) | x \in \mathbb{R}\}$ av $\mathbb{R} \times \mathbb{R}$. En __funksjon__ $\phi$ som transformerer et element i $X$ til et element i $Y$ sies å være en __mapping__ mellom $X$ og $Y$. Dette skrives $\phi: \> X \; \rightarrow \; Y$. En slik funksjon er en relasjon mellom $X$ og $Y$. Vi skriver (som kjent) en relasjon mellom to elementer, $(x,y) \in \phi$, som $\phi(x) = y$. For en slik funksjon er $X$ __definisjonsmengden__, $Y$ __verdiområet__, og $phi[X]$ __verdimengden__ til $\phi$. ## Kardinalitet Kardinaliteten til en mengde $A$ er antall elementer i $A$. Kardinaliteten til en mengde $S = \{1,2,3\}$ er altså $3$. (TODO: Skrive om kardinaliteten til mengder som f.eks. $\mathbb{Z}?) ## Surjektivitet

>En funksjon $\phi\>:\>X\>\rightarrow\>Y$ er __surjektiv__, eller __på__, hvis og bare hvis $\phi[X] = Y$. Altså hvis verdiene til $X$ etter å ha bli transformert av $\phi$, utgjør hele $Y$. Vi sier at $\phi$ er en surjeksjon fra $X$ på $Y$.

(TODO: Eksempler) ## Injektivitet

>En funksjon $\phi\>:\>X\>\rightarrow\>Y$ er __injektiv__, eller __en-til-en__, hvis og bare hvis for hver $y \in Y$, så finnes det bare en $x \in X$, s.a. $\phi(x) = y$.

(TODO: Eksempler) ## Bijektivitet

>En funksjon er __bijektiv__ hvis den er både injektiv og surjektiv.

(TODO: Eksempler) ## Ekvivalensrelasjoner En relasjon er en __ekvivalensrelasjon__ på en mengde $S$ hvis den er __refleksiv, symmetrisk__ og __transitiv__. ### Refleksiv

>En relasjon $\mathscr{R}$ på $S$ er refleksiv hvis for hver $x \in S$, så er $x\>\mathscr{R}\>x$.

__Eksempel__ $$ \{(1,1), (2,2), (1,3), (3,3)\}$$ ### Symmetrisk

>En relasjon $\mathscr{R}$ på $S$ er symmetrisk hvis for hver $x,y \in S$, og $x\>\mathscr{R}\>y$ så er $y\>\mathscr{R}\>x$.

__Eksempel__ $$ \{(1,1), (2,3), (3,2)\} $$ ### Transitiv

>En relasjon $\mathscr{R}$ på $S$ er transitiv hvis for hver $x,y,z \in S$, og $x\>\mathscr{R}\>y$, $y\>\mathscr{R}\>z$, så er $x\>\mathscr{R}\>z$.

__Eksempel__ $$ \{(1,1), (1,2), (2,3), (1,3) \} $$ ## Binære operasjoner En __binær operasjon__ $*$ på en mengde $S$, er en funksjon som mapper $S \times S$ til S. Vi skriver $*(a,b)$ som $a*b$. Operasjonen tilegner $(a,b)$ en annen verdi i $S$. Eksempelvis er $+$(addisjon) $\cdot$(multiplikasjon) binære operasjoner på $\mathbb{Z}$. >La $*$ være en binær operasjon på $S$, og la $H$ være en delmengde av $S$. $H$ er __lukket under__ $*$ hvis for alle $a, b \in H$, så er $a$*$b \in H$. I dette tilfellet hvor den binære operasjonen er begrenset til $H$, kaller vi operasjonen den __induserte operasjonen__ av $*$ på $H$. __Eksempel (2.6 i boka)__ La $+$ og $\cdot$ være de binære operasjonene addisjon og multiplikasjon på $\mathbb{Z}$, og la $H = \{x^2 \>|\>x \>\in\> \mathbb{Z^+}\}$. Er $H$ lukket under 1. Addisjon? 2. Multiplikasjon? Det kan først være greit å gjøre seg kjent med delmengden vår, $H$. Den er i kortfattethet mengden av alle kvadrater for positive heltall: $$\{1, 4, 9, \ldots\} $$ For addisjon ser vi at siden $1$ og $4$ begge er i $H$, men $1+4 = 5$ ikke er i $H$: $5 \notin H$. Så H er __ikke__ lukket under addisjon. For multiplikasjon går vi litt mer generelt til verks: La $x \in H$ og $y \in H$. Utifra definisjonen til $H$ (alle kvadrater), må det finnes $a, b \in S$ slik at $a^2 = x, b^2 = y$. Multiplikasjon mellom $x$ og $y$ kan dermed skrives $$ x\cdot y = a^2\cdot b^2 = (a\cdot b)^2 \in H $$ siden $(ab)^2$ også er et kvadrat. $H$ er dermed lukket under multiplikasjon. ### Kommutativitet

>En binær operasjon $*$ er __kommutativ__ på en mengde $S$ hvis og bare hvis

$$ a*b = b*a $$ for alle $a,b \in S$. ### Assosiativitet

>En binær operasjon $*$ er __assosiativ__ på en mengde $S$ hvis og bare hvis

$$(a*b)*c = a*(b*c)$$ for alle $a,b,c \in S$. ## Tabell-notasjon (TODO) ## Isomorfier (TODO) # Grupper

>En __gruppe__ $\left<G, *\right>$ er en mengde $G$, lukket under en binær operasjon $*$, slik at de tre følgende aksiomene holder: > >$\mathscr{G}_1$: $*$ er assossativ: For alle $a, b, c \in G$ er > >$$ (a * b) * c = a * (b * c) $$ > >$\mathscr{G}_2$: Det finnes et element $e \in G$, kalt __identitetselement__, slik at for alle $x \in G$ er > >$$ e * x = x * e = x $$ > >$\mathscr{G}_3$: For hver $a \in G$, finnes det en __invers__ $a' \in G$, slik at > >$$ a * a' = e $$

Heretter kommer en gruppe $G$ med binær operasjon $*$ til å bli refert til som $G$ _under_ $*$. __Teorem__ For en gruppe $G$ under den binære operasjonen $*$, gjelder __høyre og venstre kanselleringslov__, dvs $$ a * b = a * c \Longleftrightarrow b = c $$ $$ b * a = c * a \Longleftrightarrow b = c $$ __Eksempel__ Er $\mathbb{Z}$ en gruppe under (a) addisjon, (b) multiplikasjon? (a): Vi sjekker hvert aksiom: 1. (a+b)+c = a+(b+c). $+$ er assossiativ 2. Identitetselementet er $0$ siden $a + 0 = 0 + a = a$ 3. For en hver $x \in Z$ finnes det en invers $-x \in Z$. $\mathbb{Z}$ er dermed en gruppe under addisjon. (b): Vi sjekker hvert aksiom: 1. $(a\cdot b)\cdot c = a \cdot (b \cdot c)$ 2. $1\cdot a = a\cdot 1 = a$ 3. Her rakner det. I $\mathbb{Z}$ har vi ingen invers. Ta for eksempel tallet $4$. Tallet $b$ som gjør $b\cdot4 = 1$ er $b = \frac{1}{4} \notin \mathbb{Z}$ $\mathbb{Z}$ er dermed _ikke_ en gruppe under multiplikasjon. Vi går heretter igjennom eksempelene litt kjappere. __Eksempel__ Er $\mathbb{Z}^*$ en gruppe under (a) addisjon, (b) multiplikasjon? (a): Fra det forige eksemplet vet vi at $\mathbb{Z}$ er en gruppe under addisjon. Men dette var avhengig av identitetselementet $0$, som vi ikke har i $\mathbb{Z}^*$. $\mathbb{Z}^*$ er dermed ikke en gruppe under addisjon. (b): $\mathbb{Z}^*$ er ikke en gruppe under multiplikasjon av samme argument som for eksemplet ovenfor: vi har ingen invers. __Eksempel__ Er $\mathbb{Q}^+$ en gruppe under (a) addisjon og (b) multiplikasjon? (a): $\mathbb{Q}^+$ er ikke en gruppe under addisjon siden for et element $q \in Q^+$ må en invers være $-q$, som ikke er i $\mathbb{Q}^+$. (b): 1. Multiplikasjon er assossiativt. 2. Identitet $e = 1$ 3. For enhver $q \in \mathbb{Q}^+$, har vi en $q' \in \mathbb{Q}^+$ definert ved $q' = 1/q$ som gjør $q \cdot q' = q \cdot \frac{1}{q} = 1$ $\mathbb{Q}^+$ er dermed en gruppe under multiplikasjon. __Eksempel__ La $G = \{1, 2, 3, 4\}$ og definer $*$ ved $ a * b =$ __min__$(a,b)$ hvor min er funksjonen som velger den minste av $a$ og $b$. eller $a$ hvis de er like. Er $G$ under $*$ en gruppe? Det holder å finne et moteksempel. Vi ser at $G$ har identitetselement $4$, siden $4$ er det største elementet. Samtidig har vi ingen invers, siden for enhver $a \in G$ og $a < 4$, vil $a * b < 4$ for hver $b \in G$. $G$ er dermed ikke en gruppe under $*$. _Utfordring:_ Er $*$ assossiativ? ## Abelske grupper En gruppe $G$ er abelsk hvis dens binære operasjon er kommutativ, altså $$ a * b = b * a $$ for hver $a,b \in G$. $\mathbb{Z},\> \mathbb{N},\> \mathbb{R}\> og\> \mathbb{C}$ under addisjon er alle abelske grupper. En binær operasjon på en abelsk gruppe benevnes ofte $+$. Generelt skrives binære operasjoner ofte bare ved sidestilling av elementer, i.e. $a * b = ab$. ## Endelige grupper Hittil, med unntak av det siste eksemplet under [Grupper](#grupper), har vi bare håndtert uendelige grupper. En __endelig gruppe__ er en mengde $G$ med et endelig antall elementer under en binær operasjon $*$. (TODO: Tabeller) # Undergrupper # Sykliske grupper # Permutasjonsgrupper # Orbitaler # Restklasser # Lagranges Teorem # Endelig-genererte abelske grupper # Homomorphismer # Faktorgrupper # Gruppevirkninger # Ringer Hittil har vi bare diskutert _grupper_, som er en mengde $G$ med en tilhørende binær operasjon $*$. Det er av interesse for oss å diskutere mengder med _to_ tilhørende binære operasjoner, kalt ringer.

>En __ring__ $\left<R, +, \cdot\right>$ er en mengde $R$ med to tilhørende binære operasjoner $+$ og $\cdot$, kalt _addisjon_ og _multiplikasjon_. For en slik ring $R$, er følgende aksiomer tilfredstilt: >$\mathscr{R}_1$: $\left<R, +\right>$ er en abelsk gruppe. >$\mathscr{R}_2$: Multiplikasjonen er assosiativ >$\mathscr{R}_3$: For alle $a,b,c \in R$, gjelder den __venstre distributive lov__; $a \cdot (b+c) = a\cdot b + a\cdot c$, og den __høyre distributive lov__; $(a+b)\cdot c = a\cdot c + a\cdot b$.

Eksempler på ringer er $\left<\mathbb{Z}, +, \cdot\right>$, $\left<\mathbb{Q}, +, \cdot\right>$, og $\left<\mathbb{C}, +, \cdot\right>$. $M_n(\mathbb{R})$, mengden av $n \times n$-dimensjonale matriser, under addisjon og matrise-multiplikasjon, er også et eksempel på en ring. Det kan også vises at $\mathbb{Z}_n$ er en ring under addisjon og multiplikasjon, hvis multiplikasjon defineres til å være _resten_ av vanlig heltalsmultiplikasjon, modulo $n$ (denne operasjonen kalles for __multiplikasjon__ modulo $\mathbb{Z}_n$). ## Direkte produkt For ringer $R_1, R_2, \dots, R_n$ er det __direkte produktet__ av ringene en n-tuppel $R_1 \times R_2 \times R_3 \dots R_n$. Det direkte produktet er selv en ring, med addisjon og multiplikasjon definert elementvis. ## Homomorfier

>For ringer $R$ og $R'$ er en avbildning $\phi\>:\>R\>\rightarrow\>R'$ en __homomorfi__ hvis og bare hvis, for alle $a,b \in R$: > >1. $\phi(a+b) = \phi(a) + \phi(b)$>2. $\phi(a\cdot b) = \phi(a)\cdot \phi(b)$

En kan si at homomorfien må gjelde både for ~~både~~den additive operasjonen og den multiplikative operasjonen til R.

Mer om dette under [Ringhomomorfier](#ringhomomorfier-og-faktorgrupper). ### Evalueringshomomorfien __Evalueringshomomorfien__ er homomorfien $\phi_a$, som avbilder ringen $F$, alle funksjoner fra $\mathbb{R}$ til $\mathbb{R}$, til $\mathbb{R}$. Denne kommer til å bli hyppig brukt til videre diskusjon av løsning av polynomielle likninger. ### Ismorfiser En __isomorfi__ $\phi\>:\>R\>\rightarrow\>R'$ er en homomorfi som også er _en-til-en_ og _på_ $R'$. ## Kommutative ringer, Divisjonsringer og Kropper En ring med _kommutativ multiplikasjon_ er en __kommutativ ring__. En ring med en __multiplikativ identitet__ kalles for en __ring med enhet__. En ring med __multiplikativ invers__ for hvert element ikke lik 0, dvs. en $r' \in R$ for hver $r \in R$ slik at $rr' = e$ , kalles en __divisjonsring__. En __kropp__ er en kommutativ divisjonsring. Altså en ring med kommutativ multiplikasjon som har en multiplikativ invers for hvert element i ringen. (TODO: Eksempler) ## Underring & Underkropp En underring $S$ av en ring $R$ er logisk nok (gitt tilsvarende konsept for grupper) en delmengde $S \subseteq R$ lukket under de to binære operasjonene til $R$. En underkropp følger analogt for en kropp. ## Integritetsdomene Før vi kan definere integritetsdomener må vi kjenne til _nulldivisorer_. To elementer $a,b \in \mathbb{R}$ er __nulldivisorer__ hvis $ab = 0$, og hverken $a$ eller $b$ er $0$. __Eksempel__ Er $a = 3$ og $b = 4$ nulldivisorer i $\mathbb{Z}$? Siden $3\cdot 4 = 12$ er $a,b$ _ikke_ _nulldivisorer_. __Eksempel__ Er $a = 3$ og $b = 4$ nulldivisorer i $\mathbb{Z}_6$? $3\cdot 4 = 12 = 0$ i $\mathbb{Z}_6$. Altså er $a,b$ nulldivisorer i $\mathbb{Z}_6$. Vi er nå klare til å definere integritetsdomener: Et __integritetsdomene__ $D$ er en kommutativ ring med multiplikativ identitet $1 \neq 0$ som inneholder _ingen_ nulldivisorer. Det er lett å overbise seg om at $\mathbb{Z}$ er et integritetsdomene. __Teorem__ I $\mathbb{Z}_n$ er nulldivisorene alle elementer som ikke er lik $0$, og som ikke er relativt primiske til $n$. __Bevis__ La $m \in \mathbb{Z}_n$, hvor $m \neq 0$, og la den største fellesnevneren mellom $m$ og $n$ være $d \neq 1$. Vi har $$ m \left(\frac{n}{d}\right) = \left(\frac{m}{d}\right)n $$ $(m/d)n$ må være $0 \>\text{mod}\> n$, som betyr at $\left(\frac{n}{d}\right) m = 0$ (begge sider må være like). Men siden hverken $\frac{n}{d}$ eller $m$ er $0$, må $m$ være en nulldivisor. La så $m \in \mathbb{Z}_n$ være relativt primisk til $n$. For hver $s \in \mathbb{Z}_n$ hvor $s\cdot m = 0$, må $n$ dele $s$, og $s = 0$ i $\mathbb{Z_n}$. __Korollar__ Hvis $p$ er et primtall, har $\mathbb{Z}_p$ ingen nulldivisorer. Bevis for teoremene under kan finnes på s. 180 i boka. __Teorem__ En hver kropp $F$ er et integritetsdomene. __Teorem__ Et hvert endelig integritetsdomene er en kropp. __Korollar__ Hvis $p$ er et primtall, er $\mathbb{Z}_p$ en kropp. (Dette faller ut av forige teorem og forige korollar) Vi fullfører ringer med å definere karakteristikken til en ring: __Karakteristikken__ til en ring er det laveste heltallet $n$, slik at $n\cdot a = 0$ for _alle_ $a \in R$. Hvis inget slik heltall eksisterer, er R av karakteristikk $0$. Karakteristikken til $\mathbb{Z}_n$ er $n$. # Eulers og fermats teoremer ## Fermats Lille Teorem Vi begynner med å konstatere noe som kanskje nå er åpenlyst: `For en hver mengde, danner alle elementer ikke lik 0 en gruppe under multiplikasjon` La oss nå se på elementene i $\mathbb{Z}_p$: $$ 1,2,3,\ldots,p-1 $$ Et hvert element i denne gruppen er som tidligere nevnt syklisk, og generer undergrupper av en orden $m$, som deler $p-1$ (per definisjon). Dermed må $b^{p-1} = 1$ i $\mathbb{Z}_p$ for hver $b \in \mathbb{Z}_p$ ikke lik $0$ (siden $b^{m} = 1$, og $b^{p-1} = b^{km}$ hvor $k = (p-1)/m$). Siden $\mathbb{Z}_p$ er isomorf til ringen av restklasser $a + p \mathbb{Z}$, må enhver $a \in \mathbb{Z}$ som ikke er i restklassen $0 + p \mathbb{Z}$(merk at dette er det analoge kriteriet til $b \neq 0$ ovenfor, gitt isomorfien) følge $$ a^{p-1} = 1 (\text{mod} p) $$ Dette gir oss __Fermats Lille Teorem__:

~~__Teorem__~~ >Hvis $a \in \mathbb{Z}$ og $p$ er et primtall som ikke deler $a$, så deler $p$ $a^{p-1} -1$, altså $$ >$$ >a^{p-1} \equiv 1 (\text{mod} p), a \not\equiv 0 (\text{mod}\> p)>$$

__Korollar__

Hvis $a \in \mathbb{Z}$, så er $a^p \equiv a\> (\text{mod}\> p)$ for en hver $p$. __Eksempel__ Hva er $8^{903}\> (\text{mod}\> 17)$? Trikset her er å dele opp tallet i en base $a$ udelbar med $p$, og en eksponent lik $p-1$: (TODO: Verifiser, dette ble regnet litt fort) $$ \begin{array}{l} 8^{903} &\equiv (8^{16})^{56}\cdot8^7 \equiv (1^{56})\cdot 8^7 \equiv (8^2)^3 \cdot 8 \equiv (64)^3 \cdot 8 \equiv 13^3\cdot 8 \equiv (-4)^3 \cdot 8 \\ &\equiv -64\cdot 8 \equiv -13 \cdot 8 \equiv 4 \cdot 8 \equiv 32 \equiv -2 \equiv 15\> (\text{mod}\> 17) \end{array} $$ ## Eulers Teorem __Eulers phi-funksjon__ $\phi(n)\>:\>\mathbb{Z}^+ \rightarrow \mathbb{Z}^+$, er antall elementer ikke lik 0 i $\mathbb{Z}_n$ som ikke er nulldivisorer. Med denne kan vi gi Eulers Teorem.

~~__Teorem__~~ >Hvis $a$ er et heltall relativt primisk til $n$, er $a^{\psi(n) - 1}$ delbart med $n$, altså er $$ > >$$ >a^{\psi(n) - 1} = 1 (\text{mod}\> n)>$$

La oss se på $n = 16$. De positive heltallene som er relativt primisk til 16 er: $3, 5, 7, 9, 11, 13, 15$. Dette gir $\phi(n) = 7$. Vi kan dermed konstatere at $$ 3^{7} = 5^{7} = 7^{7} = 9^{7} = 11^{7} = 13^{7} = 15^{7} = 1 (\text{mod}\>16) $$ # Polynomer ## Ringer av polynomer Det kan være lurt å formalisere noen konsepter vi tidligere "har tatt for gitt", og introdusere noen nye utrykk. For et polynom av $x$, skal vi unngå å kalle $x$ for en __variabel__, men heller for en __ukjent__. Videre skal vi unngå å la $x$ "ta på seg verdier". Altså skal vi unngå å skrive ting som $x = 5$. $x$ fungere som et symbol i seg selv. Settet av alle polynomer med koeffesienter i ringen $R$, skrives $R[x]$. For en ring $R$, er et polynom $f(x)$ med __koeffesienter__ i $R$ en uendelig formell sum $$ f(x) = \sum_{i=0}^{\infty} a_i x^i = a_0 + a_1x + a_2x^2 + \dots + a_n x^n + \dots $$ $a_i$ er __koeffesientene til__ $f(x)$, og hvis det finnes en $i \geq 0$ slik at $a_{n} = 0$, for alle $n \geq i$, er $i$ __graden__ til polynomet. Vi skriver polynomet som en uendelig sum, ikke en endelig sum, for å unngå flere definisjoner av samme polynom, e.g $$ 2x + x^2 = 0 + 2x + x^2 + 0x^3 = 2x + x^2 + 0x^{101} $$ Merk vi i all hovedsak skal arbeide med _kropper av polynomer_. Det kan vises at for en kropp $F$ er $F[x]$ et integritetsdomene. __Eksempel__ Ekspander $(x+3)^4$ i $\mathbb{Z}_ 4$. $$ \begin{align} (x+3)(x+3)(x+3) &= x^4 + (1+1+1+1)x^3 + (1+1+1+1+1+1)x^2 \\ + (1+1+1+1)x + 1 &=x^4 + 0x^3 + 2x^2 + 1 = x^4 + 2x^2 + 1 \end{align} $$ ### To og flere ukjente For to ukjente, sier vi at $R[x,y]$ er ringen av polynomer for __to ukjente__ $x$ og $y$ med koeffesienter i $R$. For flere, sier vi at $R[x_1, x_2, \dots, x_n]$ er ringen av polynomer for __n ukjente__ $x_i$ med koeffesienter i $R$. ## Evalueringshomomorfien, part II

Det er nå hensiktsmessig å se tilbake på [evalueringshomomorfien](#evalueringshomomorfien), og definere den for ~~$kropper$~~kropper.

Har vi to kropper $F$ og $E$, med $F \leq E$, og for $\alpha \in E$, har vi __evaluasjonshomomorfien__ $$ \phi_{\alpha}\>:\>F[x] \rightarrow E \\ \phi_{\alpha}(a_0 + a_1x + \dots + a_nx^n) = a_0 + a_1 \alpha + \dots \ a_n $$ Homorfien $\phi_{\alpha}$ kalles for __evalueringen av__ $\alpha$. Det er nå klart at en "løsning" av et polynom, er enhver evalueringshomomorfi $\phi_{\alpha}$ slik at polynomet er i $\text{Ker}(\phi_{\alpha})$. (TODO legge link til kjerne-kapitellet når det kommer på plass). En $\alpha$ slik at $f(\alpha) = 0$ er __en rot__ av polynomet. Grunnen til at ordet løsning var i hermetegn over, var at vi ikke lenger snakker om å _løse_ et polynom, men heller om å _finne røttene_ til polynomet. __Eksempel__ La $\phi_{2}$ være evalueringshomomorfien $\phi_{2}\>:\>\mathbb{Q}[x]\>\rightarrow\>\mathbb{R}$. Beskriv $N = \text{Ker}(\phi_2)$. Er $x^3 - x^2 - 2$ i $N$? $\text{Ker}(\phi_2)$ er alle polynomer $f(x)$ slik at $\phi_2(f(x)) = 0$. $$ \phi_2(x^3 - x^2 - 2) = 2^3 - 2^2 - 2 = 8 - 4 - 2 = 2 \neq 0 $$ Altså er $x^3 - x^2 - 2$ ikke i $\text{Ker}(\phi_2)$. ## Faktorisering av polynomer

~~__Teorem__~~ >La $F[x]$ være en kropp av polynomer, og la $f(x), g(x) \in F[x]$ være to polynomer i $F[x]$. Da kan $f(x) skrives$ $$ > >$$ >f(x) = g(x)q(x) + r(x)$$ >$$ >hvor $q(x), r(x) \in F[x]$. Dette kalles for __divisjonsalgoritmen for__ $F[x]$.

Merk likhetstrekkene til divisjonsalgoritmen for $\mathbb{Z}$. (TODO: link til denne når den kommer på plass)

~~__Teorem__~~ >Et element $a \in F$ er en rot i $f(x) \in F[x]$ hvis og bare hvis $x - a$ er en faktor av $f(x)$ i $F[x]$. ~~__Teorem__~~ >Et polynom ikke lik $0$ i $F[x]$ av grad $n$ kan maksimalt ha $n$ røtter.

De to siste av disse teoremene har vi brukt hyppig ~~ved~~ for å finne røttene til polynomer helt fra den videregående skole.

## Irredusible polynomer

>Et polynom $f(x) \in F[x]$ er __irredusibel__ i $F$ hvis polynomet ikke kan skrives som et produkt $f(x) = g(x)h(x)$ hvor $g(x), h(x) \in F[x]$ er polynomere av lavere grad enn $f(x)$.

Et eksempel på et irredusibelt polynom er $x^2 - 2$ i $\mathbb{Q}$, siden $\sqrt{2} \not\in \mathbb{Q}$. Det er dermed viktig å merke seg at et polynom irredusibelt i en delmengde $F \leq E$, kan være redusibelt $E$. Her illustrert ved at $x^2 -2$ er redusibelt i $\mathbb{R}$, og $\mathbb{Q} \subseteq \mathbb{R}$. (TODO: Eksempler) ### Eisenstein-kriteriet

>La $p \in \mathbb{Z}$ være et primtall, og la $f(x) = a_n x^n + \dots + a_0 \in \mathbb{Z}[x]$. La også $a_n \not\equiv 0 (\text{mod} p)$, $a_i = 0 (\text{mod}\>p)$ for alle $i < n$ og $a_0 \not\equiv 0 (\text{mod}\>p^2)$. Da er $f(x)$ irredusibel over $\mathbb{Q}$.

# Ringhomomorfier og faktorringer ## Ringhomomorfier Vi repeterer homomorfier en siste gang, og definerer de analoge resultatene av [homomorfier](#homomorfier) for ringer. La $\phi$ være en homomorfi fra en ring $R$ til en ring $R'$. La $0$ være det additive identitetselementet i $R$. Da er $\phi(0)$ det additive identitetselementet i $R'$. For hver $a \in R$, er $\phi(-a) = - \phi(a)$. La $S$ være en underring av $R$. Da er $\phi[S]$ en underring av $R'$. Tilsvarende, la $S'$ være en underring av $S$. Da er $\phi^{-1}[S']$ en underring av $R$. La $1$ være multiplikativ identitet i $R$. Da er $\phi(1)$ multiplikativ identitet i $\phi[R]$. (Men _ikke_ nødvendigvis i $R'$!) (TODO: Eksempler) ### Kjerne

>La $\phi\>:\>R\>\rightarrow\>R'$ være en ringhomomorfi. Da er underringen $$ > >$$ >\phi^{-1}[0'] = \{r \in R | \phi(r) = 0'\}$$ >$$ >__kjernen__ til R.

## Faktorringer La $\phi\>:\>R\>\rightarrow\>R'$ være en ringhomomorfi med kjerne $H$. De additive restklassene til $H$ danner en ring $R/H$. Avbildningen $\mu\>:\>R/H\rightarrow\>\phi[R]$ definert ved $\mu(a + H) = \phi(a)$ er en isomorfi. Den additive delen av dette er allerede konstatert (og bevist i boken) for [faktorgrupper](#faktorgrupper). ### Idealer I gruppeteori, definerte vi [normale undergrupper](#normale-undergrupper). Tilsvarende for ringer har vi idealer. La $N$ være en additiv undergruppe av en ring $R$. N er et $ideal$ hvis $$ aN \subseteq N,\; Nb \subseteq N\; \text{for alle a,b} \in R $$ Vi kan nå definere faktorringer.

>La $N$ være et ideal av en ring $R$. De additive restklassene av $N$ danner en ring $R/N$, __faktorringen av__ $R$ ved $N$, ved de binære operasjonene addisjon og multiplikasjon, definert ved $$ > >$$ >(a + N) + (b + N) = (a + b) + N \\>(a + N)(b + N) = (ab) + N>$$

(TODO: Eksempler) ### Fundamentalteoremet for homomorfier II Har du lest [fundementalteoremet for homomorfier](#fundamentalteoremet-for-homomorfier), vil det følgende knapt overraske: La $\phi\>:\>R\>\rightarrow\>R'$ være en homomorfi med kjerne $N$. Da er $\phi[R]$ en ring, og avbildningen $\mu\>:\>R/N\>\rightarrow\>\phi[R]$, gitt ved $\mu(x + N) = \phi(x)$ er en isomorfi. Hvis $\gamma\>:\>R\rightarrow\>R/N$ er homomorfien gitt ved $\gamma(x) = x + N$, har vi for hver $x \in R$ at $\gamma\mu(x) = \phi(x)$. ### Maksimale idealer

Hver ring $R$, ikke lik 0, har minst 2 idealer: det __uekte idealet__ $R$, og det __trivielle idealet__ ${0}$. Ett __ekte ikke-trivielt ideal__ av en ring $R$, er er ideal $N$, slik at $N \neq R$ og $N \neq {0}$. ~~__Teorem__~~ >Hvis $R$ er en ring med identitet, og $N$ er et ideal av $R$ som inneholder en enhet, er $N = R$

Et __maksimalt ideal av en ring__ R, er et ideal $M$ forskjellig fra $R$, slik at det ikke finnes noe ideal $N$ av $R$ slik at $M \subset N$.

~~__Teorem__~~ >Hvis $R$ er en kommutativ ring med identitet, er $M$ et maksimalt ideal av $R$ hvis og bare hvis $R/M$ er en kropp.

(TODO: Eksempler) # Sylowteori I [endelig-genererte abelske grupper](#endelig-genererte abelske grupper) klassifiserte vi endelig-genererte abelske grupper fullstendig. Dette er ikke fullt så lett å gjøre for grupper som ikke er abelske. Men teoremene til Peter Ludvig Mejdell Sylow hjelper oss et stykke på vei. Først må vi få noen definisjoner på plass: La $G$ være en gruppe av orden $p^n$, hvor $p$ er et primtall, og la $X$ være et endelig $G$-mengde. Da er $|X| = |X_G|$ hvor $X_G = \{x \in X\> |\> gx = x \>\text{for alle}\> g \in G\}$ (altså unionen av alle en-element orbitaler i $X$).

La så $p$ være et primtall. En gruppe $G$ er e~~t primtall~~n $p$-gruppe, hvis hvert element i $G$ har orden $p^i$, altså en potens av $p$. En $p$-__undergruppe__ er en undergruppe av en $p$-gruppe som selv er en $p$-gruppe. __## Cauchy's Teorem__ >La $p$ være et primtall, og la $G$ være en endelig gruppe hvor $p$ deler $|G|$. Da har $G$ et element av orden $p$, og dermed en undergruppe av orden $p$.

__Korollar__

>La $G$ være en endelig gruppe. $G$ er da bare en $p$-gruppe hvis $|G| = p^i$, altså en potens av $p$. >La $H$ og $G$ være to grupper med $H \leq G$, og la $G_H = \{g \in G\>|\>gHg^{-1} = H\}$. $G_H$ er normalisatoren av $H$ i $G$. Vi skriver $G_H$ som $N[H]$.

__Lemma__

>La $H$ være en $p$-undergruppe av en endelig gruppe $G$. Da er $$ >$$ >(N[H]\>:\>H) \equiv (G\>:\>H)(\text{mod}\>p).>$$

__Korollar__

>La $H$ være en $p$-undergruppe av en endelig gruppe $G$. Hvis $p$ deler $(G\>:\>H)$, så er $N[H] \neq H$.

__Første Sylow Teorem__

>La $G$ være en endelig gruppe og la $G = p^n m$ hvor $n \geq 1$ og $p$ ikke deler $m$. Da har vi >1. $G$ inneholder en undergruppe av orden $p^i$ for alle $1 \leq i \leq n$,>2. Hver undergruppe $H$ av $G$ av orden $p^i$ er en _normal_ undergruppe av en undergruppe av orden $p^i$ for alle $1 \leq i \leq n$

En __Sylow__ $p$-__undergruppe__ av en gruppe $G$ er en maksimal $p$-undergruppe av $G$. __Andre Sylow Teorem__

>La $P_1$ og $P_2$ være Sylow $p$-undergrupper av en endelig gruppe $G$. Da er $P_1$ og $P_2$ konjugerte undergrupper av $G$

__Tredje Sylow Teorem__

>Hvis $G$ er en endelig gruppe og $p$ deler $|G|$, er antall Sylow $p$-undergrupper av $G$ kongruent til $1$ modulo $p$, og deler $|G|$.

(TODO: Eksempler) # Eulers phi-funksjon & RSA # Nyttige lenker [Relasjoner, matematikk.net](http://matematikk.net/side/Relasjoner) [Grupper, wolframalpha](http://mathworld.wolfram.com/Group.html) [Restklasser, UiO](http://www.uio.no/studier/emner/matnat/math/MAT2200/v13/restklasser.pdf) # Referanser [John B. Fraleigh, A First Course in Abstract Algebra]