Congruenties en restklassen

0. Overzicht

Definitie en eigenschappen
Congruentie- of restklassen
Restsystemen
3.1. Volledig resteem
3.2. Gereduceerd restsysteem, samenhang met de indicator van Euler
Stelling van Euler (waarin oa. een bewijs van de Kleine stelling van Fermat)
Orde

1. Definitie en eigenschappen

Definitie
Als voor de gehele getallen a en b en een positief geheel getal m geldt m | (a-b) dan zeggen we dat a en b congruent modulo m zijn.
Schrijfwijze: a º b (mod m) of soms ook a = b (mod m).

Stelling 1
Voor congruenties (mod m) geldt

(i)	a º a
(ii)	Uit a º b volgt b º a
(iii)	Uit a º b en b º c volgt a º c
(iv)	a º b DESDA a en b hebben dezelfde hoofdrest bij deling door m

Bewijs:
De eigenschappen (i), (ii), (iii) volgen direct uit de definitie, immers a - a º 0, a-b = -(b-a) en a-c = (a-b) +(b-c).
(iv)
Voor a, b en m geldt volgens de delingsalgoritme (op de pagina "Deelbaarheid"):
   a = q₁m + r₁ met r₁ < m
   b = q₂m + r₂ met r₂ < m
zodat
   a - b = (q₁-q₂)m+ (r₁-r₂) waarbij 0 £ (r₁-r₂) < m
Deze laatste ongelijkheid is te schrijven als 0 £ (r₁-r₂) £ m-1
Als nu ook moet gelden m | (a-b), dan is m | (r₁-r₂). En dan volgt r₁ = r₂. ¨

2. Congruentie- of restklassen
Door een congruentie (mod m) wordt de verzameling der gehele getallen opgedeeld in congruentieklassen of restklassen die vastgelegd worden door Eigenschap IV van Stelling 1.
Er zijn nu m congruentieklassen C₀, C₁, ,,,, C_m-1.
Een getal behoort tot Cr, dan en slechts dan als zijn hoofdrest bij deling door m gelijk is aan r.
Elke klasse Cr (voor r = 0, 1, ..., m-1) in de verzameling Z van de gehele getallen bestaat daardoor uit de getallen r + km (met k = 0, ±1, ±2, ...) (zie figuur 1).

figuur 1

Stelling 2 - Rekenregels
Voor a º b (mod m) en c º d (mod m) geldt

(i)	a + c º b + d (mod m)
(ii)	ac º bd (mod m)
(iii)	an º bn (mod m) DESDA a º b (mod m/gdd(m,n) )

Bewijs:
(i) a - b = pm, c - d = qm. Dus (a-b) + (c-d) = (p+q)m of (a+c) - (b+d) = rm, zodat a+c º b+d (mod m).
(ii) ac - bd = ac - bc + bc - bd = (a-b)c + (c-d) b = pm . c + qm . d = (pc+qd)m, zodat m | (ac - bd).
(iii) Zij d = ggd(m,n) en m = dm₁, n = dn₁ zodat dus ggd(m₁,n₁)=1
Als an º bn (mod m), dan dm₁ | (a-b)dn₁ of m₁ | (a-b)d, dus m₁ | (a-b) waaruit a = b (mod m₁ = m/d ).
Voor het omgekeerde leiden we uit m₁ | (a-b) af, dat dm₁ | (a-b)d₁. Waaruit het gestelde volgt.¨

Gevolg
Uit Stelling 2 (iii) volgt nu

Stelling 2
(iv) Uit an º bn (mod m) volgt dat a º b (mod m) onder voorwaarde dat ggd(m,n) = 1.

[einde Gevolg]

3. Restsystemen

3.1. Volledig restsysteem

Definitie
De verzameling {x₀, x₁, ..., x_m-1} heet een volledig restsysteem (mod m) als x_i een element is van C_i (met i =0, 1, ..., m-1).

Voorbeeld
{ 0, 1, 2, 3, 4, 5, 6 } is een volledige restsysteem (mod 7)
{ 0, 1, -1, 2, -2, 3, -3 } is eveneens een volledig restsysteem (mod 7)
[einde Voorbeeld]

Stelling 3
[1]
Is {x₀, x₁, ..., x_m-1} een volledig restsysteem (mod m) dan is
{ax₀ +b, ax₁ + b, ..., ax_m-1 + b}
eveneens een volledig restsysteem (mod m) mits ggd(a,m) = 1 (b willekeurig).
[2]
Zijn {x₁, ..., x_m}(mod m) en {y₁, ..., y_n}(mod n) volledige restsystemen dan is
{ nx_i + my_j | i=1, .., m, j = 1, ..., n }
een volledig restsysteem (mod mn) mits ggd(m,n) =1.

