Tal- og gruppeteori

Jesper M. Møller

Author address: Matematisk Institut, Universitetsparken 5, 2100 København Ø

E-mail address: moller@math.ku.dk

Resume. Noter til brug ved undervisningen i Mat 1 (algebra). I stikordsform er indholdet: Induktionsaksiomet, Divisionsalgoritmen, største fælles divisor og mindste fælles multiplum, Euklids Algoritme, primtal, entydighed af primtalsfaktorisering, grupper, Cayley tabel, undergrupper, gruppehomomorfier, kernen for en gruppehomomorfi, Lagranges Sætning, aritmetik modulo n, Eulers Sætning, Fermats lille sætning, Den kinesiske Restklassesætning.

Disse noter ligger på kursets hjemmeside.

Indhold

Kapitel 1. Talteori 5 1. Induktion 5 2. Divisionsalgoritmen 7 3. Primtal 16

Kapitel 2. Gruppeteori 23 1. Funktioner 23 2. Transformationer af planen 24 3. Kvadratets symmetrigruppe 25 4. Grupper 26 5. Undergrupper og gruppehomomorfier 28 6. Modulær aritmetik 33 7. Den kinesiske restklassesætning 38

Litteratur 47

4 INDHOLD

KAPITEL 1 Talteori

1. Induktion

Alle kender de naturlige tal

ℕ = {1, 2, 3, … }

og de hele tal

ℤ = {…, −3, −2, −1, 0, 1, 2, 3, … }

så de behøver ingen yderligere introduktion.

De naturlige tal opfylder

Induktionsaksiomet 1.1. Lad S ⊆ ℕ være en delmængde af de naturlige tal som opfylder følgende to egenskaber:

1. 1 ∈ S.

2. For alle n ∈ ℕ gælder at hvis n ∈ S, så er n + 1 ∈ S. Da er S = ℕ.

Induktionaksiomet optræder i mange forskellige varianter og forklædninger. Her er en af dem:

Induktionsaksiomet 1.2. Lad, for hvert naturligt tal n, P (n) være en påstand, som afhænger af n. Antag, at

1. P (1) er sand, og

2. P (n) medfører P (n + 1) for ethvert naturligt tal n, da er P (n) sand for alle naturlige tal n.

De to versioner af induktionsaksiomet er ækvivalente. Forbindelsen mellem dem ses ved at sætte S = {n ∈ ℕ | P (n) er sand} til at være mængden af de natrurlige tal for hvilke P (n) er sand.

Her kommer et eksempel på en typisk anvendelse af Induktionsaksiomet.

Eksempel 1.3. Vi ønsker at vise, at

1 + 2 + ⋯ + n = \frac{n(n + 1)}{2}  (1.4)

for alle naturlige tal n ≥ 1.

Lad P (n) betegne den påstand at formlen (1.4) holder for det naturlige tal n. Læg mærke til:

(I1): P (1) er sand fordi 1 = \frac{1·2}{2}. (I2): Antag at P (n) er sand. Vi har da

1 + 2 + ⋯ + n + (n + 1) = \frac{n(n + 1)}{2} + (n + 1)

= (n + 1)(\frac{n}{2} + 1)

= \frac{(n + 1)(n + 2)}{2}

hvilket viser at P (n + 1) er sand. Ifølge Induktionsaksiomet (1.2) kan vi nu slutte at P (n) er sand for alle n ≥ 1.

Du kan selv øve dig ved at tænke over:

Øvelse 1.5. Vis, at

1 + 3 + ⋯ + (2n − 1) = n^{2}

for alle naturlige tal n ∈ ℕ.

Nu, hvor jeg er kommet op i fart, snupper vi lige endnu en variant:

Induktionsaksiomet 1.6. Lad, for hvert naturligt tal n, P (n) være en påstand, som afhænger af n. Antag, at

1. P (1) er sand, og

2. sandheden af P (i) for alle i ≤ k medfører sandheden af P (k+1) for ethvert

naturligt tal k, da er P (n) sand for alle naturlige tal n.

Overvej selv, hvorfor denne tilsyneladende stærkere antagelse alligevel ikke får den store indflydelse. (Hvis nu P (n) er som ovenfor, indfør en ny påstand Q(n) som siger, at P (i) er sand for alle i ≤ n. Brug nu den første variant.)

Til slut skal vi se på endnu en variant, som er lidt mindre gennemskuelig. Vi indfører først det meget naturlige begreb et mindste element.

Definition 1.7. Lad S ⊆ ℕ være en delmængde af de naturlige tal. Vi siger, at det naturlige tal m er det mindste element i S, hvis

1. m ligger i S, og

2. m ≤ s for ethvert s ∈ S. Det vil sige, at s er det mindste element i S, hvis s er i S og s er mindre end eller lig med alle elementer i S.

Vi skriver min S for det mindste element i S; f.eks. er

min{n ∈ ℕ | n^{2} ≥ 4} = 2

(Faktisk har jeg snydt en lille smule ved allerede at tale om det mindste element; kunne der ikke tænkes at findes en delmængde af de naturlige tal med to mindste elementer?)

Kan du komme i tanke om en eneste delmængde, bortset fra den tomme mængde, af de naturlige tal som ikke har et mindste element? Er det sådan, at alle delmængder af ℕ har et mindste element? Kan du bevise det? (Vendingen “Så må der da for F..... være” er blasfemisk og derfor ikke tilladt.)

Sætning 1.8. (Princippet om det mindste element) Enhver delmængde S ⊆ ℕ af de naturlige tal, som ikke er tom, har netop et mindste element.

Bevis. For ethvert naturligt tal n, lad P (n) være påstanden

P (n): Alle delmængder S ⊆ ℕ, som indeholder mindst et af tallene 1, …, n,

har et mindste element.

Vi bruger Induktionsaksiomet til at vise, at P (n) er sand for alle n. Påstanden P (1) er sand, for hvis 1 ∈ S, da er 1 det mindste element for S. Lad os nu antage, at P (n) er sand for et n ∈ ℕ. Vi vil vise, at så er også P (n + 1) sand. Lad derfor S være en mængde af naturlige tal, så S ∩ {1, 2, …, n + 1} ≠ ∅. Hvis så også, S ∩ {1, 2, …, n} ≠ ∅, da har S et mindste element ifølge induktionsantagelsen P (n); men hvis S ∩ {1, 2, …, n} = ∅, da er n + 1 et mindste element for S.

Til sidst, lad S være en vilkårlig, ikke-tom mængde af naturlige tal. Da S ikke er tom, indeholder den et element, s. Så er S ∩ {1, 2, …, s} ≠ ∅, og alle delmængder med denne egenskab har et mindste element, da P (s) er sand.

Vi har altså set, at

Induktionsaksiomet ⇒ Princippet om det mindste element.

Den modsatte implikation gælder også; de to er ækvivalente.

Øvelse 1.9. Vis den modsatte implikation. (Vink: Antag Princippet om det mindste element. Lad P (n) være en påstand, der afhænger af det naturlige tal n og opfylder de to krav i Induktionsaksiomet. Sæt S til at være {n ∈ ℕ | P (n) er falsk}. Har S et mindste element?)

Garvede matematikere vil sige at Princippet om det mindste element siger, at ℕ er velordnet. Læg mærke til, at Princippet om det mindste element ikke gælder for de reelle tal ℝ.

Øvelse 1.10. Hvis ∅ ≠ A ⊆ B ⊆ ℕ, så er min A ≥ min B.

2. Divisionsalgoritmen

I dette afsnit udnytter vi Princippet om det mindste element til at bevise Divisionsalgoritmen.

Først vil det være bekvemt at indføre betegnelsen

ℕ_{0} = {0} ∪ ℕ = {0, 1, 2, 3, … }

for mængden af de naturlige tal og 0.

Dividerer vi 11 med 4, så vil vi se, at 4 går op 2 gange i 11 og resten er 3. Eller, som de udtrykker det i tredje klasse:

11 = 4 · 2 + 3

Dette illustrerer det næste resultat:

Sætning 2.1. (Divisionsalgoritmen.) Lad a ∈ ℤ være et helt tal og b ∈ ℕ et naturligt tal (så b ≠ 0). Der findes da entydigt bestemte hele tal q og r så

a = bq + r

hvor 0 ≤ r < b. (q kaldes kvotienten, r resten.)

Hvis a = 11 og b = 4, da er kvotienten q = 2 og resten er r = 3. Sætningen tillader også division op i negative tal; dividerer vi a = −11 med b = 4 får vi kvotienten q = −3 og resten r = 1 fordi −11 = 4 · (−3) + 1 hvor jo 0 ≤ 1 < 4. Sætningen siger derimod ikke noget om division med negative tal, tallet b, det vi dividerer med, er altid positivt; resten r er også altid positiv eller 0.

Øvelse 2.2. Lad a og b være positive, hele tal. Antag, at a = bq + r med 0 ≤ r < b. Hvad giver Divisionsalgoritmen, når vi dividerer a med −b?

Din erfaring (empirien) siger dig, at man med et givent input, a og b, altid kan finde q og r som påstået i Divisionsalgoritmen. Men er din empiriske erfaring dermed en universel sandhed? NIX! Vi er nødt til at give et

Bevis. Denne sætning er et eksempel på en eksistens- og entydighedssætning. Beviset falder derfor i to dele. Den ene del argumenterer for eksistensen, den anden for entydigheden.

Eksistens: Lad S være mængden af alle hele tal som

• er ≥ 0

• kan skrives på formen a − bq for et q ∈ ℤ. Dvs, at

S = {a − bq | q ∈ ℕ} ∩ ℕ_{0}

Efter et øjebliks overvejelse indser du, at denne mængde af hele tal ikke er tom. Ifølge Princippet om det mindste element findes der derfor et mindste element i S. (Snydes der her?) Lad os kalde det mindste element for r:

r = min S

Så er r ≥ 0. Påstanden i sætningen er, at også r < b. Lad os prøve at antage, at r ≥ b. Da er r − b ≥ 0 og

r − b = (a − bq) − b = a − b(q + 1)

så r − b er et tal i S, som er mindre end r. Det strider mod, at r er det mindste element i S. Da antagelsen fører os lige lukt i en modstrid, kan den ikke opretholdes. Vi må altså have r < b.

Entydighed: Lad

a = bq_{1} + r_{1}, 0 ≤ r_{1} < b,
a = bq_{2} + r_{2}, 0 ≤ r_{2} < b,

være to fremstillinger af a. Vi skal vise, at q_{1} = q_{2} og r_{1} = r_{2}.

r_{1} − r_{2} = −b(q_{1} − q_{2})

ligger i b-tabellen og opfylder

−b < r_{1} − r_{2} < b

fordi begge tal ligger mellem 0 og b. Hvor mange tal fra b-tabellen ligger der mellem −b og b ( endepunkterne fraregnet)?

Hvis resten r er 0 siger vi at b går op i a. Vi kan definere dette begreb for vilkårlige to hele tal.

Definition 2.3. Lad a ∈ ℤ og b ∈ ℤ være to hele tal. Vi siger, at b går op i a, at b er en divisor i a, at a er et multiplum af b, eller at a er delelig med b, og vi skriver b|a, hvis der findes et helt tal q ∈ ℤ så a = bq.

Alle hele tal er divisorer i 0, går op i 0. Alle andre hele tal har kun endelig mange divisorer.

Bemærkning 2.4. Tallet b går op i tallet a, netop når a ligger i b-tabellen, eller netop når b-tabellen indeholder i a-tabellen. Da b-tabellen er mængden bℤ = {aq | q ∈ ℤ}, og a-tabellen er aℤ, kan vi skrive:

b|a ⇔ bℤ ⊇ aℤ.

Der gælder følgende regneregler, hvis verifikation jeg overlader til dig.

Sætning 2.5. Lad a og b være to hele tal.

1. a|b ⇒ a|bc for ethvert helt tal c.

2. ac|bc ⇔ a|b for ethvert helt tal c ≠ 0. (Forkortningsreglen.)

3. Hvis a|b og b|c, så vil a|c.

4. Hvis a|b og a|c, så vil a|(xb + yc) for alle x, y ∈ ℤ.

5. Hvis a|b og b|a, så er a = ±b.

6. a|0.

7. ±1|a.

8. Hvis a|b og b ≠ 0, så er |a| ≤ |b|.

Øvelse 2.6. Vi betragter her kun naturlige tal. Lad os skrive a ≤ b når vi mener a|b. (Det bringer forvirringen op på et højere niveau.) Omskriv (de relevante dele af) Sætning (2.5) med dette symbol. Find det “største” tal, som er “≤” både 12 og 18. Find det “mindste” tal, som er “≥” både 12 og 18. Kender du et andet navn for disse tal? (Eleverne i folkeskolen gør!)

2.7. Mindste fælles multiplum. Lad a ∈ ℤ og b ∈ ℤ være hele tal. I dette delafsnit vil vi antage, at hverken a eller b er 0. (Det er ikke en strengt nødvendig antagelse. Overvej, hvad der sker hvis enten a eller b er 0.)

Definition 2.8. Et fælles multiplum af a og b er et helt tal m, som er både a-tabellen og i b-tabellen.

Da a-tabellen netop er aℤ, og b-tabellen bℤ er fællesmængden

aℤ ∩ bℤ

netop mængden af fælles multipla. Produktet ab er et fælles multiplum. Der er undeligt mange fælles multipla, f.eks. alle tal i ab-tabellen ℤab.

Eksempel 2.9. Et fælles multiplum af a = 63 og b = 105 er ab = 6615, men også 5 · 63 = 315 = 3 · 105 er et fælles multiplum.

Et særligt interessant fælles multiplum, 315 i eksemplet, er det mindste fælles multiplum, der defineres sådan her:

Definition 2.10. Det hele tal m er et mindste fælles multiplum af a og b, hvis

• m er positiv

• m er et fælles multiplum af a og b

• m går op i ethvert fælles multiplum

Vi konfronterer nu eksistens- og entydighedsproblemet for mindste fælles multiplum.

