Wikipendium

Share on Twitter Create compendium Add Language
Edit History
Tools
  • Edit
  • History
  • Share on Twitter

  • Add language

  • Create new compendium
Log in
Table of Contents
  1. Introduksjon
    1. Forord
    2. Mengde
      1. Delmengde
    3. Kartesisk produkt
    4. Noen viktige mengder
    5. Relasjoner
    6. Kardinalitet
    7. Surjektivitet
    8. Injektivitet
    9. Bijektivitet
    10. Ekvivalensrelasjoner
      1. Refleksiv
      2. Symmetrisk
      3. Transitiv
    11. Binære operasjoner
      1. Kommutativitet
      2. Assosiativitet
    12. Tabell-notasjon
    13. Isomorfier
  2. Grupper
    1. Abelske grupper
    2. Endelige grupper
    3. Undergrupper
    4. Sykliske grupper
      1. Divisjonsalgoritmen for grupper
  3. Permutasjonsgrupper
    1. Cayley's Teorem
    2. Orbitaler
      1. Disjunkte sykler
  4. Restklasser
  5. Lagranges Teorem
  6. Endelig-genererte abelske grupper
  7. Homomorphismer
  8. Faktorgrupper
  9. Gruppevirkninger
  10. Ringer
    1. Direkte produkt
    2. Homomorfier
      1. Evalueringshomomorfien
      2. Isomorfier
    3. Kommutative ringer, Divisjonsringer og Kropper
    4. Underring & Underkropp
    5. Integritetsdomene
  11. Eulers og fermats teoremer
    1. Fermats Lille Teorem
    2. Eulers Teorem
  12. Polynomer
    1. Ringer av polynomer
      1. To og flere ukjente
    2. Evalueringshomomorfien, part II
    3. Faktorisering av polynomer
    4. Irredusible polynomer
      1. Eisenstein-kriteriet
  13. Ringhomomorfier og faktorringer
    1. Ringhomomorfier
      1. Kjerne
    2. Faktorringer
      1. Idealer
      2. Fundamentalteoremet for homomorfier II
      3. Maksimale idealer
  14. Sylowteori
    1. Cauchy's Teorem
    2. Første Sylow Teorem
    3. Andre Sylow Teorem
    4. Tredje Sylow Teorem
  15. Eulers phi-funksjon & RSA
  16. Nyttige lenker
  17. Referanser
‹

TMA4150: Algebra og tallteori

Tags:
  • maths
+

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.

Mengden av alle delmengdene til en mengde $A$ kales for potensmengden til A, og skrives $\mathcal{P}(A)$.

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)\} $$

Noen viktige mengder

$\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.

En særdeles viktig mengde er mengden $\mathbb{Z}_n$, mengden av de $n$ første heltall (inklusiv 0). Vi vil ofte snakke om addisjon eller multiplikasjon modulo $n$ på denne mengden.

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 endelig mengde $A$ er antall elementer i $A$. Kardinaliteten $\lvert S \rvert$ til mengden $S = \{1,2,3\}$ er altså $3$.

Kardinaliteten til uendelige mengder er i all hovedsak utenfor pensum. Det kan dog være fornuftig å notere seg at kardinaliteten til $\mathbb{Z}$ er mindre enn kardinaliteten til $\mathbb{R}$. Uformelt kan vi si at uendeligheten av tall i $\mathbb{R}$ er større enn den i $\mathbb{Z}$.

Kardinaliteten til $\mathbb{Z}$, $\lvert \mathbb{Z} \rvert$ betegnes ved symbolet $\aleph_0$ (uttales aleph-naught eller aleph-zero). Noe som kanskje overrasker, er at kardinaliteten til $\mathbb{N}, \mathbb{Z}$ og $\mathbb{Q}$ er den samme.

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$.

To kjappe eksempeler fra kalkulus

La $ f : [-2, 2] \to [0, 4]$ være gitt ved $f(x) = x^2$. Vi ser at at $f$ er surjektiv, siden $f(0) = 0$ og $f(2) = 4$ og $f$ er kontinuerlig(!!).

La $ g : [0, \infty) \to [0, \pi /2]$ være gitt ved $g(x) = \arctan(x)$. $g$ er ikke surjektiv, siden det ikke finnes en $x$ s.a. $g(x) = \pi/2 \in Y$. Er $g$ surjektiv fra $[0, \infty)$ på $[0, \pi /2)$?

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$.