Bewijs: (volgt) ¨

3.2. Gereduceerd restsysteem, samenhang met de indicator van Euler

Stelling 4
Heeft een restklasse (mod m) een element a, dat relatief priem is met m, dan is elk element van die restklasse relatief priem met m.

Bewijs:
Als a º b (mod m), dan is a-b = km (voor zekere k). Nu is dus ook ggd(a, m) = ggd(b + km), m) en dus ook ggd(a, m) = ggd(b,m).
a en b behoren tot dezelfde restklasse, dus ook ggd (b,m) = 1. b is dus relatief priem met m. ¨

Gevolg
In de verzameling {0, 1, 2, ..., m1}, een volledig restsysteem module m, zijn er f(m) getallen die relatief priem zijn met m.
Hierbij is f(m) de zogenoemde indicator van Euler.
Er zijn dus f(m) restklassen die bestaan uit getallen die met m onderling ondeelbaar zijn.
[einde Gevolg]

We definiëren op basis hiervan

Definitie
Een gereduceerd restsysteem (mod m) is een deelverzameling van een volledig restsysteem (mod m) bestaande uit f(m) restklassen, waarvan de elementen relatief prime zijn met m.

Voorbeeld
{ 0, 1, 2, 3, 4, 5, 6 } is een volldige restsysteem (mod 7).
{ 1, 2, 3, 4, 5, 6 } is een gereduceerd restsysteem (mod 7). Merk op dat f(7) = 6, immers 7 is een priemgetal.
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } is een volledig restsysteem (mod 10).
{ 1, 3, 7, 9 } is een gereduceerd restsysteem (mod 10). We weten, dat f(10) = 4.
[einde Voorbeeld]

Stelling 5
[1]
Is { x₁, x₂, ..., x_f(m) } een gereduceerd restsysteem (mod m), dan is
{ ax₁, ax₂, ..., ax_f(m) }
een gereduceerd restsysteem (mod m), mits ggd(a,m) = 1.
[2]
Zijn { x₁, x₂, ..., x_f(m) } (mod m) en { y₁, y₂, ..., y_f(m) } (mod n) gereduceerd restsystemen, dan is ook
{ nx_i + my_j | ...}
een gereduceerd restsysteem (mod mn), bestaande uit f(mn) = f(m) . f(n) elementen.

Bewijs: (volgt).¨

4. Stelling van Euler

Stelling 6a - Stelling van Euler
ALS ggd(a, m) = 1 DAN a^f(m) º 1 (mod m).

Bewijs:
Zij n = f(m). En zij verder { x₁, x₂, ..., x_n } een gereduceerd restsysteem (mod m).
Uit Stelling 5.1 volgt dan, dat ook { ax₁, ax₂, ..., ax_n } een gereduceerd restsysteem (mod m) is.
Voor alle x_i en ax_j geldt x_j º ax_i (mod m), voor zekere i en j.
Vermenigvuldiging geeft dan
   ax₁ . ax₂ ... ax_n º x₁x₂...x_n (mod m)
Dus
   aⁿx₁x₂ ... x_n º x₁x₂ ... x_n (mod m).
Omdat ggd(x₁, x₂, ..., x_n, m) = 1 vinden we volgens het Gevolg van Stelling 2 (iii):
   a^f(n) º 1 (mod m). ¨

Gevolg

Stelling 6b - Kleine stelling van Fermat
ALS p is priem en ggd(a, p) = 1 DAN a^p-1 º 1 (mod p) voor iedere gehele a.

Bewijs:
Volgens Stelling 6a vinden we direct a^p-1 º 1 (mod p), immers f(p) = p-1. ¨

Opmerkingen
[1]
De Kleine stelling van Fermat wordt oa. gebruikt bij het onderzoek naar priemgetallen.
Zie Appendix B bij de pagina "Mersenne-priemgetallen" voor een ander bewijs van de Kleine stelling van Fermat.

[2]
De Kleine stelling van Fermat wordt ook wel geformuleerd als

Kleine stelling van Fermat
ALS p is priem en ggd(a, p) = 1 DAN a^p º a (mod p) voor iedere gehele a.

Bewijs:
Voor ggd(a,p) = 1 hebben we a^p-1 º 1 (mod p), volgens Stelling 6b. Vermenigvuldiging met a geeft, volgens het Gevolg van Stelling 2 (iii),
a^p º a (mod p).
Is ggd(a, p) ongelijk aan 1, dan is ggd(a,p) = p, zodat p | a^p, en dus ook p | (a^p - a), waaruit volgens de definitie volgt
a^p º a (mod p). ¨
[einde Opmerkingen en Gevolg]