Lemma 2.11 (Entydighed). Der findes højst et mindste fælles multiplum af a og b.

Bevis. Antag, at både m_{1} og m_{2} er fælles multipla. Da m_{2} er et fælles multiplum og m_{1} et mindste fælles multiplum, vil m_{1} gå op i m_{2}. Da m_{1} er et fælles multiplum og m_{2} et mindste fælles multiplum, vil m_{2} gå op i m_{1}. Derfor er m_{1} = m_{2}.

Lemma 2.12 (Eksistens). Lad m være det mindste positive tal, som står både i a-tabellen og i b-tabellen. Da er m et mindste fælles multiplum af a og b.

Bevis. Påstanden er, at

m = min((aℤ ∩ bℤ) ∩ ℕ)

er et mindste fælles multiplum af a og b – altså at m opfylder de tre krav fra Definition 2.10. (Naturligvis har du allerede lynhurtigt overvejet, at mængden aℤ∩bℤ∩ℕ af positive tal, der står i både a-tabellen og i b-tabellen, ikke er tom.)

Det er klart, at m > 0 (for m ∈ ℕ), og at m er et fælles multiplum, for aℤ ∩ bℤ er jo simpelthen mængde af fælles multipla. Lad M være et (andet) fælles multiplum. Jeg påstår, at m går op i M. Ifølge Divisionsalgoritmen (2.1) kan M skrives på formen M = qm + r, hvor q ∈ ℤ og 0 ≤ r < m. Vi kan ikke have 0 < r < m, for da ville r = M − qm være et positivt fælles multiplum, som var mindre end det mindste, m. Altså er r = 0, og m | M. Dette viser, at m er et mindste fælles multiplum.

Vi ved nu, at der altid findes netop et mindste fælles multiplum af a og b. Vi betegner det med mfm(a, b).

Vi samler nu vores erfaring, og lidt til, i en sætningen om eksistens- og entydighed af mindste fælles multiplum.

Sætning 2.13 (Eksistens og entydighed af mindste fælles multiplum). Lad a ≠ 0 og b ≠ 0 være to hele tal. Så gælder:

1. Der findes netop et mindste fælles multiplum, mfm(a, b), af a og b.

2. mfm(a, b) = min(aℤ ∩ bℤ ∩ ℕ).

3. mfm(a, b)ℤ = aℤ ∩ bℤ.

Bevis. Kun punkt (3) kræver en bemærkning: Da mfm(a, b) er et fælles multiplum, er mfm(a, b)ℤ ⊆ aℤ∩bℤ. Da ethvert fælles multiplum er et multiplum af mfm(a, b) er aℤ ∩ bℤ ⊆ mfm(a, b)ℤ.

Eksempel 2.14. mfm(12, 18) = min(12ℤ∩18ℤ∩ℕ) = min{36, 72, … } = 36.

Øvelse 2.15. Lad m være et naturligt tal, sådan et mℤ = aℤ ∩ bℤ. Vis, at m = mfm(a, b).

Øvelse 2.16. Vis, at m er det mindste fælles multiplum af a og b hvis og kun hvis

• m er positiv

• m er et fælles multiplum af a og b

• m er mindre end eller lig med ethvert positivt fælles multiplum af a og b Du skal altså vise, at den mindste af de positive fælles divisor er den mindste fælles divisor!

I næste afsnit kan du finde en algoritme til beregning af mfm(a, b).

2.17. Største fælles divisor. Lad a ∈ ℤ og b ∈ ℤ være to hele tal. I dette delafsnit vil vi antage, at ikke både a og b er 0. (Det er ikke en strengt nødvendig antagelse. Overvej, hvad der sker hvis både a og b er 0.)

Definition 2.18. En fælles divisor for a og b er et helt tal, m, som går op i både a og b (både a og b er i m-tabellen).

Ethvert helt tal forskellig fra 0 har kun endeligt mange divisorer. (For hvis m|a, hvor a ≠ 0, så er |m| ≤ |a|.) Der findes derfor kun endeligt mange fælles divisorer for a og b.

Eksempel 2.19. De fælles positive divisorer for a = 12 og b = 18 er 1, 2, 3, 6. De fælles positive divisorer for a = 30 og b = 42 er også 1, 2, 3, 6.

Vi kan også karakterisere de fælles divisorer på denne (mere gennemskuelige?) måde:

m er en fælles divisor for a og b

⇔ℤm ⊇ ℤa og ℤm ⊇ ℤb
⇔ℤm ⊇ ℤa ∪ ℤb
⇔ℤm ⊇ ℤa + ℤb

Her benytter jeg benytter skrivemåden

ℤa + ℤb = {sa + tb | s ∈ ℤ, t ∈ ℤ}

for mængde af alle hele tal, der kan skrives som en sum af et tal fra a-tabellen og et tal fra b-tabellen. Vi har

ℤa + ℤb ⊇ ℤa ∪ ℤb

så den sidste biimplikationspil er OK i den ene retning. Den anden retning kræver en lille overvejelse.

Hvis D(a) står for mængden af divisorer i a, så er fællesmængden D(a)∩D(b) netop mængden af fælles divisorer for a og b.

Vi skal nu se på en algoritme, Euklids algoritme, til bestemmelse af de fælles divisorer.

Lad os sige, vi ønsker at bestemmme de fælles divisorer for a_{0} of a_{1}. Vi antager, at a_{0} ≥ a_{1} > 0. Divider nu a_{0} med a_{1} og kald resten a_{2}:

a_{0} = q_{1}a_{1} + a_{2}, a_{1} > a_{2} ≥ 0.

Hvis a_{2} = 0 stopper algoritmen her. Men hvis a_{2} > 0, dividerer vi a_{1} med a_{2}, og kalder resten a_{3}. Hvis a_{3} = 0 stopper algoritmen her. Men hvis a_{3} > 0 …

Generelt, kan vi sige at output fra Euklids algoritme er en dalende følge af hele tal

a_{0} > a_{1} > ⋯ > a_{i−1} > a_{i} > a_{i+1} > ⋯ ≥ 0

hvor a_{i+1} er den rest der opstår når vi dividerer a_{i−1} med a_{i},

a_{i−1} = q_{i}a_{i} + a_{i+1}, a_{i} > a_{i+1} ≥ 0,  (2.1)

hvis ellers a_{i} > 0. Algoritmen stopper, hvis a_{i} = 0. Læg mærke til, at algortimen må stoppe efter endelig mange skridt, da der kun findes endeligt mange tal mellem a_{0} og 0. Lad os sige, at a_{n} > 0, men at a_{n+1} = 0. Overvej nøje, at ligningen (2.1), som definerer Euklids algoritme, viser (og det fortjener et lille argument!), at

D(a_{i−1}) ∩ D(a_{i}) = D(a_{i}) ∩ D(a_{i+1}), 1 ≤ i ≤ n,

dvs. at a_{i−1} og a_{i} har de samme fælles divisorer som a_{i} og a_{i+1}. Da a_{n+1} = 0 får vi

D(a_{0}) ∩ D(a_{1}) = D(a_{n}) ∩ D(0) = D(a_{n}) ∩ ℤ = D(a_{n}),

som siger, at mængde af fælles divisorer for a_{0} og a_{1} er mængden af divisorer i det sidste positive tal, a_{n} i Euklids algoritme.

Eksempel 2.20. Med input a_{0} = 712 og a_{1} = 123 producerer Euklids algoritme den endelige følge

712, 123, 97, 26, 19, 7, 5, 2, 1, 0

som output. De fælles divsorer for 712 og 123 er derfor D(712) ∩ D(123) = D(1) = {−1, 1}.

Det er ganske enkelt at implementere Euklids algoritme på en computer, f.eks. i et regneark eller i Turbo Pascal.

Lad os vende tilbage til ligningen (2.1) endnu en gang. En anden konsekvens (og det fortjener igen et argument!) er identiteterne

a_{i−1}ℤ + a_{i}ℤ = a_{i}ℤ + a_{i+1}ℤ, 1 ≤ i ≤ n,

som viser, at

a_{0}ℤ + a_{1}ℤ = a_{n}ℤ + 0ℤ = a_{n}ℤ,

dvs. at tallene fra a_{n}-tabellen præcis er de tal, der kan skrives som en sum af et tal fra a_{0}-tabellen og et tal fra a_{1}-tabellen. Det følger, at

a_{n} = min((a_{0}ℤ + a_{1}ℤ) ∩ ℕ)

dvs. at a_{n} er det mindste positive tal, der kan fås som sum af et tal fra a_{0}-tabellen med ét fra a_{1}-tabellen. (F.eks. siger Euklids algoritme, at 1 kan fås som en sum af et tal fra 712-tabellen med et tal fra 123-tabellen.)

Det er klart, at tallet a_{n} selv er den mest interessante fælles divisor, for alle fælles divisorer er også divisorer i a_{n}. Hvordan kan vi karakterisere dette tal?

Definition 2.21. Det hele tal D er en største fælles divisor for a og b, hvis • D > 0

• D er en fælles divior for a og b

• Enhver fælles divisor går op i D

Tallet a_{n} fra Euklids algoritme med input a_{0} = a og a_{1} = b (hvis ellers a ≥ b > 0) er en største fælles divisor for a og b. Kunne der være andre og er vi sikre på at der altid findes én?

Lemma 2.22 (Entydighed). Der findes højst en største fælles divisor for a og b.

Bevis. Prøv selv!

Lemma 2.23 (Eksistens). Det mindste naturlige tal, der kan skrives som en sum af et tal fra a-tabellen og et tal fra b-tabellen, dvs. det mindste positive tal som kan skrives på formen sa + bt for s, t ∈ ℤ, er en største fælles divisor.

Bevis. Påstanden er at

D = min((aℤ + bℤ) ∩ ℕ)

er en største fælles divisor – altså at D opfylder de tre krav fra Definition 2.21. (Overvej, at mængden (aℤ + bℤ) ∩ ℕ ikke er tom.)

Det er klart, at D > 0. D går også op i a. For at se det, skriv (2.1) a på formen a = Dq + r hvor q ∈ ℤ og 0 ≤ r < D. Husk på, at der findes hele tal, s og t, så D = as + bt. Altså kan resten

r = a − Dq = a − (as + bt)q = (1 − qs)a + (−tq)b

skrives som en sum af et tal fra a-tabellen og et tal fra b-tabellen. Vi kan ikke have 0 < r < D, for da ville r være mindre end det mindste naturlige tal, D, med denne egenskab. Altså er r = 0, så D går op i a. På akkurat tilsvarende måde kan man vise, at D går op i b. D er altså en fælles divisor. Lad d være en (anden) fælles divisor. Da D har formen D = as + bt, s ∈ ℤ, t ∈ ℤ, vil d gå op i D. Dette viser, at D er en største fælles divisor.

Vi ved nu, at der altid findes netop en største fælles divisor for a og b. Vi betegner den med sfd(a, b).

Vi samler vores erfaring, og lidt til, i sætningen om eksistens- og entydighed af største fælles divisor.

Sætning 2.24 (Eksistens og entydighed af største fælles divisor). Lad a og b være hele tal, ikke begge 0. Da gælder:

1. Der findes netop en største fælles divisor, sfd(a, b) for a og b.

2. sfd(a, b) = min((aℤ + bℤ) ∩ ℕ).

3. sfd(a, b)ℤ = aℤ + bℤ.

Bevis. Kun punkt (3) kræver en bemærkning: Da sfd(a, b) er en sum af et tal fra a-tabellen og et tal tal fra b-tabellen, er sfd(a, b)ℤ ⊆ aℤ + bℤ. Vi har også aℤ + bℤ ⊆ sfd(a, b)ℤ, fordi en sum af et tal fra a-tabellen og et tal fra b-tabellen er deleligt med sfd(a, b).

Læg mærke til at punkt (3) siger, at den største fælles divisor er en sum af et tal fra a-tabellen og et tal fra b-tabellen. Det er så nyttigt, at jeg får lyst til at fremhæve det i et

Korollar 2.25. Lad a og b være hele tal, ikke begge 0. Sæt D = sfd(a, b). Da findes hele tal s og t så

D = sa + tb

Øvelse 2.26. Find s og t, så 1 = 712s + 123t.

Øvelse 2.27. Lad D være et naturligt tal sådan at Dℤ = aℤ + bℤ. Vis, at D = sfd(a, b).

Øvelse 2.28. Vis, at max(D(a) ∩ D(b)) = sfd(a, b); altså, at den største fælles divisor er den største fælles divisor!

Vi ved allerede fra Euklids algoritme, hvordan den største fælles divisor beregnes.

Sætning 2.29. Antag at a_{n} > 0 og at a_{n+1} = 0 i Euklids algoritme med input a_{0} > a_{1} ≥ 0. Da er sfd(a_{0}, a_{1}) = a_{n} og mfm(a_{0}, a_{1}) = \frac{a_{0}a_{1}}{a_{n}}.

Den sidste påstand følger af Opgave 17, som siger at sfd(a, b)·mfm(a, b) = |ab|. Euklids algoritme fortæller også, hvordan vi finder s og t, så D = as + bt.

Beregningen af s og t kan godt formuleres algoritmisk, men vi skal her nøjes med et eksempel.

Eksempel 2.30. Med a_{0} = 2415 og a_{1} = 945 som input genererer Euklids algoritme tallene

2415, 945, 525, 420, 105, 0

som output og altså er sfd(2415, 945) = 105 og mfm(2415, 945) = 21735. Dette output er et resulat af divisionerne

2415 = 945 · 2 + 525
945 = 525 · 1 + 420
525 = 420 · 1 + 105
420 = 105 · 4 + 0.

Ligningerne ovenfor kan også skrives

525 = 2415 − 945 · 2
420 = 945 − 525 · 1
105 = 525 − 420 · 1

og idet vi starter forneden og arbejder os opad, får vi heraf

105 = 525 − 420 = 525 − (945 − 525) = 525 · 2 − 945
= (2415 − 945 · 2) · 2 − 945 = 2415 · 2 + 945 · (−5).

