INHOUDSOPGAVE 1
Inhoudsopgave
1 De gehele getallen 3
1.1 Deling (met rest) . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Priemfactorontbinding . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Rekenen modulo N 16
2.1 Restklassen modulo N . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Eenheden modulo N . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 De Chinese reststelling . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Groepen en homomorfismen 29
3.1 Groepen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Ondergroepen . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Homomorfismen . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Permutatie-groepen 45
4.1 Bijecties op een verzameling . . . . . . . . . . . . . . . . . . . 45
4.2 Permutaties op n getallen . . . . . . . . . . . . . . . . . . . . 46
4.3 Even en oneven permutaties . . . . . . . . . . . . . . . . . . . 50
4.4 De alternerende groep . . . . . . . . . . . . . . . . . . . . . . 52
4.5 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5 Groepen van symmetrieën 56
5.1 een aantal matrixgroepen . . . . . . . . . . . . . . . . . . . . . 56
5.2 groepen van isometrieën . . . . . . . . . . . . . . . . . . . . . 58
5.3 De diëdergroepen. . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Symmetriegroepen van de platonische lichamen. . . . . . . . . 65
5.5 Automorfismen van een graaf . . . . . . . . . . . . . . . . . . 71
5.6 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6 Conjugatie, index en Sylow-groepen 75
6.1 conjugatie en index . . . . . . . . . . . . . . . . . . . . . . . . 75
6.2 Sylow ondergroepen . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
,INHOUDSOPGAVE 2
7 Normaaldelers en factorgroepen 87
7.1 Normaaldelers . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.2 Factorgroepen . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.3 Normaaldelers in de alternerende groep . . . . . . . . . . . . . 92
7.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8 Homomorfie– en isomorfiestellingen 97
8.1 homomorfismen vanuit een factorgroep . . . . . . . . . . . . . 97
8.2 isomorfismen vanuit een factorgroep . . . . . . . . . . . . . . . 99
8.3 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9 Eindig voortgebrachte abelse groepen 105
9.1 Eindig voortgebrachte groepen . . . . . . . . . . . . . . . . . . 105
9.2 Ondergroepen van vrije abelse groepen . . . . . . . . . . . . . 107
9.3 De structuur van eindig voortgebrachte abelse groepen . . . . 109
9.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
,1 DE GEHELE GETALLEN 3
1 De gehele getallen
In dit hoofdstuk houden we ons bezig met de verzameling van alle gehele ge-
tallen Z = {. . . , −2, −1, 0, 1, 2, 3, . . .}. Veel elementaire eigenschappen daar-
van zijn ons welbekend uit het lager– en middelbaar onderwijs. Wat daar
evenwel in de meeste gevallen niet gedaan wordt, is zulke eigenschappen ook
echt bewijzen. Dat doen we hier wel, en in latere hoofdstukken zal blijken
hoe dat weer te gebruiken is voor bijvoorbeeld een beter begrip van het re-
kenen met resten bij deling door een vast getal. Dat laatste kan dan op zijn
beurt gebruikt worden voor bijvoorbeeld het vinden van criteria die zeggen
of een gegeven groot getal een priemgetal is of niet. En zo zullen we hier en
in verdere hoofdstukken veel meer voorbeelden zien van soms vrij abstracte
definities en bewijzen, die later in concrete situaties heel goed toepasbaar
blijken te zijn.
1.1 Deling (met rest)
Al op de lagere school komen we sommen als 100 : 7 = 14 rest 2 tegen.
Achter dit soort opgaven ligt het volgende.
Stelling 1.1.1 (Deling met rest.) Laat a, b ∈ Z met b > 0. Dan bestaan er
q, r ∈ Z waarvoor
a = qb + r en 0 ≤ r < b.
Bovendien zijn deze q, r uniek.
Bewijs. We tonen eerst het bestaan van zulke q, r ∈ Z aan. Voor niet-
negatieve a kan dat bijvoorbeeld met volledige inductie: is a = 0 dan kunnen
we q = r = 0 nemen. Weten we dat a − 1 ≥ 0 te schrijven is als a − 1 = q̃b + r̃
met 0 ≤ r̃ < b, dan volgt a = q̃b + r̃ + 1. Er geldt uiteraard 0 ≤ r̃ + 1 ≤ b.
In het geval r̃ + 1 < b kunnen we dus q = q̃ en r = r̃ + 1 nemen. In het
resterende geval r̃ + 1 = b hebben we a = q̃b + r̃ + 1 = q̃b + b = (q̃ + 1)b + 0,
dus q = q̃ + 1 en r = 0 voldoen. Hiermee is volgens het principe van volledige
inductie voor a ≥ 0 de existentie van q, r aangetoond.
Is a < 0, dan is −a > 0, dus uit wat we zojuist bewezen hebben volgt
dat er q 0 , r0 zijn met −a = q 0 b + r0 en 0 ≤ r0 < b. Dan is a = (−q 0 )b − r0 =
(−q 0 − 1)b + (b − r0 ), dus we concluderen dat q = −q 0 en r = 0 voldoen in
het geval dat r0 = 0, en als r0 6= 0 dan kunnen we q = −q 0 − 1 en r = b − r0
nemen.
Nu nog de uniciteit. Stel dat a = q1 b + r1 = q2 b + r2 waarbij 0 ≤ r1 ≤
r2 < b. Dan volgt 0 ≤ r2 − r1 ≤ r2 < b, maar ook r2 − r1 = b(q1 − q2 ). Dus
moet r1 = r2 , want anders zou het een positief veelvoud van b zijn en we
, 1 DE GEHELE GETALLEN 4
hebben al gezien dat r2 − r1 < b. We concluderen dat ook b(q1 − q2 ) = 0, en
omdat b 6= 0 impliceert dit q1 = q2 . Hiermee is de stelling bewezen. 2
Opmerking 1.1.2 Als we wat kennis over reële getallen gebruiken, dan kan
een heel ander bewijs gegeven worden: deel de reële lijn op in intervallen met
lengte b, dus
R = . . . ∪ [−2b, −b) ∪ [−b, 0) ∪ [0, b) ∪ . . . . . .
Het getal a ∈ R ligt dan in één zo’n interval [qb, (q+1)b), en is dus te schrijven
als a = qb + r waarin 0 ≤ r < b.
Definitie 1.1.3 Laat a, b ∈ Z. We zeggen dat a het getal b deelt, als er een
q ∈ Z bestaat waarvoor geldt b = qa. Dit noteren we als a|b. Bestaat zo’n q
niet, dan schrijven we a 6 |b (en we zeggen: a deelt b niet).
In plaats van a deelt b wordt ook wel gezegd dat a een deler van b is, of
dat b een veelvoud van a is, of dat b deelbaar is door a. Bijvoorbeeld geldt
17| − 153 en 0|0 en −2 6 |101 en 0 6 |3.
We geven een aantal eenvoudige eigenschappen van deelbaarheid.
Propositie 1.1.4 Voor a, b, c ∈ Z geldt
1. Als a|b en b|c dan ook a|c.
2. Als a|b en a|c dan ook a|b ± c.
3. a|0 en 1|a.
4. 0|a dan en slechts dan als a = 0.
5. Als voor b 6= 0 geldt dat a|b, dan is |a| ≤ |b|.
Bewijs. Al deze eigenschappen volgen direct uit de definitie. Bijvoorbeeld
impliceert a|b en a|c dat er p, q ∈ Z bestaan waarvoor b = pa en c = qa, en
daaruit volgt dat b ± c = pa ± qa = (p ± q)a, met andere woorden a|b ± c. 2
Uit de laatste in Propositie 1.1.4 genoemde eigenschap volgt, dat een
geheel getal a 6= 0 slechts eindig veel delers heeft; de grootste daarvan is ui-
teraard |a|. Hebben we nog een getal, zeg b, dan hebben dus in het bijzonder
a en b slechts eindig veel delers gemeenschappelijk (twee van die gemeen-
schappelijke delers zijn natuurlijk 1 en −1). Iets dergelijks geldt wanneer we
kijken naar gemeenschappelijke veelvouden van twee gehele getallen a, b. Als
a of b nul is, dan volgt uit de vierde in Propositie 1.1.4 gegeven eigenschap
dat 0 het enige gemeenschappelijke veelvoud is. Geldt daarentegen ab 6= 0,
dan hebben a en b gemeenschappelijke positieve veelvouden, bijvoorbeeld
|ab|. Dit leidt tot de volgende definitie:
Inhoudsopgave
1 De gehele getallen 3
1.1 Deling (met rest) . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Priemfactorontbinding . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Rekenen modulo N 16
2.1 Restklassen modulo N . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Eenheden modulo N . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 De Chinese reststelling . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Groepen en homomorfismen 29
3.1 Groepen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Ondergroepen . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Homomorfismen . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Permutatie-groepen 45
4.1 Bijecties op een verzameling . . . . . . . . . . . . . . . . . . . 45
4.2 Permutaties op n getallen . . . . . . . . . . . . . . . . . . . . 46
4.3 Even en oneven permutaties . . . . . . . . . . . . . . . . . . . 50
4.4 De alternerende groep . . . . . . . . . . . . . . . . . . . . . . 52
4.5 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5 Groepen van symmetrieën 56
5.1 een aantal matrixgroepen . . . . . . . . . . . . . . . . . . . . . 56
5.2 groepen van isometrieën . . . . . . . . . . . . . . . . . . . . . 58
5.3 De diëdergroepen. . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.4 Symmetriegroepen van de platonische lichamen. . . . . . . . . 65
5.5 Automorfismen van een graaf . . . . . . . . . . . . . . . . . . 71
5.6 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6 Conjugatie, index en Sylow-groepen 75
6.1 conjugatie en index . . . . . . . . . . . . . . . . . . . . . . . . 75
6.2 Sylow ondergroepen . . . . . . . . . . . . . . . . . . . . . . . . 80
6.3 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
,INHOUDSOPGAVE 2
7 Normaaldelers en factorgroepen 87
7.1 Normaaldelers . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.2 Factorgroepen . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.3 Normaaldelers in de alternerende groep . . . . . . . . . . . . . 92
7.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8 Homomorfie– en isomorfiestellingen 97
8.1 homomorfismen vanuit een factorgroep . . . . . . . . . . . . . 97
8.2 isomorfismen vanuit een factorgroep . . . . . . . . . . . . . . . 99
8.3 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9 Eindig voortgebrachte abelse groepen 105
9.1 Eindig voortgebrachte groepen . . . . . . . . . . . . . . . . . . 105
9.2 Ondergroepen van vrije abelse groepen . . . . . . . . . . . . . 107
9.3 De structuur van eindig voortgebrachte abelse groepen . . . . 109
9.4 Opgaven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
,1 DE GEHELE GETALLEN 3
1 De gehele getallen
In dit hoofdstuk houden we ons bezig met de verzameling van alle gehele ge-
tallen Z = {. . . , −2, −1, 0, 1, 2, 3, . . .}. Veel elementaire eigenschappen daar-
van zijn ons welbekend uit het lager– en middelbaar onderwijs. Wat daar
evenwel in de meeste gevallen niet gedaan wordt, is zulke eigenschappen ook
echt bewijzen. Dat doen we hier wel, en in latere hoofdstukken zal blijken
hoe dat weer te gebruiken is voor bijvoorbeeld een beter begrip van het re-
kenen met resten bij deling door een vast getal. Dat laatste kan dan op zijn
beurt gebruikt worden voor bijvoorbeeld het vinden van criteria die zeggen
of een gegeven groot getal een priemgetal is of niet. En zo zullen we hier en
in verdere hoofdstukken veel meer voorbeelden zien van soms vrij abstracte
definities en bewijzen, die later in concrete situaties heel goed toepasbaar
blijken te zijn.
1.1 Deling (met rest)
Al op de lagere school komen we sommen als 100 : 7 = 14 rest 2 tegen.
Achter dit soort opgaven ligt het volgende.
Stelling 1.1.1 (Deling met rest.) Laat a, b ∈ Z met b > 0. Dan bestaan er
q, r ∈ Z waarvoor
a = qb + r en 0 ≤ r < b.
Bovendien zijn deze q, r uniek.
Bewijs. We tonen eerst het bestaan van zulke q, r ∈ Z aan. Voor niet-
negatieve a kan dat bijvoorbeeld met volledige inductie: is a = 0 dan kunnen
we q = r = 0 nemen. Weten we dat a − 1 ≥ 0 te schrijven is als a − 1 = q̃b + r̃
met 0 ≤ r̃ < b, dan volgt a = q̃b + r̃ + 1. Er geldt uiteraard 0 ≤ r̃ + 1 ≤ b.
In het geval r̃ + 1 < b kunnen we dus q = q̃ en r = r̃ + 1 nemen. In het
resterende geval r̃ + 1 = b hebben we a = q̃b + r̃ + 1 = q̃b + b = (q̃ + 1)b + 0,
dus q = q̃ + 1 en r = 0 voldoen. Hiermee is volgens het principe van volledige
inductie voor a ≥ 0 de existentie van q, r aangetoond.
Is a < 0, dan is −a > 0, dus uit wat we zojuist bewezen hebben volgt
dat er q 0 , r0 zijn met −a = q 0 b + r0 en 0 ≤ r0 < b. Dan is a = (−q 0 )b − r0 =
(−q 0 − 1)b + (b − r0 ), dus we concluderen dat q = −q 0 en r = 0 voldoen in
het geval dat r0 = 0, en als r0 6= 0 dan kunnen we q = −q 0 − 1 en r = b − r0
nemen.
Nu nog de uniciteit. Stel dat a = q1 b + r1 = q2 b + r2 waarbij 0 ≤ r1 ≤
r2 < b. Dan volgt 0 ≤ r2 − r1 ≤ r2 < b, maar ook r2 − r1 = b(q1 − q2 ). Dus
moet r1 = r2 , want anders zou het een positief veelvoud van b zijn en we
, 1 DE GEHELE GETALLEN 4
hebben al gezien dat r2 − r1 < b. We concluderen dat ook b(q1 − q2 ) = 0, en
omdat b 6= 0 impliceert dit q1 = q2 . Hiermee is de stelling bewezen. 2
Opmerking 1.1.2 Als we wat kennis over reële getallen gebruiken, dan kan
een heel ander bewijs gegeven worden: deel de reële lijn op in intervallen met
lengte b, dus
R = . . . ∪ [−2b, −b) ∪ [−b, 0) ∪ [0, b) ∪ . . . . . .
Het getal a ∈ R ligt dan in één zo’n interval [qb, (q+1)b), en is dus te schrijven
als a = qb + r waarin 0 ≤ r < b.
Definitie 1.1.3 Laat a, b ∈ Z. We zeggen dat a het getal b deelt, als er een
q ∈ Z bestaat waarvoor geldt b = qa. Dit noteren we als a|b. Bestaat zo’n q
niet, dan schrijven we a 6 |b (en we zeggen: a deelt b niet).
In plaats van a deelt b wordt ook wel gezegd dat a een deler van b is, of
dat b een veelvoud van a is, of dat b deelbaar is door a. Bijvoorbeeld geldt
17| − 153 en 0|0 en −2 6 |101 en 0 6 |3.
We geven een aantal eenvoudige eigenschappen van deelbaarheid.
Propositie 1.1.4 Voor a, b, c ∈ Z geldt
1. Als a|b en b|c dan ook a|c.
2. Als a|b en a|c dan ook a|b ± c.
3. a|0 en 1|a.
4. 0|a dan en slechts dan als a = 0.
5. Als voor b 6= 0 geldt dat a|b, dan is |a| ≤ |b|.
Bewijs. Al deze eigenschappen volgen direct uit de definitie. Bijvoorbeeld
impliceert a|b en a|c dat er p, q ∈ Z bestaan waarvoor b = pa en c = qa, en
daaruit volgt dat b ± c = pa ± qa = (p ± q)a, met andere woorden a|b ± c. 2
Uit de laatste in Propositie 1.1.4 genoemde eigenschap volgt, dat een
geheel getal a 6= 0 slechts eindig veel delers heeft; de grootste daarvan is ui-
teraard |a|. Hebben we nog een getal, zeg b, dan hebben dus in het bijzonder
a en b slechts eindig veel delers gemeenschappelijk (twee van die gemeen-
schappelijke delers zijn natuurlijk 1 en −1). Iets dergelijks geldt wanneer we
kijken naar gemeenschappelijke veelvouden van twee gehele getallen a, b. Als
a of b nul is, dan volgt uit de vierde in Propositie 1.1.4 gegeven eigenschap
dat 0 het enige gemeenschappelijke veelvoud is. Geldt daarentegen ab 6= 0,
dan hebben a en b gemeenschappelijke positieve veelvouden, bijvoorbeeld
|ab|. Dit leidt tot de volgende definitie:
