Kongruenz (Zahlentheorie)

In der Zahlentheorie heißen zwei ganze Zahlen a und b kongruent modulo m (wobei m eine positive ganze Zahl ist), wenn m (a-b) teilt. Man schreibt:

$a\equiv {}b\mod {}m\qquad \mathrm {oder} \qquad {}a\equiv {}b\ (\mathrm {mod} \ m)$

Anders formuliert kann man auch sagen, dass zwei Zahlen kongruent modulo einer Zahl m sind, wenn sie bei der Division durch m den selben Rest ergeben.

Man bezeichnet die Menge aller zu a (modulo m) kongruenten ganzen Zahlen als die Restklasse von a modulo m:

${\bar {a}}:=\{x\in \mathbb {Z} :a=x\mod m\}$

Es gibt daher genau m Restklassen (${\bar {0}},{\bar {1}},\dots {\overline {m-1}}$) modulo m.

Rechenregeln

Für das Rechnen mit Kongruenzen lassen sich einige elementare Rechenregeln aufstellen:

Gilt a ≡ b (mod m) und c ≡ d (mod m), so gilt:

• $a+c\equiv b+d\mod m$
• $a-c\equiv b-d\mod m$
• $ac\equiv bd\mod m$
• $t\cdot {}a\equiv t\cdot {}b\mod |t|\cdot {}m,\quad t\neq 0$
• ${\textrm {Gilt}}\ k\mid {}m,\mathrm {so\ folgt:} \ a\equiv {}b\mod k$

Mit Hilfe von Kongruenzen lassen sich zum Beispiel die Teilbarkeitsregeln leicht beweisen. Eine wichtige Aussage über Kongruenzen von Primzahlen ist der kleine Satz von Fermat.

siehe auch: lineare Kongruenz, simultane Kongruenz