Vi kan altså bruge s_{0} = 2 og s_{1} = −5. Der er også andre muligheder, for da 2415 = 105 · 23 og 945 = 105 · 9 er 0 = 2415 · 9 − 945 · 23 og 105 = 105 + 0 = (2415 · 2 + 945 · (−5)) + (2415 · 9 − 945 · 23) = 2415 · 11 + 945 · (−28).

Øvelse 2.31. Find s og t så 712s + 123t = 1.

Øvelse 2.32. Skriv et computerprogram der med input (a_{0}, a_{1}) giver output sfd(a_{0}, a_{1}) samt hele tal (s_{0}, s_{1}) så a_{0}s_{0} + a_{1}s_{1} = sfd(a_{0}, a_{1}).

2.33. Indbyrdes primiske tal. Tallene 123 og 712 er et eksempel på to indbyrdes primiske hele tal, da 1 er det eneste positive tal, som går op i både 123 og 712. Den generelle definition lyder sådan her:

Definition 2.34. De to hele tal a og b er indbyrdes primiske hvis sfd(a, b) = 1.

Vi vil i det følgende antage at både a og b er forskellige fra 0.

Lemma 2.35. Hvis a og b er indbyrdes primiske, og a går op i bc, da vil a gå op i c.

Bevis. Da a | bc og sfd(a, b) = 1, er (2.4, 2.24) bcℤ ⊆ aℤ og aℤ + bℤ = ℤ. Altså er

cℤ = c(aℤ + bℤ) = caℤ + cbℤ ⊆ aℤ + aℤ = aℤ

så a | c.

Lemma 2.36. sfd(a, b) = 1 ⇔ mfm(a, b) = |ab|.

Bevis. Antag, at sfd(a, b) = 1. Vi skal vise, at ab går op i ethvert fælles multiplum. Lad M = sa = tb være et fælles multiplum. Da a | tb og sfd(a, b) = 1 vil (2.35) a gå op i t og ab vil gå op i tb = M.

Antag, at mfm(a, b) = |ab|. Vi skal vise, at de eneste fælles divisorer er ±1. Lad d være en fælles divisor, a = da′ og b = db′. Da da′b′ er et fælles multiplum, vil ab = d^{2}a′b′ gå op i da′b′, og derfor vil d gå op i 1.

Vi samler til sidst resultaterne fra Sætning 2.13, Sætning 2.24 og Lemma 2.36 i en sætning.

Sætning 2.37. Lad a og b være to hele tal. Da er følgende betingelser ækvivalente:

1. sfd(a, b) = 1

2. mfm(a, b) = |ab|

3. aℤ + bℤ = ℤ

4. aℤ ∩ bℤ = abℤ

5. Der findes hele tal s og t så as + bt = 1.

Vi vil i en senere anvendelse (II.7.1) af Sætning 2.37 erstatte 2.37.(4) med det tilsyneladende svagere aℤ∩bℤ ⊆ abℤ. Det kan vi tillade os fordi fordi inklusionen abℤ ⊆ aℤ ∩ bℤ altid gælder.

Korollar 2.38. Hvis a og b er indbyrdes primiske, og a og b går op i c, da vil ab gå op i c.

Bevis. Tallet c er et fælles multiplum af a og b, så det mindste fælles multiplum, mfm(a, b) = ab, går op i c.

.

3. Primtal

Primtallene har fascineret mennesket gennem i hvert fald de seneste par tusind år, og det vil de nok fortsætte med vores tid ud.

Definition 3.1. Det naturlige tal n kaldes et sammensat tal, hvis der findes hele tal, n_{0} og n_{1}, så n = n_{0}n_{1}, hvor 1 < n_{0} < n og 1 < n_{1} < n. Et primtal er et naturligt tal p > 1 som ikke er sammensat.

Et primtal er altså et naturligt tal, som er større end 1, og som ikke har andre positive divisorer end 1 og sig selv. De første primtal er

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59

og det er faktisk ret let at finde alle primtal under 100 – f.eks. ved at bruge:

Bemærkning 3.2. (Eratostenes’ si.) Gem tallet 2. Fjern dernæst alle multipla af 2 fra mængden af naturlige tal n > 1. Det mindste tilbageblivende tal er 3. Gem det, for det er et primtal. Fjern derefter alle multipla af 3. Gem det mindste af de tilbageblivende tal, 5. Fjern alle multipla af 5 – osv. Det der bliver tilbage er primtallene. Hvis vi er interesseret i at finde alle primtal ≤ N kan vi nøjes med at fjerne alle multipla af n for 2 ≤ n ≤ \sqrt{N}. Skriv et computerprogram der beregner alle primtal ≤ N. Find alle primtal < 10000. (Vel, har du ikke adgang til en computer, kan du nøjes med at finde alle primtal < 100.)

Hvis p er et primtal, og a et naturligt tal, så er sfd(p, a) = 1, hvis og kun hvis p ikke er en divisor i a. Derfor er følgende to observationer faktisk specialtilfælde af (2.35) og (2.38).

Lemma 3.3 (Primtalsdivisionssætningen, Euklid). Lad p være et primtal og a og b to hele tal. Hvis p | ab, da vil p | a, eller p | b.

Bevis. Hvis p | a er der intet at vise. Hvis p ikke er en divisor i a, da er a og p indbyrdes primiske og så vil p | b ifølge (2.35).

Lemma 3.4 (Coprimtalsdivisionssætningen). Lad p og q være to forskellige primtal. Hvis p | a og q | a, da vil pq | a.

Bevis. Da p ≠ q, er p og q indbyrdes primiske, sfd(p, q) = 1, og resultatet følger direkte af Korollar 2.38.

Sætning 3.5. Ethvert naturligt tal n > 1 er et produkt af primtal.

Bevis. Lad P (n), n ≥ 2, være påstanden, at n er et produkt af primtal. P (2) er sand, for 2 er et primtal. Antag at P (k) er sand for 1 < k < n. Hvis n er et primtal, er P (n) oplagt sand. Hvis ikke, er n = n_{0}n_{1}, hvor 1 < n_{0} < n og 1 < n_{1} < n, og begge faktorer er ifølge induktionsantagelsen produkter af primtal. Derfor er også n et produkt af primtal. Dette viser at P (n) er sand.

Ifølge Induktionsaksiomet (1.6) følger det nu, at alle naturlige tal kan skrives som produkter af primtal.

Korollar 3.6. Ethvert naturligt tal n > 1 har en primtalsdivisor.

I fremstillingen af n som et produkt af primtal kan det samme primtal godt forekomme flere gange som i eksemplet

12 = 2 · 2 · 3.  (3.7)

Samler vi alle faktorer af samme primtal p og udtrykker produktet som en potens af p, kan enhver primfaktoropløsning af n > 1 skrives på formen

n = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{r}^{α_{r}}  (3.8)

hvor 1 < p_{1} < p_{2} < ⋯ < p_{r} er forskellige primtal og α_{i}erne er naturlige tal. På den måde kan (3.7) omskrives til

12 = 2^{2} · 3.

Sætning 3.5 siger, at ethvert naturligt tal n > 1 har mindst en fremstilling af formen (3.8). Kan n have mere end en fremstilling? Svaret er, ifølge den følgende sætning om entydig faktorisering, nej.

Sætning 3.9 (Aritmetikkens Hovedsætning). Antag at

p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{r}^{α_{r}} = q_{1}^{β_{1}}q_{2}^{β_{2}} … q_{s}^{β_{s}}

hvor 1 < p_{1} < p_{2} < … p_{r}, 1 < q_{1} < q_{2} < … q_{s}, alle p_{i} og alle q_{j} er primtal, og alle α_{i} og β_{j} er naturlige tal. Da er r = s, og p_{i} = q_{i} og α_{i} = β_{i} for alle i = 1, 2, …, r.

Bevis. Lad P (n), n > 1, stå for den påstand, at n kun har én primfaktoropløsning (3.8). P (2) er klart sand, da 2 er et primtal.

Antag at P (k) er sand for 1 < k < n. Hvis n er et primtal, findes kun en faktorisering af formen (3.8), så P (n) er sand i dette tilfælde. Hvis n er et sammensat tal, lad

p_{1}p_{2} … p_{u} = n = q_{1}q_{2} … q_{v}  (3.10)

være to fremstillinger af n. (Her er antallene af faktorer u ≥ 2 og v ≥ 2, da n ikke er et primtal.) Vi kan ordne faktorerne i voksende orden så vi opnår at

p_{1} ≤ p_{2} ≤ ⋯ ≤ p_{u}, q_{1} ≤ q_{2} ≤ ⋯ ≤ q_{v}.

Vi stiler mod at vise, at u = v, og p_{i} = q_{i} for alle i = 1, 2, …, u.

Antag nu at p_{1} ≠ q_{1}. Da p_{1} og q_{1} går op i n, og p_{1} og q_{1} er indbyrdes primiske, vil (3.4) produktet p_{1}q_{1} gå op i n. Skriv n på formen n = p_{1}q_{1}r og lad r = r_{1} … r_{l} være en fremstilling af r som et produkt (3.5) af primtal. Da er

n = p_{1}q_{1}r_{1} … r_{l}

en fremstiling af n som et produkt af primtal. Nu ved vi, at

p_{1}p_{2} … p_{u} = n = p_{1}q_{1}r_{1} … r_{l}

eller (ved division med p_{1}) at

p_{2} … p_{u} = \frac{n}{p_{1}} = q_{1}r_{1} … r_{l}.

Fra induktionsantagelsen slutter vi, at disse to fremstillinger af \frac{n}{p_{1}} < n har de samme faktorer. Specielt må q_{1} på højresiden være lig med et af tallene p_{2}, …, p_{u} på venstresiden. Altså er q_{1} ≥ p_{1}, da p_{2} ≥ p_{1}, …, p_{u} ≥ p_{1}. Tilsvarende er

q_{1}q_{2} … q_{v} = n = p_{1}q_{1}r_{1} … r_{l}

eller

q_{2} … q_{v} = \frac{n}{q_{1}} = p_{1}r_{1} … r_{l}

og induktionsantagelsen giver, at faktoren p_{1} fra højresiden er lig med en af faktorerne q_{2}, …, q_{v} fra venstresiden, og det følger, at p_{1} ≥ q_{1}, da q_{2} ≥ q_{1}, …, q_{v} ≥ q_{1}. Vi kan nu konkludere, at p_{1} = q_{1}. Det er i åbenlys modstrid med antagelsen p_{1} ≠ q_{1}.

Vi ser heraf, at p_{1} ≠ q_{1} ikke kan gælde. Altså må vi have p_{1} = q_{1}, og vi kan nu dividere begge sider af fremstillingen (3.10) med p_{1} = q_{1}. Det giver:

p_{2} … p_{u} = \frac{n}{p_{1}} = \frac{n}{q_{1}} = q_{2} … q_{v}

og da \frac{n}{p_{1}} = \frac{n}{q_{1}} er mindre end n, giver induktionsantagelsen, at u = v (eller rettere at u − 1 = v − 1) og at p_{i} = q_{i} for alle i = 2, …, u. Dette viser, at P (n) er sand, også hvis n er sammensat.

Induktionsaksiomet tillader os nu at konkludere, at alle hele tal n > 1 har en entydig primtalsfaktorisering.

Øvelse 3.11. Skriv et computerprogram, der beregner primtalsfaktoriseringer.

Sætningen om Entydig Faktorisering har sandsynligvis været kendt i en eller anden form siden Euklid, men den første eksplicitte formulering skyldes Gauss i 1801. Den næste sætning skyldes faktisk Euklid, så den dateres til ca. -400, hvor Euklid viste, at “der er flere primtal end ethvert forelagt antal af primtal”.

Sætning 3.12 (Euklid). Der findes uendeligt mange primtal.

Bevis. Antag, at der kun findes endelig mange primtal. Lad p_{1}, …, p_{k} være listen over alle primtal. Sæt

n = 1 + p_{1} … p_{k}.

Ifølge (3.6) har n en primtalsdivisor, p. Men dette primtal p er forskelligt fra p_{1}, …, p_{k}, for ingen af disse primtal går op i n (resten ved division af n med p_{i} er 1). Det er i modstrid med antagelsen, at vores liste bestod af alle primtal.

Selv om der altså findes uendeligt mange pritmal, så findes der på den anden side vilkårligt lange primtalsfri zoner.

Bemærkning 3.13. Lad n være et helt tal. De n − 1 tal

n! + 2, n! + 3, …, n! + n

er alle sammensatte, for 2|n!+2, 3|n!+3, …, n|n!+n. Vi kan altså finde vilkårligt lange strækninger af primtalsfrie naturlige tal.

Her er nogle af eksempler på uløste problemer om primtal:

• Goldbachs formodning fra 1742: Ethvert lige tal > 2 er en sum af to primtal. F.eks. er 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, …, 36 = 13 + 23.

• Hvis både p og p + 2 er primtal, siges de at være primtalstvillinger. Det formodes, men vides ikke, at der findes uendeligt mange primtalstvillinger. I begyndelsen af talrækken er primtalstvillinger ret hyppige, 2 og 3, 3 og 5, 5 og 7. Også 250049 og 2500051 er (lidt større) tvillinger. Det siges, at 242206083 · 2^{38880} ± 1 er primtalstvillinger.

• En sætning af Gauss, som han beviste, da han var 19, siger, at den regulære p-kant, hvor p er et ulige primtal, er konstruerbar hvis og kun hvis p er et Fermat tal. Et Fermat tal er et tal af formen F_{t} = 2^{2^{t}} + 1 for et t ≥ 0. Fermat påstod, at alle tal af denne form, var primtal, og godt nok er 3, 5, 17, 257, 65537 svarende til t = 0, 1, 2, 3, 4 alle primtal. (Den regulære 257-kant kan altså konstrueres med passer og lineal.) L. Euler (1707–1783) viste imidlertid, at

F_{5} = 2^{2^{5}} + 1 = 4294967297 = 641 · 6700417,