5. Orde

Definitie
Als ggd(a,m) = 1dan heet het kleinste positieve gehele getal r met a^r º 1 (mod m) de orde van a (mod m).

Opmerking
De Stelling van Euler toont aan, dat r bestaat en dat r £ f(m).
Als ggd(a,m) groter dan 1 is, dan bestaat zo'n getal r niet.
Immers, a^r º 1 (mod m) houdt in, dat a^r = 1 + km (voor zekere k). Voor d = ggd(a,m) blijkt dan, als r > 0, dat d | 1.
Dus d = ggd(a,m) = 1.
[einde Opmerking]

Voorbeelden
[1] We kiezen m = 7. Dan is f(7) = 6.
Een gereduceerd restsysteem (mod 7) is dan { 1, 2, 3, 4, 5, 6 }.
In figuur 2 staan machten van a, waarbij a element is van bovenstaand gereduceerd rest systeem.

figuur 2

Tabel van aⁿ (mod 7)
waarin {a} een gereduceerd restsysteem (mod 7) is

We zien uit figuur 2, dat


orde r gelijk aan	voor a gelijk aan

1	1
2	6
3	2, 4
6	3, 5

Merk op, dat de delers van f(m) alle voorkomen als orde.
We zullen bewijzen (zie Stelling 8) dat voor de orde r van een a (mod m) geldt, dat r | f(m).
Dat echter niet alle delers van f(m) als orde voorkomen blijk in het tweede voorbeeld.

[2]
Kies m = 21. Dan is f(21) = 21 (1-¹/₃)(1-¹/₇) = 2 . 6 = 12.
Een gereduceerd restsysteem (mod 21) is dan { 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20 }.
In figuur 3 staan de machten van a.

figuur 3

Tabel van aⁿ (mod 21)
waarin {a} een gereduceerd restsysteem (mod 21) is

Uit figuur 3 blijkt


orde r gelijk aan	voor a gelijk aan

1	1
2	8, 13, 20
3	4, 16
4	geen
6	2, 5, 10, 11, 17, 19
12	geen

N.B. We zien nu, dat niet alle delers van f(m) als orde voorkomen.
[einde Voorbeelden]

Voor de orde van a hebben we de volgende eigenschappen

Stelling 7
Als ggd(a,m) = 1 en als r de orde van a (mod m) is, dan
[1] 1, a, a², ..., a^r-1 zijn incongruent (mod m)
[2] Voor n > 0 is er een uniek getal s met 0 £ s < r zodat aⁿ º a^s (mod m)
[3] aⁿ º 1 (mod m) DESDA r | n
[4] ALS b º a (mod m), DAN de orde van b (mod m) is gelijk aan de orde van a (mod m)

Bewijs:
[1]
Bewijs uit het ongerijmde.
Stel er zijn u en v met a^u º a^v (mod m) waarbij 0 £ u < v < r.
Dan is 0 < v-u < r. Dus ook a^u º a^u+(v-u) (mod m).
Omdat ggd(a^u,m) = 1 hebben we (bij deling door a^u) a^v-u º 1 (mod m).
Maar nu is v-u kleiner dan r, en dat is in tegenspraak met r is het kleinste getal waarvoor a^r º 1 (mod m). ¨
[2]
Volgens de delingsalgoritme zijn er getallen q en s met
n = qr + s waarbij 0 £ s < r
Nu is
aⁿ = a^{qr + s} = (a^r)^q . a^s º 1 . a^s = a^s (mod m).¨
[3]
Uit Stelling 5.2 volgt dat nu s = 0. Dus n = qr, waaruit r | n.¨
[4]
Als b º a (mod m) dan is ook bⁿ º aⁿ (mod m) voor iedere positieve n.
Dus bⁿ º 1 (mod m) dan en slechts dan als aⁿ º 1 (mod m).
Dit geldt dus ook voor r = n.¨

Gevolg

Stelling 8
ALS r is de orde van a (mod m), DAN r | f(m).

Bewijs:
Volgens de Stelling van Euler is a^f(m) º 1 (mod m). Uit Stelling 7.3 volgt dan eenvoudig, dat r | f(m).¨

Opmerking
Uit deze stellling kunnen we dus de resultaten in de beide voorbeelden mbt. de deelbaarheid van de orde van a (mod m) op f(m) verklaren.
[einde Opmerking]

[congruent.htm] laaste wijziging op: 05-10-2009 (18-09-1999)