Wat is Congruentie? — Wiskunde

বইগুলো এখনো বাংলা ভাষায় পাওয়া যায় না — Nederlands সংস্করণ দেখানো হচ্ছে।

Definitie 29.4 Wiskunde bovenbouw · অধ্যায় 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$ .

প্রসঙ্গসহ পড়ো →

Definitie 6.18 Universitaire wiskunde — Bachelor jaar 1 · অধ্যায় 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$ .

উদাহরণ

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.

প্রসঙ্গসহ পড়ো →

উদাহরণ

সম্পর্কিত পরিভাষা-শব্দ