er sammensat. F_{6} er produktet af primtallet 274177 og et andet primtal med 14 cifre. Faktisk ved man i dag, at F_{5}, …, F_{20} alle er sammnensatte tal. Mange talteoretikere tror nu, at alle Fermat tal efter F_{4} er sammensatte [3].

Læs mere om primtal på http://www.utm.edu/research/primes/index.html

Opgaver

Opgave 1. Vis, at 2^{n} > n^{2} + 1 for alle naturlige tal n ≥ 5.

Opgave 2. Vis, at

∑_{k=1}^{n} 2^{k−1} = 2^{n} − 1

for alle naturlige tal n ∈ ℕ.

Opgave 3. Vis, at

∑_{k=1}^{n} k^{2} = \frac{n(n + 1)(2n + 1)}{6}

for all naturlige tal n ∈ ℕ.

Opgave 4. Vis, at

∑_{k=1}^{n} k^{3} = \frac{n^{2}(n + 1)^{2}}{4}

for alle naturlige tal n ∈ ℕ.

Opgave 5. Vis, at n! > 2^{n} for alle naturlige tal n ≥ 4.

3. PRIMTAL 21

Opgave 6. Vis, at 9 går op i 10^{n+1} + 3 · 10^{n} + 5 for alle naturlige tal n ∈ ℕ. Opgave 7. Vis, at enhver opad begrænset mængde S ⊆ ℤ har et største

element, max S. Vink: max S = − min(−S).

Opgave 8. Lad S ⊆ ℤ være nedad begrænset. Vis, at min(aS) = a min(S) når a > 0. Hvad kan du sige når a < 0?

Opgave 9. Vis, at min(S_{1}) ≥ min(S_{2}) når S_{1} ⊆ S_{2} ⊆ ℤ er nedad begrænsede mængder af hele tal.

Opgave 10. Brug Euklids algoritme til at beregne sfd(a, b) og finde hele tal s og t så as + bt = sfd(a, b) for a = 1091, b = 165 og a = 1324, b = 56.

Opgave 11. Vis, at sfd(a, b) = sfd(−a, b) = sfd(−a, −b) = sfd(b, a) = sfd(|a|, |b|). Gælder noget tilsvarende for mfm(a, b)?

Opgave 12. Antag, at a > 0 og b > 0 og vis: sfd(a, b) = a ⇔ a | b ⇔ mfm(a, b) = b.

Opgave 13. Vis, at sfd(a, b + sa) = sfd(a, b). Brug dette til at beregne sfd(572, 112).

Opgave 14. Antag (for nemheds skyld) at a > 0, b > 0, c > 0. Vis, at sfd(ca, cb) = c sfd(a, b)

mfm(ca, cb) = c mfm(a, b)

Opgave 15. Vis, at sfd(a, bc) = sfd(a, sfd(a, b)c). Vink: aℤ + bcℤ = aℤ + (aℤ + bℤ)c.

Opgave 16. Kik på denne tabel:

\begin{matrix}a & b & ab & mfm(a, b) & sfd(a, d) \\ 2 & 6 & 12 & 6 & 2 \\ -4 & 6 & -24 & 12 & 2 \\ 6 & 8 & 48 & 24 & 2 \\ 6 & -9 & -54 & 18 & 3 \\ 24 & 36 & 864 & 72 & 12 \end{matrix}

Formuler en formodning om sammmenhængen mellem tallen i de tre sidste søjler. Regn den næste opgave.

Opgave 17. Vis, at mfm(a, b) · sfd(a, b) = |ab| (når a ≠ 0 og b ≠ 0). Opgave 18. Vis, at sfd(a^{2}, b^{2}) = sfd(a^{2}, sfd(sfd(a, b)^{2}, b)b). Slut heraf at hvis

sfd(a, b) = 1, da er også sfd(a^{2}, b^{2}) = 1.

Opgave 19. Hvad siger Opgave 18 om sfd(\frac{a^{2}}{sfd(a,b)^{2}} , \frac{b^{2}}{sfd(a,b)^{2}} )? Konkludér, at sfd(a^{2}, b^{2}) = sfd(a, b)^{2}.

Opgave 20. Antag, at a er indbyrdes primisk med a_{1}, …, a_{r}. Vis, at a er indbyrdes primisk med produktet a_{1} … a_{r}. (Vink: Induktion.)

Opgave 21. Lad p være et primtal og a_{1}, …, a_{r} hele tal. Vis, at hvis p går op i produktet a_{1} … a_{r}, da vil p | a_{i} for (mindst) et i, 1 ≤ i ≤ r. (Vink: Se (3.3) og brug induktion.)

Opgave 22. Antag, at tallene a_{1}, …, a_{r} er parvis indbyrdes primiske, dvs. at sfd(a_{i}, a_{j}) = 1 for i ≠ j, og at de alle går op i b. Vis, at produktet a_{1} … a_{r} går op i b. (Vink: Se (2.38) og brug induktion.)

Opgave 23. Lad a_{1}, a_{2}, a_{3} være hele tal. Vis at a_{1}, a_{2}, a_{3} er parvis indbyrdes primiske, dvs sfd(a_{2}, a_{3}) = sfd(a_{1}, a_{3}) = sfd(a_{1}, a_{2}) = 1, hvis og kun hvis der findes hele tal s_{1}, s_{2}, s_{2} så s_{1}a_{2}a_{3} +s_{2}a_{1}a_{3} +s_{3}a_{1}a_{2} = 1. Kan du generalisere dette resulat?

Opgave 24. Antag at p | a^{2} hvor p er et primtal og a et helt tal. Vis, at p | a.

Opgave 25. Er 499 et primtal? Er 501? (Se (3.2.))

Opgave 26. Skriv 9464 som et produkt af primtal.

Opgave 27. Vis, at der ikke findes hele tal m og n så m^{2} = 2n^{2}. Slut at \sqrt{2} ikke er rational (dvs. ikke kan skrives på formen \frac{m}{n}). (Se Messer p. 121.)

Opgave 28. Skriv a > 0 og b > 0 på formen

a = p_{1}^{α_{1}}p_{2}^{α_{2}} … p_{r}^{α_{r}}, b = p_{1}^{β_{1}}p_{2}^{β_{2}} … p_{r}^{β_{r}}.

Hvis vi tillader at α_{i}erne og β_{i}erne kan antage værdien 0, kan vi godt antage at det er de samme primtal der forekommer i begge faktoriseringer hvor p_{1} < p_{2} < … p_{r}. Vis, at

1. a|b ⇔ α_{i} ≤ β_{i} for alle i = 1, …, r.

2. sfd(a, b) = ∏_{i=1}^{r} p_{i}^{min{α_{i},β_{i}}}

3. mfm(a, b) = ∏_{i=1}^{r} p_{i}^{max{α_{i},β_{i}}}

KAPITEL 2 Gruppeteori

En gruppe er en algebraisk struktur som optræder meget hyppigt i matematik. Faktisk drejede hele første kapitel sig om den abelske gruppe af hele tal. Andre eksempler på grupper er symmetrigrupper, f.eks. symmetrigruppen af et molekyle.

1. Funktioner

Formålet med dette afsnit er at indføre nogle begreber. Det indeholder sikkert ikke noget der er nyt for dig, så jeg udelader beviserne. (Se også Messer p. 219– 221.)

Lad A og B være mængder. En funktion f: A → B med domæne dom(f) = A og codomæne codom(f) = B er en forskrift der til ethvert element a i A knytter netop et element f(a) i B. Elementet f(a) ∈ B er billedet af a ∈ A.

For delmængder A_{1} ⊆ A og B_{1} ⊆ B kaldes

f(A_{1}) = {f(a_{1}) | a_{1} ∈ A_{1}}

for billedet af A_{1} og

f^{−1}(B_{1}) = {a ∈ A | f(a) ∈ B_{1}}

for originalmængden af B_{1}. Specielt, for et element b ∈ B, betegner

f^{−1}(b) = f^{−1}({b}) = {a ∈ A | f(a) = b}

af alle elementer i A som afbildes i b ∈ B, originalmængden til b.

Definition 1.1. Funktionen f: A → B er

1. surjektiv hvis ethvert element i B er billede af mindst et element i A

2. injektiv hvis ethvert element i B er billede af højst et element i A

3. bijektiv hvis ethvert element i B er billede af netop et element i A.

Funktionen f er surjektiv, hvis f^{−1}(b) ≠ ∅ for alle b ∈ B, injektiv hvis f^{−1}(b) indeholder højst et element for alle b ∈ B, bijektiv hvis f^{−1}(b) indeholder netop et element for alle b ∈ B. En funktion er bijektiv hvis og kun hvis den er surjektiv og injektiv.

Hvis f: A → B og g: B → C er to funktioner med codom(f) = dom(g), da er sammensætningen g ∘ f: A → C funktionen defineret ved g ∘ f(a) = g(f(a)) for all a ∈ A.

Sætning 1.2. (Sammensætning af funktioner er associativ). Lad f: A → B, g: B → C og h: C → D være funktioner. Da er

h ∘ (g ∘ f) = (h ∘ g) ∘ f: A → D.

Da det alligevel ikke spiller nogen rolle hvor parenteserne placeres, skriver vi h ∘ g ∘ f for en af de to sammensatte funktioner i Sætning 1.2.

Øvelse 1.3. Enhver funktion kan skrives som sammensætningen af en surjektion efterfulgt af en injektion.

Identitetsfunktionen id_{A}: A → A eller 1_{A}: A → A er den funktion der til ethvert element a ∈ A knytter a.

Vi siger, at g: B → A er en invers til f: A → B hvis g ∘f = 1_{A} og f ∘g = 1_{B}. Hvis f har en invers, da er den entydigt bestemt og vi betegner den med f^{−1}. Men ikke alle funktioner har en invers.

Sætning 1.4. En funktion har en invers hvis og kun hvis den er bijektiv.

Øvelse 1.5. Hvis både f og g er bijektive og codom(f) = dom(g), da er g ∘f bijektiv med invers (g ∘ f)^{−1} = f^{−1} ∘ g^{−1}. Den inverse funktion f^{−1} er bijektiv og dens inverse er (f^{−1})^{−1} = f.

Jeg slutter med en meget simpel, men overraskende nyttig observation.

Sætning 1.6. (Skuffeprincippet.) Antag at A og B er to endelige mængder og at antallet af elementer i A er lig med antallet af elementer i B. Lad f: A → B være en afbildning fra A til B. Da er følgende betingelser ækvivalente:

1. f er injektiv.

2. f er surjektiv.

3. f er bijektiv.

Som ethvert postbud ved, hvis 100 breve fordeles i 100 postkasser så der højst ligger et brev i hver postkasse, da vil der faktisk ligge netop et brev i hver postkasse.

2. Transformationer af planen

Den geometriske plan kan identificeres med mængden ℝ^{2} af alle reelle talpar ved valg af et koordinatsystem. Ved en (ortogonal) transformation af planen forstår vi en afbildning af planen ind i sig selv givet ved en drejning om (0, 0) eller en spejling i en ret linje gennem (0, 0).

Vi vil bruge betegnelsen D(α): ℝ^{2} → ℝ^{2} for drejningen mod uret med vinkel α omkring (0, 0). Vi vil bruge betegnelsen S(β): ℝ^{2} → ℝ^{2} for spejlingen i den rette linje gennem (0, 0) der danner vinklen (!) \frac{β}{2} med x-aksen.

I polære koordinater er funktionerne D(α) og S(β) givet ved

D(α)(r cos ϕ, r sin ϕ) = (r cos(ϕ + α), r sin(ϕ + α))
S(β)(r cos ϕ, r sin ϕ) = (r cos(β − ϕ), r sin(β − ϕ)).

For alle α ∈ ℝ og β ∈ ℝ, er

D(α + 2π) = D(α), S(β + 2π) = S(β).

D(0) er identiteten, ofte betegnet med E, af ℝ^{2}.

Ud fra disse to eksplicitte udtryk for drejningen D(α) og spejlingen S(β) er det meget nemt at finde ud af deres opførsel under sammensætning.

Sætning 2.1. Der gælder

D(α) ∘ D(β) = D(α + β)
S(α) ∘ S(β) = D(α − β)
D(α) ∘ S(β) = S(α + β)
S(α) ∘ D(β) = S(α − β)

Heraf følger at både D(α) og S(β) er bijektioner med inverse

D(α)^{−1} = D(−α), S(β)^{−1} = S(β).

Bemærk specielt at en spejling er sin egen inverse, S(β) ∘ S(β) = E.

3. Kvadratets symmetrigruppe

Lad K være kvadratet i planen med hjørner (±1, ±1). Vi skal undersøge mængden D_{4} af symmetrier af K, dvs. mængden af de transformationer f: ℝ^{2} → ℝ^{2} som opfylder f(K) = K. (D_{4} er mængden af symmetrier af en 4-kant.)

Symmetrierne af K er identitetsafbildningen, drejninger med vinkel \frac{π}{2}, π og \frac{3π}{2} samt spejlingerne i koordinatakserne og de to diagonaler. Dvs.

D_{4} = {e, d_{1}, d_{2}, d_{3}, s_{1}, s_{2}, s_{3}, s_{4}}

hvor

e = E,

d_{1} = D(\frac{π}{2} ), d_{2} = D(π), d_{3} = D(\frac{3π}{2} ),

s_{1} = S(0), s_{2} = S(\frac{π}{2} ), s_{3} = S(π), s_{4} = S(\frac{3π}{2} ).

Dette er imidlertid ikke hele historien. For sammensætningen af to symmetrier er igen en symmetri. Vi siger, at mængden D_{4} er lukket under sammensætning. F.eks. er

d_{1} ∘ d_{1} = d_{2}

d_{1} ∘ s_{1} = D(\frac{π}{2} ) ∘ S(0) = S(\frac{π}{2} ) = s_{2}

ifølge Sætning 2.1.

Vi kan sætte beregningen af alle sammensætninger af to symmetrier op i en tabel, en såkaldt Cayley tabel:

