Wat is Congruentie? — Wiskunde

Definitie 29.4 Wiskunde bovenbouw · Hoofdstuk 29 — Getaltheorie

Zij $n \in \N^*$ . Twee gehele getallen $a$ en $b$ heten congruent modulo $n$ , genoteerd $a \equiv b \pmod n$ , als $n \mid (a - b)$ — gelijkwaardig: als $a$ en $b$ dezelfde rest hebben bij de euclidische deling door $n$ .

Lees in het hoofdstuk →

Definitie 6.18 Universitaire wiskunde — Bachelor jaar 1 · Hoofdstuk 6 — Getaltheorie in ℤ

Voor $n \in \N^*$ schrijven we $a \equiv b \pmod n$ wanneer $n \mid a - b$ . Dat is een equivalentierelatie die verenigbaar is met optellen en vermenigvuldigen: is $a \equiv b$ en $a' \equiv b'$ (mod $n$ ), dan is $a + a' \equiv b + b'$ , $aa' \equiv bb'$ en $a^k \equiv b^k$ voor $k \in \N$ .

Voorbeelden

Voorbeeld 6.19 (De negenproef)

De verenigbaarheid met $+$ en $\times$ is een controlemiddel dat zo oud is als de handel. Omdat $10 \equiv 1 \pmod 9$ , is elk geheel getal modulo $9$ congruent met zijn cijfersom (bewezen als Oefening 6.2). Om de bewering $1234 \times 567 = 699\,678$ te toetsen: de cijfersommen geven $1234 \equiv 1$ en $567 \equiv 18 \equiv 0 \pmod 9$ , dus moet het product $\equiv 1 \times 0 = 0$ zijn; en inderdaad is $6 + 9 + 9 + 6 + 7 + 8 = 45 \equiv 0$ . De proef slaagt (en het product klopt ook echt). Had iemand $699\,478$ gemeld, dan zou de cijfersom $43 \equiv 7 \not\equiv 0$ hem meteen ontmaskeren. De toets is eenzijdig — ze betrapt een fout tenzij de fout zelf een veelvoud van $9$ is — en dat is in het klein precies de les over pseudopriemgetallen uit Voorbeeld 6.24: controles met congruenties weerleggen, ze bewijzen niet.

Voorbeeld 6.21 ( $7$ inverteren modulo $26$ )

Omdat $\gcd(7, 26) = 1$ , is de klasse van $7$ inverteerbaar modulo $26$ . Uitgebreid Euclides:

26 = 3 \times 7 + 5, \qquad 7 = 1 \times 5 + 2, \qquad 5 = 2 \times 2 + 1 ,

en dan achterstevoren:

1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 .

Bijgevolg is $7 \times (-11) \equiv 1 \pmod{26}$ , oftewel $7^{-1} \equiv -11 \equiv 15 \pmod{26}$ ; controle: $7 \times 15 = 105 = 4 \times 26 + 1$ . Met de inverse in handen los je elke congruentie $7x \equiv c \pmod{26}$ in één vermenigvuldiging op: $x \equiv 15c$ . Dit mechanische inverteren is het werkpaard van het modulaire rekenen — en van de protocollen met publieke sleutel die in Opmerking 6.27 genoemd worden, waar de moduli honderden cijfers tellen maar het algoritme exact dit is.

Voorbeeld 6.22 (Wanneer de coëfficiënt niet inverteerbaar is)

Los $12x \equiv 8 \pmod{20}$ op. Hier is $\gcd(12, 20) = 4$ , dus $12$ is niet inverteerbaar modulo $20$ — maar de vergelijking blijft hanteerbaar. De congruentie zegt $20 \mid 12x - 8$ ; deling van de hele betrekking door $4$ (een deler van alle drie de ingrediënten) maakt haar equivalent met $5 \mid 3x - 2$ , oftewel

3x \equiv 2 \pmod 5 .

Nu is $\gcd(3, 5) = 1$ en $3^{-1} \equiv 2 \pmod 5$ (want $3 \times 2 = 6 \equiv 1$ ), dus $x \equiv 4 \pmod 5$ : de oplossingen zijn $x \equiv 4, 9, 14, 19 \pmod{20}$ — vier klassen modulo $20$ , overeenkomend met de ggd. (Was het rechterlid niet deelbaar door $4$ geweest, zeg $12x \equiv 6 \pmod{20}$ , dan was er helemaal geen oplossing: het linkerlid is altijd $\equiv 0 \pmod 4$ .) Algemene vorm: $ax \equiv b \pmod n$ is oplosbaar precies wanneer $\gcd(a, n) \mid b$ , en heeft dan precies $\gcd(a, n)$ oplossingsklassen — deel alles door de ggd en inverteer.

Lees in het hoofdstuk →

Voorbeelden

Verwante begrippen