Hoofdstuk 7
Congruenties in actie
7.1
Het aantal inverteerbare restklassen
We pakken hier de vraag op waarmee we in het vorige hoofdstuk ge¨eindigd zijn,
namelijk hoeveel inverteerbare restklassen modulo M zijn er? Laten we dit aantal
om te beginnen maar een naam geven, ϕ(M ). Deze funktie van M staat bekend
als de ϕ-funktie van Euler, of ook Euler’s totientfunktie. Verder defini¨eren we
ϕ(1) = 1. Volgens Stelling 6.3.2 kunnen we ϕ(M ) nu ook omschrijven als het
aantal gehele getallen n met 0 < n ≤ M en ggd(n, M ) = 1. Om enigszins
een idee te krijgen van het verloop van ϕ(n) volgt hier een tabel van ϕ(m) voor
m = 1, . . . , 16,
m
ϕ(m)
1 2
1 1
3
2
4
2
5
4
6
2
7
6
8
4
9 10
6 4
11 12
10 4
13 14
12 6
15
8
16
8
Een nogal grillige funktie dus. Merk echter op dat als p priem is, dan ϕ(p) = p−1.
Dit is duidelijk. Alle getallen 1, 2, . . . , p−1 zijn relatief priem met p. Verder geldt
ook dat ϕ(pk ) = pk − pk−1 voor elk priemgetal p en elke k ∈ N. Dit is ook niet
lastig. Immers ϕ(pk ) is gelijk aan pk min het aantal gehele getallen in het interval
[1, pk ] dat een deler gemeen heeft met pk . Merk op dat een getal n een deler
gemeen heeft met pk precies dan als n deelbaar is door p. Het aantal p-vouden
in het interval [1, pk ] is gelijk aan pk−1 . Dus ϕ(pk ) = pk − pk−1 .
In het bijzonder volgt uit het voorgaande dat voor p priem,
ϕ(1) + ϕ(p) + ϕ(p2 ) + · · · + ϕ(pk ) = 1 + p − 1 + p2 − p + · · · + pk − pk−1 = pk .
Dit is een speciaal geval van de algemenere eigenschap dat voor elke n ∈ N geldt,
∑
ϕ(d) = n.
d|n
Dit kunnen we als volgt zien. Met Vd geven we de verzameling van gehele getallen
in het interval [1, n] aan waarvan het ggd met n precies gelijk is aan d. Als
46
7.1. HET AANTAL INVERTEERBARE RESTKLASSEN
47
ggd(m, n) = d dan weten we dat ggd(m/d, n/d) = 1. Het aantal elementen in de
verzameling Vd is dus gelijk aan ϕ(n/d). Verder is {1, 2, . . . , n} de vereniging van
alle Vd met d|n. Dus
n=
∑
d|n
|Vd | =
∑
ϕ(n/d) =
∑
d|n
ϕ(d).
d|n
Met de notatie |Vd | bedoelen we hier het aantal elementen van Vd .
Tenslotte heeft de ϕ-funktie de volgende multiplicatieve eigenschap. Er geldt
namelijk ϕ(mn) = ϕ(m)ϕ(n) zodra ggd(m, n) = 1. Voor het bewijs hiervan
gebruiken we de chinese reststelling. Beschouw de verzameling A van alle gehele
getallen a met 1 ≤ a ≤ mn die relatief priem zijn met mn. Zij B de verzameling
van alle geordende paren (b, c) met 1 ≤ b ≤ m, 1 ≤ c ≤ n en ggd(b, m) = 1,
ggd(c, n) = 1. Tussen A en B bestaat een 1-1-duidig verband. Immers met a ∈ A
correspondeert het tweetal resten bij deling van a door m respectievelijk n. Dit
tweetal resten vormt een element van B. Omgekeerd kunnen we met de chinese
reststelling bij elk paar (b, c) ∈ B een element a ∈ A vinden z´o dat a ≡ b (mod m)
en a ≡ c (mod n). Tussen haakjes, aan de voorwaarde ggd(m, n) = 1 voor gebruik
van de chinese reststelling is voldaan.
Het aantal elementen in A is ϕ(mn). Het aantal elementen in B is ϕ(m)ϕ(n).
Dus volgt uit het 1-1-duidig verband tussen beide verzamelingen dat ϕ(mn) =
ϕ(m)ϕ(n).
2
We vatten de aldus gevonden resultaten samen,
Stelling 7.1.1 Zij ϕ(m) het aantal gehele getallen k die voldoen aan 1 ≤ k ≤ m
en ggd(m, k) = 1. Dan gelden de volgende eigenschappen
1. ϕ(pk ) = pk − pk−1 voor elk priemgetal p en elke k ∈ N.
∑
2.
d|n ϕ(d) = n voor elke n ∈ N.
3. ϕ(mn) = ϕ(m)ϕ(n) voor elk tweetal m, n ∈ N met ggd(m, n) = 1.
Een belangrijk gevolg is een recept om ϕ(m) uit te rekenen,
Gevolg 7.1.2 Stel m = pk11 pk22 · · · pkr r . Dan geldt
ϕ(m) = (pk11 − pk11 −1 ) · · · (pkr r − pkr r −1 ).
Anders geschreven,
ϕ(m) = m
∏ (
p|m
p priem
1
1−
p
)
.
48
HOOFDSTUK 7. CONGRUENTIES IN ACTIE
We kunnen dit aantonen door herhaald gebruik te maken van de multiplicatieve
eigenschap van ϕ,
ϕ(m) = ϕ(pk11 )ϕ(pk22 ) · · · ϕ(pkr r )
= (pk11 − pk11 −1 ) · · · (pkr r − pkr r −1 )
(
) (
)
1
1
k1
kr
··· 1 −
= p 1 · · · pr 1 −
p1
pr
)
∏ (
1
= m
1−
p
p|m
p priem
2
7.2
De stelling van Euler
De volgende stelling is ´e´en van de fundamentele stellingen in het congruentierekenen en heeft een groot aantal toepassingen. Aan deze toepassingen zullen we in
de loop van dit boek ook aandacht besteden.
Stelling 7.2.1 Zij M ∈ Z≥2 . Dan geldt voor elke a ∈ Z met ggd(a, M ) = 1 dat
aϕ(M ) ≡ 1 (mod M )
Het bewijs van deze stelling is van een bewonderenswaardige elegantie. Geef de
restklassen van (Z/M Z)∗ aan met
b1 (mod M ), b2 (mod M ), . . . , bϕ(M ) (mod M )
We vermenigvuldigen elk van deze restklassen met a. De verzameling restklassen
ab1 (mod M ), ab2 (mod M ), . . . , abϕ(M ) (mod M )
is weer precies (Z/M Z)∗ . Alleen is door vermenigvuldiging met a de volgorde
van de elementen door elkaar gegooid. De produkten van de elementen uit deze
verzamelingen zijn echter wel gelijk,
b1 b2 · · · bϕ(M ) ≡ ab1 ab2 · · · abϕ(M ) (mod M )
≡ aϕ(M ) b1 b2 · · · bϕ(M ) (mod M )
Delen we aan beide zijden de inverteerbare restklassen bi weg dan houden we
1 ≡ aϕ(M ) (mod M )
over.
2
Een speciaal geval van deze stelling hebben we al eens eerder gezien. Als we
M = p priem nemen dan vinden we
7.3. ORDES
49
Gevolg 7.2.2 Zij p priem en a ∈ Z niet deelbaar door p. Dan geldt,
ap−1 ≡ 1 (mod p)
Dit is de kleine stelling van Fermat die we al eerder tegenkwamen, zie Stelling
5.1.3. Het bewijs berust nu echter op het elegante bewijs van de stelling van
Euler, hetgeen bevredigender is dan het folkloristische bewijs dat we in Hoofdstuk
5 gaven.
In verband met de kleine stelling van Fermat vermelden we hier het volgende, nog
onopgeloste, probleem. We weten dat p een deler is van 2p − 2 voor elke priem
p. Enig experimenteren leert dat voor p = 1093 en 3511 geldt dat p2 een deler is
van 2p − 2. Verder zoeken levert verrassend weinig op en het blijkt dat de twee
genoemde waarden de enige waarden van p < 3.2 × 1013 zijn waarvoor geldt dat
2p ≡ 2 (mod p2 ). Grote vraag is uiteraard, bestaan er oneindig veel priemgetallen
p z´o dat 2p ≡ 2 (mod p2 ) ? Niemand heeft enig idee hoe dit probleem aan te
pakken. Een nog onverwachter vraag zonder oplossing is de volgende. Omdat
van alle priemgetallen kleiner dan 3.2 × 1013 er slechts twee zijn waarvoor geldt
2p ≡ 2 (mod p2 ) zou men kunnen vermoeden dat er oneindig veel priemgetallen
p zijn z´o dat 2p − 2 precies ´e´en factor p bevat. Hoewel dit wel zeer waarschijnlijk
lijkt heeft ook hier niemand enig idee hoe men met een bewijs moet beginnen.
Uiteraard kunnen we dergelijke vragen ook stellen voor andere getallen van de
vorm ap − a.
7.3
Ordes
Kies nu M ∈ Z≥2 even vast. De stelling van Euler zegt blijkbaar dat er bij elke
a ∈ Z met ggd(a, M ) = 1 een natuurlijk getal k bestaat z´o dat ak ≡ 1 (mod M ).
Kies zo’n a en beschouw de verzameling
E = {k ∈ N|ak ≡ 1 (mod M )}
Het kleinste element uit E noemen we de orde van a (mod M ). Notatie: ordM (a).
Het is duidelijk dat E een verschillenverzameling is. Dus is volgend Stelling 3.2.3
elk element van E veelvoud van ordM (a). We maken hier een Lemma van,
Lemma 7.3.1 Zij M ∈ Z≥2 en a ∈ Z met ggd(a, M ). Stel ak ≡ 1 (mod M ).
Dan geldt dat ordM (a)|k.
Dit Lemma heeft een aantal onmiddelijke gevolgen. Stel bijvoorbeeld dat p een
priemdeler is van am −1 en niet van a−1, a2 −1, . . . , am−1 −1. Dan is m = ordp (a).
Als p ook een deler is van an − 1 dan impliceert bovenstaand Lemma dat m|n.
Maar dit is precies Stelling 5.1.2. Verder volgt uit de kleine stelling van Fermat
dat p deler is van ap−1 −1. Dus m deelt p−1, hetgeen precies Stelling 5.1.4 is. We
50
HOOFDSTUK 7. CONGRUENTIES IN ACTIE
zien dus dat de resultaten uit Hoofdstuk 5 teruggevoerd worden tot elementaire
eigenschappen van ordes van inverteerbare restklassen.
Laten we ter nadere ori¨entatie eens een paar tabellen van ordM (a) opschrijven
voor M = 7, 15
a
ord7 (a)
a
1
ord15 (a) 1
1 2
1 3
2
4
4
2
3
6
7
4
4
3
8
4
5
6
11
2
6
2
13
4
14
2
Merk allereerst op dat de ordes van de elementen inderdaad delers zijn van ϕ(7) =
6 respectievelijk ϕ(15) = 8. Er is echter ook een verschilpunt tussen de twee
gevallen. Modulo 7 bestaat er een element van orde 6, namelijk 3 (en ook 5). Dit
betekent, dat de restklassen 31 , 32 , . . . , 36 ≡ 1 allen verschillend zijn. Met andere
woorden, de machten van 3 geven modulo 7 alle elementen van (Z/7Z)∗ . In het
geval van (Z/15Z)∗ is dat niet geval, er bestaan geen elementen van orde 8 en
(Z/15Z)∗ bestaat dus niet uit de machten van een of ander element. Het verschil
zit hem in het feit dat 7 priem is en 15 niet.
Om dit wat beter te zien gaan we de stelling van Euler wat verscherpen. Definieer
voor elke M ∈ Z≥2 het getal
λ(M ) = kgvp|M (pk − pk−1 ).
In plaats van het product van pk − pk−1 over alle priemdelers p van M , zoals bij
de berekening van ϕ(M ), nemen we nu het kleinste gemene veelvoud van deze
getallen. Merk op dat pk − pk−1 even is, tenzij pk = 2. Als M dus twee primaire
factoren, elk groter dan 2, bevat dan geldt λ(M ) < ϕ(M ). Een voorbeeld, λ(15) =
kgv(2, 4) = 4 en is dus kleiner dan ϕ(15) = 8. De verscherping van Euler’s stelling
gaat nu als volgt,
Stelling 7.3.2 Zij M ∈ Z≥2 . Dan geldt voor elke a ∈ Z met ggd(a, M ) = 1 dat
aλ(M ) ≡ 1 (mod M ).
Het bewijs volgt door de opmerking dat voor elke priemdeler p van M geldt
k
k−1
ap −p ≡ 1 (mod pk ), waarin pk het getal M precies deelt. Dit is Euler’s stelling
toegepast modulo pk . Automatisch volgt hieruit dat aλ(M ) ≡ 1 (mod pk ). Anders
gezegd, pk deelt aλ(M ) − 1 voor elke primaire factor pk van M . Dus deelt het
product, dat wil zeggen M zelf, het getal aλ(M ) − 1 ook.
2
o dat
Definitie 7.3.3 Een geheel getal g z´
{g, g 2 , . . . , g ϕ(M ) } = (Z/M Z)∗ ,
noemen we een primitieve wortel modulo M
7.4. PRIMITIEVE WORTELS
51
Uit de verfijning van de stelling van Euler hebben we gezien dat als M twee
verschillende primaire factoren, elk groter dan 2 bevat, er geen primitieve wortel
modulo M kan zijn, omdat altijd g λ(M ) ≡ 1 (mod M ), waarbij λ(M ) < ϕ(M ).
De enige getallen M waarbij nog een primitieve wortel modulo M kan bestaan
zijn de machten van priemgetallen en tweemaal de machten van priemgetallen.
We zullen deze kwestie in de volgende paragraaf aanpakken en laten zien dat er
altijd een primitieve wortel modulo een priemgetal bestaat.
We gaan hier nog wat spelen met ordes van elementen modulo M . We willen uit
elementen waarvan de orde bekend is, een nieuw element te maken waarvan de
orde het kgv is van de oorspronkelijke ordes is. We doen dit met behulp van een
tweetal Lemmas die ook in de volgende paragraaf goed van pas komen.
Lemma 7.3.4 Zij a, b ∈ (Z/M Z)∗ en stel dat hun ordes A = ordM (a) en B =
ordM (b) relatief priem zijn. Dan heeft ab orde AB.
In ieder geval geldt dat (ab)AB ≡ aAB bAB ≡ 1B 1A ≡ 1 (mod M ). Dus ordM (ab)
deelt AB. Stel omgekeerd (ab)k ≡ 1 (mod M ). Verhef aan beide zijden tot de
macht A. Dan geldt aAk bAk ≡ 1 (mod M ). Omdat aA ≡ 1 (mod M ), volgt
hieruit bAk ≡ 1 (mod M ). Gevolg, B deelt Ak en omdat ggd(A, B) = 1 geldt dat
B|k. Op dezelfde manier leiden we af dat A|k. Omdat nog steeds ggd(A, B) = 1
volgt uit A|k, B|k dat AB|k. In het bijzonder AB|ordM (ab). We concluderen dat
ordM (ab) = AB.
2
Hier is nog een nuttige hulpstelling.
Lemma 7.3.5 Stel dat a1 , a2 , . . . , am ∈ (Z/M Z)∗ . Stel
A = kgv(ordM (a1 ), . . . , ordM (am )).
Dan is er een element b ∈ (Z/M Z)∗ z´o dat ordM (b) = A.
Stel dat A = pk11 · · · pkr r de priemontbinding van A is. Wij beweren dat er voor
elke i = 1, . . . , r een element bi ∈ (Z/M Z)∗ bestaat z´o dat ordM (bi ) = pki i .
Omdat A een kleinste gemene veelvoud is, bestaat er immers een j z´o dat pki i
A /p
ki
deler is van Aj = ordM (aj ). Maar dan heeft aj j i precies orde pki i waarmee
we ons gewenste element bi gevonden hebben. Omdat de zo gevonden elementen
b1 , b2 , . . . , br de ordes pk11 , . . . , pkr r hebben en deze ordes relatief priem zijn, volgt
uit het voorgaande lemma dat b1 b2 . . . br precies de orde pk11 · · · pkr r = A heeft.
Hiermee is ons element b gevonden.
2
7.4
Primitieve wortels
Hoofdresultaat van deze paragraaf is de volgende stelling.
52
HOOFDSTUK 7. CONGRUENTIES IN ACTIE
Stelling 7.4.1 Voor elk priemgetal p bestaat er een primitieve wortel modulo p.
Het bewijs presenteren we aan het eind van deze paragraaf. Eerst geven we wat
voorbeelden. Kies p = 71. Dank zij deze stelling weten we dat er een primitieve
wortel is. Laten we er ´e´en bepalen. Probeer eerst 2. We weten dat ord71 (2) een
deler van 71 − 1 = 70 is. Merk op dat de priemdelers van 70 gegeven worden door
2, 5, 7. Test eerst 2d (mod 71) voor de delers d = 70/2, 70/5, 70/7 = 35, 14, 10 van
71. We vinden dat 235 ≡ 1 (mod 71). Dus 2 is geen primitieve wortel modulo
71. We proberen vervolgens 3 als primitieve wortel. Wederom blijkt dat 335 ≡
1 (mod 71). Daarom proberen we vervolgens 5 (waarom wordt 4 overgeslagen?).
Het blijkt dat 535 ≡ 1 (mod 71) en ook 635 ≡ 1 (mod 71). Tenslotte blijkt dat
735 , 714 , 710 allen ongelijk 1 modulo 71 zijn en dus is 7 een primitieve wortel
modulo 71. Hoewel deze methode om primitieve wortels te zoeken erg na¨ıef is,
is dit in feite de enige methode om primitieve wortels modulo een priemgetal te
vinden. In de volgende tabel staan de kleinste primitieve wortels w modulo de
priemgetallen p tot 100.
p
w
p
w
41
6
3
2
5
2
7
3
43
3
47
5
53
2
11
2
59
2
13
2
61
2
17
3
67
2
19
2
71
7
23
5
73
5
29
2
79
3
31
3
83
2
37
2
89
3
97
5
Een korte blik hierop leert ons dat er geen enkel systeem zit in deze rij waarden.
Men heeft wel enkele vermoedens. Als een diep vermoeden uit de analytische
getaltheorie, de zogenaamde Gegeneraliseerde Riemann Hypothese, waar is dan
kan men de volgende uitspraak aantonen.
Vermoeden 7.4.2 Voor elk priemgetal p bestaat er een natuurlijk getal g met
g < 2(log(p))2 z´o dat g primitieve wortel modulo p is.
Het beste resultaat dat men tot dusver kan aantonen is dat er een primitieve
wortel g < p1/4 bestaat (Burgess, 1962).
Bij het bekijken van tabellen als het bovenstaande zou men wellicht tot het
volgende vermoeden kunnen komen,
Vermoeden 7.4.3 (E.Artin) Het getal 2 is een primitieve wortel modulo p voor
oneindig veel priemgetallen p.
Ook hier geldt dat dit vermoeden waar is als de gegeneraliseerde Riemann hypothese waar is. Uiteraard kunnen we soortgelijke vermoedens voor andere
getallen dan 2 opstellen. Echter, bij gebrek aan concrete resultaten zullen we
hier verder niet over uitweiden.
7.4. PRIMITIEVE WORTELS
53
Het belangrijkste ingredient in het bewijs van Stelling 7.4.1 is het feit dat polynomen modulo p, met p priem niet meer nulpunten kunnen hebben dan hun graad
bedraagt. Even ter herinnering, een polynoom is een uitdrukking van de vorm
P = an X n + an−1 X n−1 + · · · + a1 X + a0 waarin a0 , · · · , an ∈ Z. We spreken
van een polynoom modulo p als we de co¨efficienten modulo p beschouwen. Als
an ̸≡ 0 (mod p) dan zeggen we dat P (mod p) graad n heeft. Als alle co¨efficienten
ai nul modulo p zijn dan noemen we het polynoom P (mod p) triviaal. Er geldt
nu de volgende stelling.
Stelling 7.4.4 Zij P (mod p) een niet-triviaal polynoom van graad n. Dan heeft
de congruentievergelijking P (x) ≡ 0 (mod p) hoogstens n restklassen x modulo p
als oplossing.
Als we met gehele of rationale co¨efficienten zouden werken, dan komt deze stelling
waarschijnlijk bekend voor, het aantal nulpunten van een polynoom kan niet
groter dan de graad zijn. Het bewijs dat we voor Stelling 7.4.4 geven gaat ook
op voor polynomen met gehele of rationale co¨efficienten.
Merk op dat als n >= p deze stelling vanzelfsprekend is, omdat er niet meer dan
p restklassen modulo p zijn. Een andere opmerking is dat alleen polynoomvergelijkingen modulo priemgetallen deze eigenschap hebben. Voor samengestelde getallen
gaat het fout. Beschouw bijvoorbeeld de polynomiale congruentievergelijking
x2 ≡ 1 (mod 24). Deze heeft de restklassen 1, 5, 7, 11, 13, 17, 19, 23 (mod 24) als
oplossing. Veel meer dan de graad 2 in dit geval.
Het bewijs van de stelling gaat via volledige inductie naar de graad n. Als n = 0
dan is de stelling duidelijk. Polynomen van graad nul zijn de constante polynomen
a0 met a0 ̸≡ 0 en wat we ook voor x kiezen nooit zullen a0 en 0 gelijk worden
modulo p. Er zijn dus nul oplossingen.
Stel nu n > 0 en neem aan dat de stelling geldt voor alle niet-triviale polynomen
van graad kleiner dan n. Zij f (X) een polynoom van graad n en stel dat de
co¨efficient van X n gelijk is aan a ̸≡ 0 (mod p). Stel dat f (x) ≡ 0 (mod p)
minstens n verschillende oplossingen heeft. Geef ze aan met x1 , x2 , . . . , xn . We
laten eerst zien dat f (X) ≡ a(X − x1 ) · · · (X − xn ) (mod p). Merk namelijk op
dat de graad van g(X) = f (X) − a(X − x1 ) · · · (X − xn ) kleiner dan n is. Ga
verder na dat g(xi ) ≡ 0 (mod p) voor i = 1, 2, . . . , n. Dus g heeft n nulpunten.
Maar volgens onze induktiehypothese kan een polynoom van graad < n nooit n
nulpunten modulo p hebben, tenzij dat polynoom triviaal is. Dus is g(X) triviaal
modulo p. Gevolg f (X) ≡ a(X − x1 ) · · · (X − xn ) (mod p).
Stel vervolgens, dat f nog een nulpunt ξ heeft. Dan geldt f (ξ) ≡ 0 (mod p) en
dus, a(ξ − x1 ) · · · (ξ − xn ) ≡ 0 (mod p). Dus p deelt het produkt van de getallen
ξ − xi . Omdat p een priemgetal is moet p ´e´en van deze faktoren delen. Dit is
het enige moment waarop we van de primialiteit van p gebruikmaken! Er is een
i met 1 ≤ i ≤ n z´o dat ξ ≡ xi (mod p). Dus elk nulpunt is modulo p gelijk aan
´e´en van de xi . Er kunnen dus niet meer dan n nulpunten van f modulo p zijn. 2
54
HOOFDSTUK 7. CONGRUENTIES IN ACTIE
Het bewijs van Stelling 7.4.1 is nu niet lastig meer. Zij E het kgv van alle ordes
ordp (a) voor a = 1, 2, . . . , p − 1. We weten dat E een deler is van p − 1, want p − 1
is een veelvoud van elke ordp (a). Dus E ≤ p−1. Anderzijds geldt aE ≡ 1 (mod p)
voor a = 1, 2 . . . , p − 1. Dus heeft X E − 1 precies p − 1 verschillende nulpunten.
Volgens onze stelling over polynomen modulo p moet dus gelden E ≥ p − 1. We
concluderen dat E = p − 1. Pas nu Lemma 7.3.5 toe, dat zegt dat er een element
met orde E = p − 1 bestaat.
2
Er bestaan ook primitieve wortels modulo pk als p een oneven priem is.
Stelling 7.4.5 Zij p een oneven priemgetal en k ∈ N. Dan bestaat er een primitieve wortel modulo pk .
Omdat we deze stelling later niet echt nodig zullen hebben geven we er hier ook
geen bewijs voor.
Merkwaardig genoeg bestaan er modulo 2k geen primitieve wortels als k ≥ 3.
Voor k = 3 zien we dit bijvoorbeeld uit het feit dat x2 ≡ 1 (mod 8) voor x =
1, 3, 5, 7. Modulo 2 en 4 zijn er wel primitieve wortels, namelijk 1 respectievelijk
−1.
© Copyright 2024 ExpyDoc