\begin{matrix}D_{4} & e & d_{1} & d_{2} & d_{3} & s_{1} & s_{2} & s_{3} & s_{4} \\ e & e & d_{1} & d_{2} & d_{3} & s_{1} & s_{2} & s_{3} & s_{4} \\ d_{1} & d_{1} & d_{2} & d_{3} & e & s_{2} & s_{3} & s_{4} & s_{1} \\ d_{2} & d_{2} & d_{3} & e & d_{1} & s_{3} & s_{4} & s_{1} & s_{2} \\ d_{3} & d_{3} & e & d_{1} & d_{2} & s_{4} & s_{1} & s_{2} & s_{3} \\ s_{1} & s_{1} & s_{4} & s_{3} & s_{2} & e & d_{3} & d_{2} & d_{1} \\ s_{2} & s_{2} & s_{1} & s_{4} & s_{3} & d_{1} & e & d_{3} & d_{2} \\ s_{3} & s_{3} & s_{2} & s_{1} & s_{4} & d_{2} & d_{1} & e & d_{3} \\ s_{4} & s_{4} & s_{3} & s_{2} & s_{1} & d_{3} & d_{2} & d_{1} & e \end{matrix}

hvor sammensætningen f ∘g er skrevet ind i krydset mellem f-rækken og g-søjlen.

Ved hjælp af Cayley tabellen er det let at beregne sammensætninger af kvadratets symmetrier. Bemærk specielt, at d_{1}^{2} = d_{2}, d_{1}^{3} = d_{1}d_{1}^{2} = d_{1}d_{2} = d_{3}, og

s_{1}^{2} = s_{1} ∘ s_{1} = e
d_{1}^{4} = d_{1} ∘ d_{1}^{3} = d_{1} ∘ d_{3} = e
s_{1} ∘ d_{1} ∘ s_{1} = s_{4} ∘ s_{1} = d_{3} = d_{1}^{3}.

Mere generelt bemærker vi 1. For alle f, g, h ∈ D_{4} gælder f ∘ (g ∘ h) = (f ∘ g) ∘ h.

2. For alle f ∈ D_{4} gælder f ∘ e = f = e ∘ f.

3. For ethvert f ∈ D_{4} findes et g ∈ D_{4} så f ∘ g = e = g ∘ f. Den første påstand, som involverer 8^{3} tilfælde, er måske lidt omstændelig at

verificere ud fra Cayley tabellen; det er nemmere at benytte Sætning 1.2. De to andre egenskaber ved D_{4} ses umiddelbart ud fra Cayley tabellen.

Det er disse egenskaber der gør D_{4} til en gruppe.

4. Grupper

Gruppebegrebet er en formalisering af de egenskaber ved D_{4} som vi observerede i forrige afsnit.

Definition 4.1. En gruppe er en mængde sammen med en afbildning

G × G → G
(f, g) → f • g

som opfylder de tre betingelser:

1. (Associativitet) For alle f, g, h ∈ G gælder f • (g • h) = (f • g) • h.

2. (Neutralt Element) Der findes et element e ∈ G, så f • e = f = e • f for alle f ∈ G.

3. (Inverst element) For ethvert element f ∈ G findes et element g ∈ G, så f • g = e = g • f.

Et element e der opfylder (2) kaldes et neutralelement; et element g der opfylder (3) siges at være et inverst element til f. (Lige om lidt viser vi, at der kun findes et neutralelement og kun et inverst element.)

Gruppen (G, •) består således af både mængde G og af kompositionsreglen eller gruppemultiplikation •: G × G → G som er en forskrift der fortæller hvordan elementet f • g dannes ud fra f og g. For øvrigt udelades symbolet for kompositionsreglen ofte, og man skriver bare fg for f • g.

Eksempel 4.2. (D_{4}, ∘) er en gruppe, kompositionsreglen er sammensætning. Mængden af alle transformationer af planen er en gruppe, O(2), med sammensætning som gruppemultiplikation. (ℤ, +) er en gruppe, kompositionsreglen er addition. (ℕ, +) er ikke en gruppe, der mangler et neutralt element. (ℕ_{0}, +) er heller ikke en gruppe, der mangler inverse elementer. Den trivielle gruppe {e} indeholder et enkelt (neutral)element.

Her er nogle umiddelbare konsekvenser af definitionen (4.1) af en gruppe.

Proposition 4.3. Neutralelementet er entydigt bestemt.

Bevis. Lad e_{1} og e_{2} være neutralelementer. Da er

e_{1} = e_{1} • e_{2} = e_{2}

hvor det venstre lighedstegn skyldes at e_{2} er et neutralelement, og det højre at e_{1} er et neutralelement.

Proposition 4.4. Inverse elementer er entydige.

Bevis. Lad g_{1} og g_{2} være inverse til f. Da er

g_{1} = g_{1} • e = g_{1} • (f • g_{2}) = (g_{1} • f) • g_{2} = e • g_{2} = g_{2}

hvor vi benytter alle tre egenskaber fra Definition 4.1.

Det inverse element til f, som altså er entydigt bestemt af f, betegnes f^{−1}.

Eksempel 4.5. Mængden af alle bijektioner f: A → A med sammensætning som komposition er en gruppe. Kompositionsreglen er associativ fordi (1.2) sammensætning af funktioner er associativ. Neutralelementet er identitetsafbildningen 1_{A} og den inverse til gruppeelementet f er den inverse funktion f^{−1}.

Proposition 4.6. (Forkortning) Hvis g • x = g • y eller x • g = y • g, da er x = y.

Bevis. Multiplicer fra venstre eller højre med g^{−1}.

For n ∈ ℕ sætter vi

f^{n} = \underbrace{f • f ⋯ • f}_{n faktorer}, f^{−n} = (f^{−1})^{n} = \underbrace{f^{−1} • f^{−1} ⋯ • f^{−1}}_{n faktorer}

og vi sætter f^{0} = e til at være neutralelementet. Så gælder de sædvanlige regler for potensregning.

Proposition 4.7. Lad f og g være elementer i gruppen (G, •). Så gælder:

1. (fg)^{−1} = g^{−1}f^{−1}

2. (f^{−1})^{−1} = f

3. f^{m}f^{n} = f^{m+n} for alle hele tal m, n ∈ ℤ

4. (f^{m})^{n} = f^{mn} for alle hele tal m, n ∈ ℤ

5. (f^{n})^{−1} = f^{−n} for alle hele tal n ∈ ℤ

Eksempel 4.8. I symmetrigruppen D_{4} er d_{1}^{−1} = d_{1}^{−1}e = d_{1}^{−1}d_{1}^{4} = d_{1}^{3} = d_{3} og (d_{1}s_{2})^{−2} = ((d_{1}s_{2})^{−1})^{2} = (s_{2}^{−1}d_{1}^{−1})^{2} = (s_{2}d_{3})^{2} = s_{3}^{2} = e.

Gruppens orden, |G|, er antallet af elementer i G. En endelig gruppe er en gruppe med en endelig orden. D_{4} er en endelig gruppe af orden |D_{4}| = 8. De hele tals gruppe er uendelig.

I almindelighed er f • g ≠ g • f. I D_{4} f.eks. er d_{1} ∘ s_{1} = s_{2} mens s_{1} ∘ d_{1} = s_{4}. I gruppen (ℤ, +) derimod gælder at m + n = n + m for alle m, n ∈ ℤ. De hele tal er et eksempel på en kommutativ eller abelsk gruppe.

Definition 4.9. En abelsk gruppe er en gruppe (G, •) som opfylder at

f • g = g • f

for alle elementer f ∈ G og g ∈ G.

I den abelske gruppe (ℤ, +) er 2^{−1} = −2. Det ser jo lidt mærkværdigt ud. Det er da også sædvane at betegne kompositionsreglen i en abelsk gruppe med +, neutralelementet med 0 og det inverse, eller modsatte, element til f med −f. Potensen f^{n} defineret ved f^{n} = f +⋯+f betegnes nf og f^{−n} = (−f)+⋯+(−f) betegnes (−n)f for n ∈ ℕ. Med disse notationskonventioner får regnereglerne fra Proposition 4.7 udseendet:

1. −(f + g) = (−f) + (−g)

2. −(−f) = f

3. mf + nf = (m + n)f

4. n(mf) = (nm)f

5. −(nf) = (−n)f for alle gruppeelementer f, g ∈ G og for alle hele tal m, n ∈ ℤ.

Øvelse 4.10. (=Opgave 41) Lad (G, •) og (H, ∗) være grupper. Vis, at produktet G×H på naturlig måde er en gruppe. (Husk at verificere betingelserne fra Definition 4.1!) Hvad er ordenen af produktgruppen hvis begge grupper er endelige? Vis, at produktgruppen er abelsk hvis (og kun hvis?) G og H er abelske.

5. Undergrupper og gruppehomomorfier

Hvis du kigger på det øverste venstre hjørne af Cayley tabellen for symmetrigruppen D_{4} vil du lægge mærke til at delmængden bestående af de 4 elementer {e, d_{1}, d_{2}, d_{3}} danner en mindre gruppe inden i D_{4}. Dette er et eksempel på en undergruppe.

Definition 5.1. Lad (G, •) være en gruppe. En undergruppe af G er en delmængde H ⊆ G så

1. e ∈ H

2. f • g ∈ H for alle f ∈ H og g ∈ H

3. f^{−1} ∈ H for alle f ∈ H.

Betingelse (2) udtrykker at H er lukket under gruppemultiplikationen, og betingelse (3) at H er lukket under dannelse af inverse elementer.

Bemærk, at hvis H er en undergruppe af G, da er H med den arvede gruppemultiplikation igen en gruppe:

Proposition 5.2. Enhver undergruppe H ⊆ G er en gruppe.

Eksempel 5.3. G har altid de to undergrupper G og {e}. 3ℤ, og mere generelt nℤ, er en undergruppe i ℤ. Symmetrigruppen D_{4} indeholder en undergruppe {e, d_{1}, d_{2}, d_{3}} af orden 4, som igen indeholder undergruppen {e, d_{2}} af orden 2. D_{4} er selv en undergruppe af gruppen O(2) af alle transformationer af planen. Og O(2) er en undergruppe af alle bijektioner ℝ^{2} ⟶ℝ^{2}.

Øvelse 5.4. Det er klart, at a-tabellen aℤ, for ethvert helt tal a ∈ ℤ, er en undergruppe af ℤ. Vi vil vise, at der ikke er andre.

Lad H være en undergruppe af ℤ. Hvis H = {0} er triviel, er vi hjemme, da {0} = 0ℤ. Antag derfor, at H ikke er triviel. Vis, at da er H ∩ ℕ ≠ ∅ og at tallet a = min(H ∩ ℕ) derfor er defineret. Overbevis nu dig selv, og hvem der ellers befinder sig indenfor hørevidde, om at a > 0, a ∈ H og aℤ ⊆ H. For at vise den anden inklusion, H ⊆ aℤ, vælg et vilkårligt element n ∈ H og skriv n på formen n = aq + r hvor 0 ≤ r < a (Divisionsalgoritmen!). Argumenter for, at r = 0 er den eneste mulighed, og slut at n ∈ aℤ.

Undergrupper kan f.eks. opstå som billeder af såkaldte gruppehomomorfier.

Definition 5.5. Lad (G, •) og (H, ∗) være grupper. En (gruppe)homomorfi er en afbildning ϕ: G → H som opfylder

ϕ(g_{1} • g_{2}) = ϕ(g_{1}) ∗ ϕ(g_{2})

for alle g_{1} ∈ G og g_{2} ∈ G.

En epimorfi er en surjektiv homomorfi, en monomorfi er en injektiv homomorfi, en isomorfi er en bijektiv homomorfi. En endomorfi er en homomorfi af en gruppe ind i sig selv, en automorfi er en bijektiv endomorfi.

Eksempel 5.6. Lad g være et element i en gruppe G og lad ϕ_{g}: ℤ → G være afbildningen givet ved ϕ_{g}(n) = g^{n}, n ∈ ℤ. Da (se (4.7))

ϕ_{g}(n + m) = g^{n+m} = g^{n}g^{m} = ϕ_{g}(n)ϕ_{g}(m)

er ϕ_{g}: ℤ → G en homomorfi.

Øvelse 5.7. Find to forskellige gruppehomomorfier ϕ: ℤ → ℤ, med billede ϕ(ℤ) = nℤ lig med n-tabellen. Find en automorfi af ℤ som sender den ene homomorfi over i den anden. Hvor mange automorfier af ℤ findes der?

Proposition 5.8. Identitetsafbildningen er en homomorfi. Sammensætningen af to homomorfier er en homomorfi. Den inverse afbildning til en isomorfi er en isomorfi.

Bevis. Prøv selv!.

Vi siger, at grupperne G og H er isomorfe, G ≅ H, hvis der findes en gruppeisomorfi mellem dem. Isomorfe (endelige) grupper har samme orden. (Men er to grupper af samme orden isomorfe?)

Øvelse 5.9. Find isomorfier mellem gruppen (ℝ_{+}, ·) af positive, reelle tal med multiplikation og gruppen (ℝ, +) af reelle tal med addition.

Proposition 5.10. Enhver gruppehomomorfi afbilder neutralelement i neutralelement og inverst element i inverst element.

Bevis. Vi har

ϕ(e) = ϕ(ee) = ϕ(e)ϕ(e)

og multiplicerer vi denne ligning på begge sider med ϕ(e)^{−1}, får vi, at ϕ(e) er neutralelementet i H. Multiplicerer vi nu begge sider af ligningen

ϕ(e) = ϕ(gg^{−1}) = ϕ(g)ϕ(g^{−1})

med ϕ(g)^{−1} fra venstre følger det, da jo ϕ(e) er neutralelement i H, at ϕ(g)^{−1} = ϕ(g^{−1}).

Eksempel 5.11. Lad S_{4} være gruppen af alle bijektive afbildninger af {1, 2, 3, 4} ind i sig selv. S_{4} er med andre ord gruppen af alle permutationer af tallene 1,2,3,4. Ordenen er |S_{4}| = 4! = 24.

