Congruentie (rekenkunde)

Twee gehele getallen ${\displaystyle a}$ en ${\displaystyle b}$ heten congruent modulo een positief geheel getal ${\displaystyle n}$ als ze een veelvoud van ${\displaystyle n}$ van elkaar verschillen.

Meestal wordt congruentie als volgt genoteerd:

${\displaystyle a\equiv b\ ({\hbox{mod}}\ n)}$

Gauss was aan het einde van de 18e eeuw de eerste die zich in de congruentie tussen getallen verdiepte en schreef zijn bevindingen daarover op in zijn Disquisitiones arithmeticae in 1801.

Algemene definitie

Zij ${\displaystyle R}$ een ring en ${\displaystyle I}$ een ideaal in ${\displaystyle R}$. Twee elementen ${\displaystyle a}$ en ${\displaystyle b}$ heten in ${\displaystyle R}$ congruent modulo ${\displaystyle I}$ als hun verschil tot ${\displaystyle I}$ behoort.

Voorbeelden

• ${\displaystyle 2\equiv 5\ ({\hbox{mod }}3)}$

want ${\displaystyle 5-2=3}$ is een veelvoud van 3.

• ${\displaystyle -7\equiv 9\ ({\hbox{mod }}8)}$

want ${\displaystyle -7-9=-16}$ is een veelvoud van 8.

• ${\displaystyle 6\equiv 0\ ({\hbox{mod }}3)}$
• ${\displaystyle 2\not \equiv 5\ ({\hbox{mod }}6)}$
• De restklassen ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ van gehele getallen zijn de congruentieklassen modulo het ideaal ${\displaystyle n\mathbb {Z} }$, de veelvouden van ${\displaystyle n}$.

Eigenschappen

• De congruentieklassen modulo ${\displaystyle I}$ vormen opnieuw een ring, de factorring. Die wordt genoteerd met ${\displaystyle R/I}$, bijvoorbeeld ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$.
• Congruentie is een equivalentierelatie en de equivalentieklassen vormen dus een partitie van de verzameling van de gehele getallen. De restklassen modulo ${\displaystyle n}$ zijn deze congruentieklassen.