To kjappe eksempler

La $ f : [-2, 2] \to [0, 4]$ være gitt ved $f(x) = x^2$. $f$ er ikke injektiv, siden $\forall x \in [-2, 2], -x \in [-2, 2], f(x) \in [0, 4]$ og $f(x) = f(-x)$.

La $ g: \{a, b, c, d, e\} \to \{aa, ab, ac, ad, ae, af, ba, bb \dots \}$ være gitt ved $g(x) = ax$ ($g(a) = aa$ osv.). $g$ er injektiv siden $f[X] = \{aa, ab, ac, ad, ae\}$, og om vi lar $g^{-1}(x) = g^{-1}(ax') = x'$, hvor $x' \in \{a, b, c, d, e\}$.

Bijektivitet

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

Om en funksjon er surjektiv og strengt voksende på en ordnet mengde (dvs. vi har en tilhørende relasjon $>$ som bestemmer "størrelsen på elementene), er funksjonen bijektiv.

La $f : R \to R$ være gitt ved $f(x) = x$.

La $g : [0, \infty) \to [0, \infty]$ være gitt ved $g(x) = x^n, n \in (0, \infty)$. Er $g$ injektiv? (Hint: Bruk at $f$ er strengt voksende, $f(0)$, $\lim_{x \to \infty}$ og kontinuitet)

Om du ønsker, prøv til slutt å finne en bijeksjon mellom $\mathbb{Z}$ og $\mathbb{Q}$. Hint: Det kan være lurt å tegne.

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?

Eksempel

Vis at $\mathbb{Z}_n$ under addisjon modulo $n$ er en gruppe.

For en $a \in \mathbb{Z}$, er addisjon modulo $n$ definert som resten av $a/n$. Ta for eksempel $a = 9$ og $n = 5$, i $\mathbb{Z}_5$ er $a$ resten av $9/5$, som er $4$. En kjapp teknikk for å regne ut dette er å trekke fra $a$ den høyeste multippel av $n$ som er mindre enn $a$. En annen definisjon ( som er bedre siden den ikke er avhengig av at deling og rest er definert) er at addisjon modulo $n$ er vanlig addisjon helt til du når et tall $n$, hvor du "starter på nytt". Et typisk eksempel er klokken, som opererer med addisjon modulo $12$.

La oss først verifisere at $\mathbb{Z}_n$ er lukket under addisjon modulo $n$. Dette gjør vi ved å vise at addisjon modulo $n$ er veldefinert.

La $a,b,c \in \mathbb{Z}_N$.

Først må vi vise at operasjonen $+$ på to elementer $a, b$, gir et nytt element i $\mathbb{Z}_n$. Dette faller ut av definisjonen til addisjon på $\mathbb{Z}$. Videre er $+$ åpenlyst definert for alle elementer i $\mathbb{Z}_n$. Vi har også at hvis $a + b = a + c$, så er $b = c$.

La oss så sjekke gruppeaksiomene:

  1. $(a + b) + c = a + (b + c)$, dette faller rett ut av assossiativiteten til addisjon
  2. $0$ er identitetselement
  3. For enhver $a \in \mathbb{Z}_n$ finnes det en $a' \in \mathbb{Z}_n$ slik at $a a' = 0$, definert ved $a + a' = n$ i $\mathbb{Z}$.

$\mathbb{Z}_n$ er dermed en gruppe.

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, 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

La $H$ være en mengde, og la $G$ være en gruppe med binær operasjon $*$. $H$ er en undergruppe av $G$, skrevet $H \leq G$, hvis $H$ er en delmengde av $G$, og $*$ er lukket under $H$.

Hvis $H = G$, er $H$ den uekte undergruppen av $G$. Gruppen $\{e\}$ er den trivielle undergruppen.

Eksempelvis er $3Z$, gruppen av alle heltall delbar med $3$, i.e. $\{\dots -3, 0,3,6,\dots\}$, en undergruppe av $Z$ under addisjon, siden $3Z$ er lukket under addisjon.

Vi har generelt tre krav som må tilfredstilles for at en gruppe $H$ skal være en undergruppe av en gruppe $G$:

En gruppe $H$ er en undergruppe av en gruppe $G$ hvis og bare hvis 1. $H$ er lukket under den binære operasjonen til $G$ 2. Identitetselementet til $G$ er også i $H$ 3. For alle $a \in H$, er også $a^{-1} \in H$

Eksempel

La $G = \mathbb{Z}_4$ under addisjon modulo $4$. Altså $\{0,1,2,3\}$. Og la $H = \{0, 2\}$. Er $H$ en undergruppe av $G$?

Vi sjekker enkelt og greit kravene våre. Her kan vi sjekke alle kravene ved å teste alle elementer om vi vil.

  1. Dette må åpenlyst være tilfelle. Men la oss verifisere det for å være på den sikre siden: $0 + 2 = 2,\> 2 + 0 = 2,\> 2 + 2 = 4 \equiv 0,\> 0 + 0 = 0$.
  2. Identitetselementet til $G$ er $0$, som også er i $H$.
  3. Vi har bare ett element ikke lik $0$ i $H$, nemlig $2$, som har invers $2$.

$H$ er dermed en undergruppe av $G$.

Sykliske grupper

La oss slenge ut en påstand:

En endelig gruppe $G$ som inneholder et element $a$, må også inneholde alle $a^n,\>n \in \mathbb{Z}$.

Dette kan vi bevise ganske enkelt ved induksjon (her gjort litt uformelt):

Hvis $a$ er i $G$, må $a * a = a^2 \in G$, siden $G$ må være lukket under $*$. Tilsvarende, hvis $a^i \in G$, må $a^{i+1} \in G$.

Det burde nå være enkelt å overbevise seg over følgende:

For en gruppe $G$ og et element $a \in G$, er undergruppen $H$ av G, definert ved

$$ H = \{a^n\:|\:n \in \mathbb{Z} \} $$

den minste undergruppen som inneholder $a$.

Gruppen $H$ over er den sykliske undergruppen av $G$ generert av $a$, og skrives $\left<a\right>$, Hvis $a$ genererer $G$, er $a$ en generator av $G$.

Hvis en gruppe $G$ har en generator er $G$ syklisk.

Eksempel

Er $\mathbb{Z}_{3}$ syklisk? Hvis ja, finn en generator.

$\mathbb{Z}_3$ er syklisk. Vi ser at både $\left<2\right> = \{2, 4, 6\} = \{2, 1, 0\}$ og $\left<1\right> = \{1, 2, 0\}$ er generatorer.

Ordenen til et element $a$ i en gruppe $G$, er ordenen til den sykliske gruppen $\left<a\right>$ generert av $a$. Hvis denne er uendelig, sier vi at $a$ er av uendelig orden.

Hver sykliske gruppe er abelsk

Bevis

La $G$ være gruppen generert av $a$, og la $b,c \in G$. Da har vi at $b = a^m, c = a^n$ for $n, m \in \mathbb{Z}$. Det gir

$$ bc = a^m a^n = a^{m+n} = a^{n+m} = a^n a^m = cb. $$

Merk at $a^{m+n} = a^{n+m}$ siden $\mathbb{Z}$ er abelsk.

Samme bevis med annen notasjon

La $a, b, c$ som over. Da er

$$ bc = \underbrace{aaa \ldots a}_\text{n} \underbrace{aaa \ldots a}_\text{m} = \underbrace{aaa \ldots a}_\text{m} + \underbrace{aaa \ldots a}_\text{n} = cb $$

Divisjonsalgoritmen for grupper

La $m$ være et positivt heltall, og la $n$ være et gitt heltall. Da finnes det heltall $q, r$ slik at

$$ n = mq + r,\quad 0 \leq r \le m $$

Det blir ikke gitt noe bevis for dette her. Rent intuivt kan kanskje se at dette må være tilfelle, siden et hvert heltall kan skrives som en multippel av et annet heltall, pluss en rest.

Eksempel

La $n = 5$ og $m = 3$, finn $q$ og $r$.

$$ n = m\cdot q + r $$

Vi vet at $r$ er positiv og mindre enn $m$. Vi ser dermed at $m$ ikke kan være større enn $1$, vi ser faktisk at den må være $1$. Dermed er $r = 2$, og vi har

$$ 5 = 1\cdot 3 + 2 $$

Dette virker knapt overraskende. Men vi skal nå bruke dette teoremet til noe litt viktigere.

En undergruppe av en syklisk gruppe er selv syklisk

Bevis

La $G$ være en syklisk gruppe med generator $a$, og la $H$ være en undergruppe av $G$. Hvis $H = \{e\}$ er vi ferdige. Hvis ikke, la $m$ være det minste positive heltallet slik at $a^m \in H$.

La $a^m = c \in H$. Vi påstår at $c$ genererer $H$, altså $\left<c\right> = H$. Det må bety at hver $b \in H$ må være en potens av c (kravet for at H skal være syklisk).

Så la oss skrive $b = a^n$. La oss nå bruke divisjonsalgoritmen og skrive $$n = mq + r,$$ slik at $$ a^n = a^{mq + r} \ \implies a^r = a^n a^{-mq} $$

Siden $a^{-mq}, a^n \in H$ er $a^r \in H$. Men dette kan ikke være mulig med mindre $r = 0$, siden vi har av divisjonsalgoritmen at $r < m$, og siden vi valgte $m$ til å være den minste positive potensen $a^m \in H$. Dermed er $r = 0$, og $$ a^n = a^{mq} \implies b = c^q $$

Alle gruppene $n \mathbb{Z}$ hvor $n \in \mathbb{Z}$, er sykliske undergrupper av $\mathbb{Z}$, siden $\mathbb{Z}$ selv er syklisk, med generatorer $1$ og $-1$

La $G$ være en syklisk gruppe av uendelig orden. Da er $G$ isomorf til $\left<\mathbb{Z}, +\right>$.

Permutasjonsgrupper

De fleste har kanskje en ide om hva en permutasjon er. For en mengde kan man anse det som en omstokking av elementene. La oss ta mengden $\{1,2,3,4\}$. En permutasjon av denne mengden kan være $\{3,4,2,1\}$. Vi skal håndtere permutasjonsgrupper, endelige grupper som omstokker på endelige mengder.

En permutasjon av en mengde $M$ er en funksjon $\phi\: :\: M \rightarrow M$ som er bijektiv (altså en-til-en.)

Permutasjon er en binær operasjon.

Eksempel

Ta utgangspunkt i permutasjonen

$$ 1 \rightarrow 2 \\ 2 \rightarrow 3 \\ 3 \rightarrow 5 \\ 4 \rightarrow 4 \\ 5 \rightarrow 1 $$

og kall denne $\tau$. La $S = \{1,2,3,4,5\}$. Regn ut $\tau(S)$ og $\tau^2(S)$.

Vi regner ut ved å bytte om elementene som indikert:

$$ \tau(S) = \{2, 3, 5, 4, 1\} $$

$$ \tau^2(S) = \tau(\tau(S)) = \tau(\{2,3,5,4,1\}) = \{3, 5, 1, 4, 2\} $$

Eksempel

La S og $\tau$ være som over, og la $\sigma$ være

$$ 1 \rightarrow 5 \\ 2 \rightarrow 2 \\ 3 \rightarrow 3 \\ 4 \rightarrow 4 \\ 5 \rightarrow 1 $$

Regn ut $\tau(\sigma(S))$ og $\sigma(\tau(S))$. Kan du si noe om kommutativiten til $\tau$ og $\sigma$?

$$ \sigma(S) = \{5,2,3,4,1\} \\ \tau(S) = \{2, 3, 5, 4, 1\} \\ \tau(\sigma(S)) = \tau(\{5,2,3,4,1\}) = \{1,3,5,4,2\} \\ \sigma(\tau(S)) = \sigma(\{2,3,5,4,1\}) = \{2,3,1,4,5\} $$

Vi merker oss at resultatene ikke er kommuterer, og at gruppen av permutasjoner dermed ikke kan være abelsk.

Merk også at vi regner ut fra høyre til venstre.

Siden notasjonen brukt i eksemplene ovenfor kan være litt slitsom og klumpete, bruker vi ofte notasjonen

$$ \tau = \left(\begin{array}{ccccc} 1, 2, 3, 4, 5 \\ 5, 4, 3, 2, 1 \end{array}\right) $$

for permutasjoner. Her indikerer hvert vertikalt par en avbildning.

La $A$ være en endelig gruppe med $n$ elementer $\{1,2,3,\dots,n\}$. Gruppen av alle permutasjoner på $A$, er den symmetriske gruppen på n bokstaver, $S_n$.

Merk at vi har $n!$ permutasjoner på $A$, så $S_n$ har $n!$ elementer.

Denne gruppen er essensielt alle permutasjoner en kan gjøre på en regulær $n$-kant. $D_3$ er eksempelvis gruppen av alle permutasjoner på den regulære (likevinklede) trekant. (s. 79 i boken for den interesserte).

Cayley's Teorem

Enhver gruppe er isomorf til en gruppe av permutasjoner.

Alternativt kan man si at en enhver gruppe er isomorf til en delgruppe av $S_n$.

Orbitaler

La oss se på permutasjonen

$$ \sigma = \left(\begin{array}{ccccc} 1, 2, 3, 4, 5 \\ 1, 4, 3, 2, 5 \end{array}\right). $$

Vi ser at permutasjonen bytter om $2$ og $4$, og at en kontinuerlig applikasjon av $\sigma$ vil fortsette å bytte $2$ i $4$ og $4$ i $2$. Mengden av $\{2,4 \}$ i $\sigma$ er en orbital.

Orbitaler kan defineres ved en ekvivalensrelasjon:

La $\sigma$ være en permutasjon av en mengde $A$. La så $a, b \in A$, og la $~$ være en relasjon definert ved $a~b$ hvis og bare hvis $b = \sigma^n(a)$ for en $n\in \mathbb{Z}$.

Merk analogien til sykliske grupper.

Eksempel

Finn alle orbitaler i permutasjonen

$$ \sigma = \left(\begin{array}{cccccccc} 1, 2, 3, 4, 5, 6, 7, 8 \\ 1, 3, 4, 2, 5, 7, 8, 6 \\ \end{array}\right). $$

Vi ser på hvert element. Til å begynne med er $\{1\}$ en ett-elements orbital. For $2$ har vi $2 \xrightarrow{\sigma} 3 \xrightarrow{\sigma} 4 \xrightarrow{\sigma} 2 \dots$, så vår neste orbital er $\{2,3,4\}$. $\{5\}$ er en ett-elements orbital. Til slutt har vi orbitalen $\{6,7,8\}$.

En orbital med to elementer kalles en transposisjon.

En permutasjon $\tau$ er en sykel hvis den har maksimalt en orbital med mer enn ett element.

Vi bruker ofte en en-rads notasjon for sykler

$$ \tau = (1,2,4) $$

Her tar permutasjonen $1$ til $2$, $2$ til $3$, og $4$ til $1$. Det må gjøres klart ved bruk av denne notasjonen hvilken mengde det er snakk om. Merk også at alle andre elementer ikke nevnt i notasjonen antas å permutere til seg selv.

Permutasjonen

$$ \sigma = \left(\begin{array}{ccccc} 1, 2, 3, 4, 5 \\ 1, 4, 3, 2, 5 \end{array}\right) = (2, 4), $$

er eksempelvis en sykel. Mens

$$ \tau = \left(\begin{array}{ccccc} 1, 2, 3, 4, 5 \\ 1, 4, 5, 2, 3 \end{array}\right), $$

er ikke en sykel, siden den inneholder to orbitaler med to elementer: $\{2, 4\}$ og $\{3, 5\}$.

Disjunkte sykler

To sykler er disjunkte hvis de ikke inneholder samme element

For eksempel er $\tau = (1,2,3)$, og $\sigma = (4,5,6)$ disjunkte.

Enhver permutasjon kan skrives som et produkt av disjunkte sykler.

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 den additive operasjonen og den multiplikative operasjonen til R.

Mer om dette under Ringhomomorfier.

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.

Isomorfier

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$.

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.

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.

En hver kropp $F$ er et integritetsdomene.

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 kropp, 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:

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.

Hvis $a$ er et heltall relativt primisk til $n$, er $a^{\phi(n)} - 1$ delbart med $n$, altså er

$$ a^{\phi(n)} = 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+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, og definere den for 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}$.

  1. Beskriv $N = \text{Ker}(\phi_2)$.
  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

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}$.

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]$.

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 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 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.

Idealer

I gruppeteori, definerte vi 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, 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}$. Et ekte ikke-trivielt ideal av en ring $R$, er er ideal $N$, slik at $N \neq R$ og $N \neq {0}$.

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$.

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 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 en $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
  • Grupper, wolframalpha
  • Restklasser, UiO

Referanser

[John B. Fraleigh, A First Course in Abstract Algebra]

Written by

Stian Jensen sigveseb trmd
Last updated: Mon, 14 Dec 2015 10:20:08 +0100 .
  • Contact
  • Twitter
  • Statistics
  • Report a bug
  • Wikipendium cc-by-sa
Wikipendium is ad-free and costs nothing to use. Please help keep Wikipendium alive by donating today!