Nummerer hjørnerne i kvadratet med tallene 1,2,3 og 4. Da enhver af kvadratets symmetrier permuterer hjørnerne, vil enhver symmetri bestemme en permutation af {1, 2, 3, 4}. Til enhver symmetri har vi altså knyttet en permutation, dvs. vi har en afbildning af D_{4} ind i S_{4}. Denne afbildning ϕ: D_{4} → S_{4} er en gruppehomomorfi. F.eks. er (hvis du ellers har nummereret kvadratets hjørner som jeg har)

ϕ(d_{1}) = ( \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{matrix} )
ϕ(s_{1}) = ( \begin{matrix}1 & 2 & 3 & 4 \\ 4 & 3 & 2 & 1 \end{matrix} )

og

ϕ(d_{1}s_{1}) = ϕ(s_{2}) = ( \begin{matrix}1 & 2 & 3 & 4 \\ 1 & 4 & 3 & 2 \end{matrix} ) = ϕ(d_{1})ϕ(s_{1})

hvilket viser, at ϕ opfylder kravet til en homomorfi i hvert fald for produktet d_{1}s_{1}.

Definition 5.12. Kernen for homomorfien ϕ: G → H er originalmængden til neutralelementet, dvs.

ker ϕ = ϕ^{−1}(e) = {g ∈ G | ϕ(g) = e}

Vi viser nu, at både kernen og billedet, im ϕ = ϕ(G), for en homomorfi er undergrupper.

Proposition 5.13. Kernen for homomorfien ϕ: G → H er en undergruppe i G og billedet er en undergruppe i H.

Bevis. Lad ϕ: G → H være en homomorfi. Vi skal nøjes med at vise, at kernen ker ϕ er en undergruppe i G. Da ϕ sender neutralelement i neutralelement, er e ∈ K. Hvis g_{1} og g_{2} ligger i kernen, vil også produktet g_{1}g_{2} ligge i kernen, for ϕ(g_{1}g_{2}) = ϕ(g_{1})ϕ(g_{2}) = ee = e. Hvis g ligger i kernen, vil også dets inverse ligge i kernen for ϕ(g^{−1}) = ϕ(g)^{−1} = e^{−1} = e.

Faktisk er billedet af enhver undergruppe af G og originalmængden af enhver undergruppe af H igen en gruppe.

Bemærkning 5.14. Der gælder

ϕ(K) = {e} ⇔ K ⊆ ker ϕ

for enhver delmængde (specielt undergruppe) K ⊆ G.

Kernen afgør om en homomorfi er injektiv.

Sætning 5.15. Lad ϕ: G → H være en homomorfi. Da gælder:

ker ϕ = {e} ⇔ ϕ er en monomorfi.

Bevis. Det er klart, at hvis ϕ er injektiv, så er kernen triviel. Antag omvendt at kernen er triviel. Lad g_{1} og g_{2} være to elementer af G med samme billede, ϕ(g_{1}) = ϕ(g_{2}). Da ϕ(g_{1}g_{2}^{−1}) = ϕ(g_{1})ϕ(g_{2}^{−1}) = ϕ(g_{1})ϕ(g_{2})^{−1} = e, ligger g_{1}g_{2}^{−1} i kernen og er derfor lig med neutalelementet, dvs. g_{1} = g_{2}.

Eksempel 5.16. Kernen for homomorfien ϕ: D_{4} → S_{4} fra Eksempel 5.11 består af de symmetrier der fixer alle kvadratets hjørner. Men det gør kun identiteten og derfor er ker ϕ = {e} den trivielle gruppe og ϕ er en monomorfi. Dette viser (Opgave 34), at permutationsgruppen S_{4} indeholder en undergruppe isomorf med kvadratets symmetrigruppe D_{4}.

Bemærkning 5.17. Lad G og H være endelige grupper af samme orden (f.eks. G = H) og ϕ: G → H en homomorfi mellem dem. Da gælder:

ϕ er en isomorfi

⇔ϕ er en epimorfi
⇔ϕ er en monomorfi
⇔ ker ϕ = {e}.

Dette følger ved at kombinere Sætning 5.15 med Skuffeprincippet 1.6.

Vi viser nu, at ordenen af en undergruppe (og ordenen af et element) i en endelig gruppe er divisor i hele gruppens orden.

Sætning 5.18 (Lagranges Sætning). Ordenen af en undergruppe af en endelig gruppe går op i gruppens orden.

Bevis. Lad G være en endelig gruppe og H en undergruppe af G. Vi ønsker at vise at |H| går op i |G|.

For g ∈ G, lad gH = {gh | h ∈ H} være mængden af alle produkter af g med et element fra undergruppen H. Læg mærke til, at hvis to af disse mængder skærer hinanden, da er de identiske:

g_{1}H ∩ g_{2}H ≠ ∅ ⇔ g_{1}H = g_{2}H, g_{1}, g_{2} ∈ G.

Denne egenskab medfører, at der findes g_{1}, …, g_{r} ∈ G så

G = g_{1}H ∪ ⋯ ∪ g_{r}H  (5.19)

er en opsplitning af G i disjunkte delmængder.

Vælg nemlig først et element g_{1} ∈ G. Hvis g_{1}H = G, er vi færdige. Hvis ikke, vælg g_{2} ∈ G \ g_{1}H. Da er g_{1}H ∪ g_{2}H en disjunkt foreningsmængde. Hvis g_{1}H ∪ g_{2}H = G, er vi færdige. Hvis ikke, vælg g_{3} ∈ G \ (g_{1}H ∪ g_{2}H). Denne proces må stoppe efter et endeligt antal skridt, da G er endelig.

Bemærk nu at mængden g_{i}H indeholder præcis lige så mange elementer som H. For der findes nemlig en bijektion H ⟶g_{i}H givet ved h ⟶g_{i}h (hvad er den inverse?). Den disjunkte opsplitning (5.19) viser derfor, at |G| = r|H|.

Vi skal til sidst se en anvendelse af Lagranges sætning på elementorden.

Definition 5.20. Lad g ∈ G være et element i gruppen G. Vi siger, at g har endelig orden, hvis der findes et naturligt tal n, så g^{n} = e. Det mindste naturlige tal med denne egenskab kaldes for ordenen af g, og det betegnes med ord_{G} g. Hvis g ikke har endelig orden, siges g at have uendelig orden.

Det eneste element med orden 1 er neutralelementet. I symmetrigruppen D_{4} er ord_{D_{4}} s_{1} = 2 og ord_{D_{4}} d_{1} = 4.

Øvelse 5.21. For ethvert element g af endelig orden gælder

• g^{ord_{G} g} = e.

• For ethvert helt tal m er g^{m} = g^{r}, hvor r er resten ved division af m med ord_{G} g.

Eksempel 5.22. Kernen for homomorfien ϕ_{g}: ℤ → G fra Eksempel 5.6 er undergruppen

ker ϕ_{g} = {n ∈ ℤ | g^{n} = e}

af ℤ og billedet er undergruppen

im ϕ_{g} = {g^{n} | n ∈ ℤ}

frembragt af g (som ofte betegnes med ⟨g⟩). Bemærk, at

ϕ_{g} er ikke-injektiv ⇔ g har endelig orden

og at hvis g har endelig orden n, da frembringer g en undergruppe

im ϕ_{g} = ⟨g⟩ = {e, g, g^{2}, …, g^{n−1}}

af orden n. Vi kan altså sige, at

ord_{G} g = min{n ∈ ℕ | g^{n} = e} = |⟨g⟩| og ker ϕ_{g} = (ord_{G} g)ℤ

når g har endelig orden.

Sætning 5.23. Lad G være en endelig gruppe og g et element i G. Da gælder 1. g har endelig orden.

2. ord_{G} g går op i |G|.

3. g^{|G|} = e.

Bevis. Dette følger umiddelbart af det foregående fordi

1. Homomorfien ϕ_{g}: ℤ → G kan ikke være injektiv, da G er en endelig gruppe.

2. ord_{G} g, som er lig med ordenen af undergruppen ⟨g⟩ frembragt af g, går op i gruppens orden ifølge Lagranges Sætning.

3. g^{|G|} = g^{0} = e, da resten ved division af |G| med ord_{G} g er 0.

Øvelse 5.24. Vis, at ord_{G×H}(g, h) = mfm(ord_{G} g, ord_{H} h), hvis gruppeelementerne g ∈ G og h ∈ H begge har endelig orden. Find f.eks. ker ϕ_{(g,h)} og benyt Eksempel 5.22

6. Modulær aritmetik

Lad n ≥ 1 være et naturligt tal. Vi siger, at de to hele tal x og y er kongruente modulo n, x ≡ y mod n, hvis n går op i differensen x − y. Det kan udtrykkes på flere ækvivalente måder: De syv påstande

• x ≡ y mod n

• n|x − y

• n|y − x

• der findes et helt tal s ∈ ℤ så y = x + ns

• der findes et helt tal t ∈ ℤ så x = y + nt • x og y har samme rest ved division med n

• x + nℤ = y + nℤ er alle ensbetydende.

Mængden x + nℤ, n-tabellen afsat ud fra x, består af alle hele tal, der har samme rest ved division med n som x har. Den kaldes for restklassen af x modulo n og betegnes også med \underline{x}_{n} eller blot \underline{x}; dvs.

\underline{x}_{n} = x + nℤ
= {y | der findes et s ∈ ℤ så y = x + ns}
= {…, x − 2n, x − n, x, x + n, x + 2n, … }

Relationen x ≡ y mod n har en hel del til fælles med lighedstegnet:

Proposition 6.1. Lad x, y og z være hele tal. Da gælder:

1. x ≡ x mod n

2. x ≡ y mod n ⇒ y ≡ x mod n

3. Hvis x ≡ y mod n og y ≡ z mod n, da er x ≡ z mod n

Vi udtrykker indholdet af Proposition 6.1 ved at sige, at x ≡ y mod n er en ækvivalensrelation.

Øvelse 6.2. Vis, at

x ≡ y mod n ⇔ \frac{x}{d} ≡ \frac{y}{d} mod \frac{n}{d}

hvis d går op i alle de tre tal x, y og n. (Eller regn den mere generelle Opgave 61.)

Da restklassen \underline{0}_{n} består af alle tal, der får resten 0 ved division med n, restklassen \underline{1}_{n} består af alle tal, der får resten 1 ved division med n, osv., indtil restklassen \underline{n − 1}_{n}, som består af alle tal, der får resten n − 1 ved division med n, ser vi, at de hele tal

ℤ = \underline{0} ∪ \underline{1} ∪ ⋯ ∪ \underline{n − 1} = (0 + nℤ) ∪ (1 + nℤ) ∪ ⋯ ∪ ((n − 1) + nℤ)

kan skrives som den disjunkte foreningsmængde af de n restklasser modulo n. Vi har altså n restklasser modulo n, og vi skriver,

ℤ/n = \{\underline{0}, \underline{1}, …, \underline{n − 1}\}

for mængden af de n restklasser. (Ja, du så rigtigt: ℤ/n er en mængde af mængder.) Bemærk, at \underline{n} = \underline{0}, \underline{n + 1} = \underline{1}, ja, at

\underline{x} = \underline{y} ⇔ x ≡ y mod n

for alle hele tal x, y ∈ ℤ.

Eksempel 6.3. Der er 12 restklasser modulo 12. Vi har \underline{13} = \underline{1}, \underline{14} = \underline{2}, …, \underline{23} = \underline{11}, \underline{24} = \underline{0}.

Vi ønsker at definere addition og multiplikation af restklasser modulo n. Det er fristende at sætte

\underline{x} + \underline{y} = \underline{x + y}

og

\underline{x} · \underline{y} = \underline{xy}

men der er et problem her fordi restklasserne har mange forskellige repræsentanter. (Tænk lige over det!) Problemet forsvinder imidlertid, så snart vi har vist:

Lemma 6.4. Antag at x_{1} ≡ x_{2} mod n og y_{1} ≡ y_{2} mod n. Da er

1. x_{1} + y_{1} ≡ x_{2} + y_{2} mod n

2. x_{1}y_{1} ≡ x_{2}y_{2} mod n

Bevis. Da n går op i x_{2} − x_{1} og i y_{2} − y_{1} vil n også gå op i

(x_{1} + y_{1}) − (x_{2} + y_{2}) = (x_{1} − x_{2}) + (y_{1} − y_{2})

og i

x_{1}y_{1} − x_{2}y_{2} = x_{1}y_{1} − x_{1}y_{2} + x_{1}y_{2} − x_{2}y_{2} = x_{1}(y_{1} − y_{2}) + (x_{1} − x_{2})y_{2}.

Dette viser de to påstande.

Det er nu ganske let at verificere de sædvanlige regneregler

\underline{x} + \underline{y} = \underline{y} + \underline{x}
(\underline{x} + \underline{y}) + \underline{z} = \underline{x} + (\underline{y} + \underline{z})
\underline{0} + \underline{x} = \underline{x}
\underline{x} + \underline{−x} = \underline{0}
\underline{x} · \underline{y} = \underline{y} · \underline{x}
(\underline{x} · \underline{y}) · \underline{z} = \underline{x} · (\underline{y} · \underline{z})
\underline{1} · \underline{x} = \underline{x}
\underline{x} · (\underline{y} + \underline{z}) = \underline{x} · \underline{y} + \underline{x} · \underline{z}

(Disse regneregler gør mængden af restklasser modn til en ring.) Idet vi nu bare fokuserer på additionen og ignorerer multiplikationen, får vi umiddelbart:

Sætning 6.5. (ℤ/n, +) er en abelsk gruppe, den abelske gruppe af restklasser modulo n, af orden n med neutralelement \underline{0} og invers −\underline{x} = \underline{−x}.

Vi kan nu tillade os at bruge de regneregler vi fandt i forrige afsnit (4.6, 4.7) i gruppen (ℤ/n, +).

Eksempel 6.6. Cayley tabellen for den abelske gruppe (ℤ/6, +) af retsklasser modulo 6

