Congruentie (rekenkunde)

Twee gehele getallen en heten congruent modulo een positief geheel getal als ze een veelvoud van van elkaar verschillen.

Meestal wordt congruentie als volgt genoteerd:

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

bewerken

Zij   een ring en   een ideaal in  . Twee elementen   en   heten in   congruent modulo   als hun verschil tot   behoort.

Voorbeelden

bewerken
  •  
want   is een veelvoud van 3.
  •  
want   is een veelvoud van 8.
  •  
  •  
  • De restklassen   van gehele getallen zijn de congruentieklassen modulo het ideaal  , de veelvouden van  .

Eigenschappen

bewerken
  • De congruentieklassen modulo   vormen opnieuw een ring, de factorring. Die wordt genoteerd met  , bijvoorbeeld  .
  • Congruentie is een equivalentierelatie en de equivalentieklassen vormen dus een partitie van de verzameling van de gehele getallen. De restklassen modulo   zijn deze congruentieklassen.