\begin{matrix}(ℤ/6, +) & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \end{matrix}

viser, at ℤ/6 indeholder undergrupperne {0, 3} ≅ ℤ/2 og {0, 2, 4} ≅ ℤ/3.

Bemærkning 6.7. Her er nogle småbemærkninger:

• Afbildningen R_{n}: ℤ → ℤ/n, som sender x ∈ ℤ i R_{n}(x) = \underline{x} ∈ ℤ/n, er en epimorfi med kerne nℤ.

• Faktisk er R_{n} blot et nyt navn for ϕ\underline{1}, så det følger, at ord_{ℤ/n} \underline{1} = n, dvs. at ℤ/n = ⟨\underline{1}⟩ er frembragt af elementet \underline{1} ∈ ℤ/n.

• Lad g ∈ G være et gruppeelement af endelig orden. Afbildningen ℤ/(ord_{G} g) ⟶ ⟨g⟩ som sender \underline{x} i g^{x} er en (veldefineret!) isomorfi.

Vi betragter nu den multiplikative struktur på ℤ/n.

Øvelse 6.8. Betragt ligningen \underline{4} · \underline{x} = \underline{6} i mængden af restklasser modulo n. Vis, at

1. Hvis n = 8, er der ingen løsninger.

2. Hvis n = 10, er der netop to løsninger.

3. Hvis n = 15, er der netop en løsning.

Mutliplikationen i ℤ/n er godt nok associativ, og \underline{1} er et neutralelement, men ikke alle elementer har inverse. F.eks. har \underline{0} aldrig nogen invers, og \underline{2} har ikke noget inverst element i ℤ/6. Så (ℤ/n, ·) er ikke en gruppe. Men indskrænker vi til mængden (ℤ/n)^{∗} af multiplikativt invertible elementer (idet vi bemærker, at produktet af to invertible elementer er invertibelt) ja, da får vi faktisk en gruppe. Gruppen af multiplikativt invertible restklasser modulo n betegnes ((ℤ/n)^{∗}, ·).

Eksempel 6.9. Cayley tabellen for ((ℤ/4), ·)

\begin{matrix}(ℤ/4, ·) & 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 \\ 2 & 0 & 2 & 0 & 2 \\ 3 & 0 & 3 & 2 & 1 \end{matrix}

viser, at (ℤ/4)^{∗} = \{\underline{1}, \underline{3}\} ≅ ℤ/2.

Vi bestemmer nu elementerne i gruppen (ℤ/n)^{∗}. Bemærk først, at multiplikation med m ∈ ℤ er en endomorfi af (en vilkårlig abelsk gruppe og specielt af) ℤ/n: Multiplikation med m sender \underline{x} ∈ ℤ/n i m\underline{x} = \underline{m} · \underline{x} = \underline{mx}.

Lemma 6.10. Lad m og n være hele tal. Da er følgende betingelser ækvivalente:

1. \underline{m} har en multiplikativ invers i ℤ/n.

2. Multiplikation med m, m: ℤ/n → ℤ/n, er en automorfi.

3. sfd(m, n) = 1. Hvis en af disse betingelser er opfyldt, og sm + tn = 1, så er \underline{m}^{−1} = \underline{s}.

Bevis. Vi viser (1) ⇒ (2) ⇒ (3) ⇒ (1). Antag (1). Vælg \underline{s} så \underline{m} · \underline{s} = \underline{1}. Da viser

\underline{y} = \underline{1} · \underline{y} = \underline{m} · \underline{s} · \underline{y} = \underline{m} · (\underline{s} · \underline{y}) = \underline{m} · \underline{sy} = m(\underline{sy})

at multiplikation med m er en epimorfi, og derfor (5.17) en automorfi.

Antag (2). Da multiplikation med m er en automorfi, findes s ∈ ℤ så \underline{m}·\underline{s} = \underline{1} eller \underline{1 − ms} = \underline{0}, dvs, at 1 − ms er et multiplum af n, og (I.2.37) at m og n er indbyrdes primiske.

Antag (3). Da sfd(m, n) = 1 findes (I.2.37) hele tal s, t ∈ ℤ med ms + nt = 1. Så er \underline{1} = \underline{ms + nt} = \underline{ms} + \underline{ns} = \underline{ms} = \underline{m} · \underline{s}, så \underline{s} er en multiplikativ invers til \underline{m}.

Eksempel 6.11. (ℤ/6)^{∗} = \{\underline{1}, \underline{5}\} er isomorf med ℤ/2. (ℤ/5)^{∗} = \{\underline{1}, \underline{2}, \underline{3}, \underline{4}\} er isomorf med ℤ/4: Overvej, at ϕ: ℤ/4 → (ℤ/5)^{∗} givet ved ϕ(\underline{x}) = \underline{2}^{x} er en (veldefineret!) isomorfi. (ℤ/9)^{∗} = \{\underline{1}, \underline{2}, \underline{4}, \underline{5}, \underline{7}, \underline{8}\} er en gruppe af orden 6.

Definition 6.12. Funktionen ϕ givet ved

ϕ(n) = |(ℤ/n)^{∗}|

kaldes for Eulers ϕ-funktion.

Eulers ϕ-funktion er altså givet ved at ϕ(n) er antallet af naturlige tal m med 0 < m < n som er indbyrdes primiske med n. F. eks. er ϕ(4) = 2ϕ(6). Specielt er ϕ(p) = p − 1 for ethvert primtal p. Du kan finde mere om beregningen af Eulers ϕ-funktion i opgaverne.

Sætning 6.13 (Eulers Sætning). Lad n være et naturligt tal og m et helt tal, som er indbyrdes primisk med n. Så er

m^{ϕ(n)} ≡ 1 mod n

Bevis. Anvend Sætning 5.23 på \underline{m} ∈ (ℤ/n)^{∗}.

Korollar 6.14 (Fermats lille sætning). Lad p være et primtal og x et helt tal som ikke er divisibelt med p. Da er

x^{p−1} ≡ 1 mod p

Bevis. ϕ(p) = p − 1.

Eksempel 6.15. 2^{10} ≡ 1 mod 11, 31 | 20^{30} − 1, 378^{1060} − 1 er deleligt med Det næste eksempel handler om løsning af (lineære) ligninger i gruppen ℤ/n.

Eksempel 6.16. Lad m og n være naturlige tal med største fælles divisor d = sfd(m, n). Vælg hele tal s og t, så ms + nt = d.

Ligningen mx ≡ a mod n har en løsning, hvis og kun hvis a ∈ mℤ+nℤ = dℤ, dvs. hvis og kun hvis d går op i a.

Antag derfor, at d går op i a. Så gælder

mx ≡ a mod n ⇔ \frac{m}{d}x ≡ \frac{a}{d} mod \frac{n}{d}

⇔ \frac{sm}{d}x ≡ \frac{sa}{d} mod \frac{n}{d}

⇔ x ≡ \frac{sa}{d} mod \frac{n}{d}

hvor den første biimplikation er Øvelse 6.2, den anden skyldes Lemma 6.10, og den tredje kommer af at s\frac{m}{d} ≡ 1 mod \frac{n}{d} (se Lemma 6.10).

Øvelse 6.17. Brug Eksempel 6.16 og Eksempel 2.30 til at vise at

945x ≡ 525 mod 2415 ⇔ x ≡ 21 mod 23.

Øvelse 6.18. Lad m: ℤ/n → ℤ/n være endomorfien af ℤ/n givet ved multiplikation med m. Da er

im(m) = ⟨\underline{m}⟩ = \{\underline{0}, \underline{d}, 2\underline{d}, …, (\frac{n}{d} − 1)\underline{d}\} ≅ ℤ/(\frac{n}{d})

ker(m) = \{\underline{0}, \underline{\frac{n}{d}}, 2\underline{\frac{n}{d}}, …, (d − 1)\underline{\frac{n}{d}}\} = ⟨\underline{\frac{n}{d}}⟩ ≅ ℤ/d

hvor d = sfd(m, n) er den største fælles divisor af m og n. (Er det et tilfælde at produktet af kernens og billedets orden er lig med domænets orden?) Med andre ord, er ord_{ℤ/n} \underline{m} = |⟨\underline{m}|⟩ = \frac{n}{sfd(m,n)}.

7. Den kinesiske restklassesætning

Lad a og b være to naturlige tal. Betragt afbildningen

f: ℤ/(ab) ⟶ℤ/a × ℤ/b
\underline{x} ⟶(\underline{x}, \underline{x})

fra ℤ/(ab) ind i produktet af ℤ/a og ℤ/b. (Det fremgår ikke eksplicit af notationen, at det første \underline{x} er element i gruppen ℤ/(ab), det andet i ℤ/a og det tredje i ℤ/b.) Det fortjener lige en overvejelse at denne afbildning i det hele taget er veldefineret! (Hvad er problemet?) Selvom du selvfølgelig husker det, vil jeg lige minde dig om (Opgave 41), at codomænet er en abelsk gruppe med

(\underline{x_{1}}, \underline{y_{1}}) + (\underline{x_{2}}, \underline{y_{2}}) = (\underline{x_{1}} + \underline{y_{1}}, \underline{x_{2}} + \underline{y_{2}})

som gruppestruktur. Det er nu klart, at f er en homomorfi for

f(\underline{x} + \underline{y}) = f(\underline{x + y}) = (\underline{x + y}, \underline{x + y}) = (\underline{x} + \underline{y}, \underline{x} + \underline{y}) = (\underline{x}, \underline{x}) + (\underline{y}, \underline{y})
= f(\underline{x}) + f(\underline{y})

for alle \underline{x}, \underline{y} ∈ ℤ/(ab).

Lemma 7.1. Homomorfien f: ℤ/(ab) → ℤ/a × ℤ/b er en isomorfi, hvis og kun hvis a og b er indbyrdes primiske. I så fald er den inverse f^{−1} : ℤ/a × ℤ/b → ℤ/(ab) givet ved

f^{−1}(\underline{x}, \underline{y}) = bt\underline{x} + as\underline{y}, (\underline{x}, \underline{y}) ∈ ℤ/a × ℤ/b,

hvor de hele tal s og t er valgt (I.2.37), så as + bt = 1.

Bevis. Kernen for homomorfien f er billedet R_{ab}(aℤ ∩ bℤ) af undergruppen aℤ ∩ bℤ ⊆ ℤ ved afbildningen R_{ab}: ℤ ⟶ ℤ/(ab): x ⟶ \underline{x} fra Bemærkning 6.7. Altså gælder:

f er en isomorfi ⇔ ker f = \{\underline{0}\}
⇔ R_{ab}(aℤ ∩ bℤ) = \{\underline{0}\}
⇔ aℤ ∩ bℤ ⊆ ker R_{ab}
⇔ aℤ ∩ bℤ ⊆ abℤ
⇔ sfd(a, b) = 1

hvor vi har benyttet (5.17), (5.14), (6.7) og (I.2.37) (og i øvrigt holdt hovedet koldt).

Vi antager nu, at a og b er indbyrdes primiske hele tal og forsøger at finde den inverse til isomorfien f. Lad g: ℤ/a × ℤ/b → ℤ/(ab) være funktionen givet ved

g(\underline{x}, \underline{y}) = bt\underline{x} + as\underline{y}, (\underline{x}, \underline{y}) ∈ ℤ/a × ℤ/b,

hvor de hele tal s og t er valgt (I.2.37) så as + bt = 1. Det kræver en lille overvejelse, som jeg trygt overlader til dig, at vise, at g er veldefineret, og at g er en homomorfi. Idet vi benytter bl.a. regel (3) fra Proposition 4.7, får vi for alle \underline{x} ∈ ℤ/(ab),

(g ∘ f)(\underline{x}) = g(\underline{x}, \underline{x}) = bt\underline{x} + as\underline{x} = (bt + as)\underline{x} = \underline{x}  (7.2)

og for alle (\underline{x}, \underline{y}) ∈ ℤ/a × ℤ/b,

(f ∘ g)(\underline{x}, \underline{y}) = f(bt\underline{x} + as\underline{y}) = (bt\underline{x}, as\underline{y}) = ((1 − as)\underline{x}, (1 − bt)\underline{y}) = (\underline{x}, \underline{y})(7.3)

og derfor er f og g hinandens inverse.

Øvelse 7.4. Hvorfor kan den ene af udregningerne (7.2) og (7.3) udelades?

Alternativt bevis for 7.1. Antag, at a og b er indbyrdes primiske hele tal. Læg mærke til, at billedet im f = im ϕ_{(\underline{1},\underline{1})} = ⟨(\underline{1}, \underline{1})⟩ er undergruppen frembragt af (\underline{1}, \underline{1}) ∈ ℤ/a × ℤ/b, som har orden

|⟨(\underline{1}, \underline{1})⟩| = ord_{ℤ/a×ℤ/b}(\underline{1}, \underline{1}) = mfm(ord_{ℤ/a} \underline{1}, ord_{ℤ/b} \underline{1}) = mfm(a, b) = ab

ifølge Øvelse 5.24. Dette viser, at f er en epimorfi og derfor en isomorfi ifølge Skuffeprincippet 1.6. Den inverse f^{−1} findes som i det første bevis.

Antag dernæst, at a og b ikke er indbyrdes primiske. Så er \underline{mfm(a, b)} et element i ker f som ikke er lig med neutralelementet \underline{0}. Derfor (5.15) er f ikke injektiv, specielt ikke en isomorfi.

Sætning 7.5. Lad m_{1}, m_{2}, …, m_{r} være parvis indbyrdes primiske naturlige tal. Da er den naturlige homomorfi

f: ℤ/(m_{1}m_{2} … m_{r}) ⟶ℤ/m_{1} × ℤ/m_{2} × … ℤ/m_{r}
\underline{x} ⟶(\underline{x}, …, \underline{x})

en isomorfi.

Bevis. Vi benytter induktion efter antallet r af faktorer. Hvis r = 2 er vi tilbage i Lemma 7.1. Antag, at sætningen er sand for produkter med < r faktorer. Lad m = m_{1}m_{2} … m_{r} være et produkt af r parvis indbyrdes primiske faktorer. Bemærk først, at m_{1} og m_{2} … m_{r} er indbyrdes primiske. (Se Opgave 20.) Lemma 7.1 giver nu, at

ℤ/m ≅ ℤ/m_{1} × ℤ/(m_{2} … m_{r})

hvor

ℤ/(m_{2} … m_{r}) ≅ ℤ/m_{2} × ⋯ × ℤ/m_{r}

ifølge induktionsantagelsen.

Korollar 7.6. (Den Kinesiske Restklassesætning) Lad m_{1}, m_{2}, …, m_{r} være parvis indbyrdes primiske naturlige tal og lad a_{1}, a_{2}, … a_{r} være hele tal. Der findes et helt tal a ∈ ℤ så

a ≡ a_{i} mod m_{i}

for alle i = 1, …, r.

Bevis. Vælg a så \underline{a} ∈ ℤ/(m_{1} … m_{r}) afbildes i (\underline{a_{1}}, …, \underline{a_{r}}) ∈ ℤ/m_{1} × ⋯ × ℤ/m_{r} ved isomorfien f fra Sætning 7.5.

Bemærkning 7.7. Den Kinesiske Restklassesætning, eller rettere Sætning 7.5, siger, at løsningen til ligningssystemet (bestående af r ligninger)

x ≡ a_{i} mod m_{i}, 1 ≤ i ≤ r,

er

x ≡ a mod m_{1} … m_{r}

hvor f(\underline{a}) = (\underline{a_{1}}, …, \underline{a_{r}}). Der siges intet eksplicit om, hvordan a findes, for f^{−1} er ikke eksplicit angivet. Dog ved vi fra Lemma 7.1 at i tilfældet r = 2 er

a = m_{2}s_{2}a_{1} + m_{1}s_{1}a_{2}

hvor s_{1} og s_{2} er valgt så m_{1}s_{1} + m_{2}s_{2} = 1. Ved en trinvis procedure kan man derfor faktisk finde a; se Eksempel 7.8.

Eksempel 7.8. Ligningssystemet

x ≡ 2 mod 5
x ≡ 4 mod 7
x ≡ 3 mod 6

er, da 1 = (−4)·5+3·7 ifølge Euklids algoritme, ækvivalent med ligningssystemet

x ≡ 32 mod 35
x ≡ 3 mod 6

som, da 1 = (−1) · 35 + 6 · 6, er ækvivalent med ligningen

x ≡ 207 mod 210.

Bemærkning 7.9. Programmeringssproget PASCAL kan kun behandle latterligt små hele tal. Den Kinesiske Restklassesætning kan anvendes til at udvide det tilladte område, idet man udnytter, at hvis man kan regne modulo p_{1}, …, p_{r}, da kan man også regne modulo p_{1} … p_{r}.

Vi kunne specielt anvende Sætning 7.5 på primfaktoropløsningen (I.3.8) af n og opnå en faktorisering af ℤ/n.

Korollar 7.10. Hvis n har primtalsfaktoriseringen

n = p_{1}^{α_{1}} … p_{r}^{α_{r}}

da er homomorfien

f: ℤ/n ⟶ℤ/p_{1}^{r_{1}} × ⋯ × ℤ/p_{r}^{α_{r}}
\underline{x} ⟶(\underline{x}, …, \underline{x})

en isomorfi.

Opgaver

Opgave 29. Lad g ∘ f: A → C være den sammensatte funktion af f: A → B og g: B → C. Vis, at

(g ∘ f)^{−1}(c) = f^{−1}(g^{−1}(c))

for alle c ∈ C. Vis også, at

g ∘ f er injektiv ⇒ f er injektiv
g ∘ f er surjektiv ⇒ g er surjektiv

Opgave 30. Vis, at sammensætningen af to surjektive (injektive) afbildninger er surjektiv (injektiv).

Opgave 31. Vis, at alle elementer i symmetrigruppen D_{4} er frembragt af d_{1} og s_{1}, dvs. at elle elementer kan skrives som produkter af de to elementer d_{1} og s_{1}.

Opgave 32. Lad f: D_{4} → D_{4} være afblildningen givet ved f(x) = x^{3}. Vis, at f er bijektiv. Er f en homomorfi?

Opgave 33. Definer c_{g}: G → G ved c_{g}(h) = ghg^{−1}. Er c_{g} en homomorfi? Er c_{g} en automorfi? Find c_{g} ∘ c_{h} og (c_{g})^{−1}.

Opgave 34. Vis, at enhver monomorfi ϕ: G → H bestemmer en isomorfi G ≅ ϕ(G) mellem domænet og billedet.

Opgave 35. Lad D_{3} betegne symmetrigruppen for en ligesidet trekant centreret i (0, 0). Hvad er ordenen af D_{3}? Opstil Cayley tabellen. Er D_{3} abelsk?

Opgave 36. Lad D_{n} betegne symmetrigruppen for en ligesidet n-kant centreret i (0, 0). Hvad er ordenen af D_{n}? Er D_{n} abelsk?

Opgave 37. Lad S_{n} betegne mængden af alle bijektive afbildninger af {1, 2, …, n} ind i sig selv. Vis, at S_{n} er en gruppe. Find |S_{n}|.

Opgave 38. Find Cayley tabellen for symmetrigruppen af et rektangel som ikke er et kvadrat. Hvad er gruppens orden? Er gruppen abelsk? Vis, at denne gruppe er isomorf med et produkt af to af sine undergrupper. (Har vi et generelt fænomen her?)

Opgave 39. Hvad er cirklens symmetrigruppe?

Opgave 40. Vis, at ligningerne xg = h og gx = h begge har netop en løsning i enhver gruppe.

Opgave 41. Lad (G, ·) og (H, ∗) være grupper. Vis, at produktet G × H på naturlig måde er en gruppe. (Husk at verificere betingelserne fra Definition 4.1!) Hvad er ordenen af produktgruppen hvis begge grupper er endelige? Vis, at produktgruppen er abelsk hvis (og kun hvis?) G og H er abelske.

Opgave 42. Vis, at G_{1} ×H_{1} er en undergruppe i G×H hvis G_{1} er en undergruppe i G og H_{1} en undergruppe i H. Er alle produktgruppens undergrupper af denne form?

Opgave 43. Opstil Cayley tabellen for ℤ/2 × ℤ/2 og for ℤ/2 × ℤ/3. Er ℤ/4 og ℤ/2 × ℤ/2 isomorfe? Er ℤ/6 og ℤ/2 × ℤ/3 isomorfe?

Opgave 44. Er ℤ/n^{2} og ℤ/n × ℤ/n isomorfe for noget n > 1? (Øvelse 6.18 kan måske være til nytte.)

Opgave 45. Find en undergruppe isomorf med ℤ/n i D_{n}.

Opgave 46. Konstruer en (interessant) gruppehomomorfi D_{n} ⟶S_{n}. Er din homomorfi en monomorfi?

Opgave 47. Vis at symmetrigruppen D_{3} fra Opgave 35 er isomorf med permutationsgruppen S_{3}.

Opgave 48. Vis, at enhver undergruppe af de hele tal ℤ har formen aℤ for et a ∈ ℤ. (Vink: (I.1.8), (I.2.1))

Opgave 49. Vis, at H ⊆ G er en undergruppe af G hvis og kun hvis

1. H ≠ ∅.

2. fg^{−1} ∈ H for alle f ∈ H og g ∈ H

Opgave 50. Bevis Proposition II.5.8.

Opgave 51. Lad ϕ: G → H være en homomorfi mellem to endelige grupper. Find en bijektion mellem ker ϕ = ϕ^{−1}(e) og originalmængden ϕ^{−1}(ϕ(g)) for g ∈ G, f.eks. ved at vise ϕ^{−1}(ϕ(g)) = g ker ϕ. Konkluder, at |G| = | ker ϕ|| im ϕ|.

Opgave 52. Hvor mange homomorfier ℤ/5 ⟶ℤ/7 findes der?

Opgave 53. Vis, at ℤ/n indeholder en undergruppe isomorf med ℤ/m hvis og kun hvis m går op i n. Hvis m | n, hvor mange undergrupper isomorfe med ℤ/m har ℤ/n? (Vink: (5.23), (6.18).)

Opgave 54. Vis, at (ℤ/5)^{∗} ≅ ℤ/4 og at (ℤ/7)^{∗} ≅ ℤ/6. Kan du ane et muligt generelt fænomen her?

Opgave 55. Find ϕ(n) for for 2 ≤ n ≤ 20.

Opgave 56. Vis, at ϕ(p^{r}) = |(ℤ/p^{r})^{∗}| = p^{r} − p^{r−1} = p^{r−1}(p − 1) for ethvert primtal p.

Opgave 57. Vis, at (ℤ/8)^{∗} er isomorf med ℤ/2 × ℤ/2.

Opgave 58. Find \sqrt{2} ⊆ (ℤ/7)^{∗}, dvs find alle x ∈ (ℤ/7)^{∗} som opfylder ligningen x^{2} = \underline{2}.

Opgave 59. Vis, at isomorfien fra Sætning 7.5 bestemmer en isomorfi

(ℤ/n)^{∗} ≅ (ℤ/p_{1}^{α_{1}})^{∗} × ⋯ × (ℤ/p_{r}^{α_{r}})^{∗}

og konkluder heraf at

ϕ(n) = ∏_{i=1}^{r} p_{i}^{α_{i}−1}(p_{i} − 1)

Opgave 60. (Uløst problem) Vis, at der for ethvert n ≥ 2 findes et m ≠ n så ϕ(m) = ϕ(n).

Opgave 61. Antag, at det hele tal c går op i a og b. Vis, at

a ≡ b mod n ⇔ \frac{a}{c} ≡ \frac{b}{c} mod \frac{n}{d}

hvor d = sfd(c, n) er den største fælles divisor af c og n. (Øvelse 6.2 indeholder et specialtilfælde.)

Opgave 62. Vis, at grupperne ℤ/9 × ℤ/15 og ℤ/45 × ℤ/3 er isomorfe.

Opgave 63. (Midtvej 95/96)

1. Find mængden af løsninger x ∈ ℤ til ligningen 3072x ≡ 3 mod 51.

2. Vis, at ligningen 3072x ≡ 4 mod 51 ikke har nogen løsninger x ∈ ℤ.

Opgave 64. Løs ligningerne

(a) 2x ≡ 4 mod 6 (c) 3x ≡ 4 mod 10
(b) 4x ≡ 6 mod 10 (d) 2x ≡ 3 mod 30

f.eks. ved at hente inspiration i Eksempel 6.16.

Opgave 65. Løs ligningerne

(a) 56x − 3 ≡ 133 mod 1324
(b) 200x − 12 ≡ 35x + 4 mod 1091

f.eks. ved at se tilbage på Opgave 10 og Eksempel 6.16.

Opgave 66. Find alle hele tal x så

(a) x ≡ 2 mod 5 og x ≡ 8 mod 14
(b) x ≡ 56 mod 123 og x ≡ 212 mod 712

f.eks. ved at benytte Bemærkning 7.7 og (for (b)) Øvelse 2.31.

Opgave 67. Find den inverse til isomorfien f fra Sætning 7.5 for r = 3. (Vink: Se Opgave 23.)

Opgave 68. Betragt homomorfien f: ℤ/(ab) → ℤ/a × ℤ/b givet ved f(\underline{x}) = (\underline{x}, \underline{x}) (som i Lemma 7.1) hvor (a, b) = (2, 5) eller (a, b) = (2, 6).

1. Find f(\underline{x}) for alle \underline{x} i de to tilfælde.

2. Vis, at billedet f(ℤ/(ab)) er isomorft med ℤ/ mfm(a, b) og at kernen ker f er isomorf med ℤ/ sfd(a, b) i de to tilfælde.

Opgave 69. Vis, at produktgruppen ℤ/m_{1} × ℤ/m_{2} indeholder en undergruppe isomorf med ℤ/ mfm(m_{1}, m_{2}).

Opgave 70. Lad m_{1} > 0 og m_{2} > 0 være naturlige tal med største fælles divisor d = sfd(m_{1}, m_{2}) og mindste fælles multiplum m = mfm(m_{1}, m_{2}). Betragt afbildningen f: ℤ → ℤ/m_{1} × ℤ/m_{2} givet ved f(x) = (\underline{x}, \underline{x}), dvs. f = ϕ_{(\underline{1},\underline{1})}.

1. Vis, at f er en homomorfi.

7. DEN KINESISKE RESTKLASSESÆTNING 45

2. Vis, at kernen for f er ker f = mℤ og at billedet er im f = \{(\underline{0}, \underline{0}), (\underline{1}, \underline{1}), 2(\underline{1}, \underline{1}), …, (m − 1)(\underline{1}, \underline{1})\} ≅ ℤ/m.

3. Vis, at im f også kan beskrives som undergruppen im f = \{(\underline{a_{1}}, \underline{a_{2}}) | a_{1} ≡ a_{2} mod d\}.

4. Konkluder, at der findes et x ∈ ℤ så

x ≡ a_{1} mod m_{1} og x ≡ a_{2} mod m_{2}

hvis og kun hvis a_{1} ≡ a_{2} mod d.

5. Find løsningsmængden til ligningssystemet i punkt (4).

46 2. GRUPPETEORI

Litteratur

[1] Ireland and Rosen, A classical introduction to modern number theory. Graduate Texts in Mathematics 84, Springer-Verlag, Berlin-Heidelberg-New York, 1990.

[2] C.R. Jordan and D.A. Jordan, Groups, Edward Arnold, London, 1994.

[3] C. Pomerance, A tale of two sieves, Notices Amer. Math. Soc. 43 (1996), 1473–1484.

[4] Joseph J. Rotmann, The theory of groups. An introduction, Allyn and Bacon, Boston, 1976.

[5] Harold N. Shapiro, Introduction to the theory of numbers, John Wiley and Sons, New York, 1983.