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) und b ≡ x (mod m), so gilt:

• $a\equiv a\mod m$                       Reflexivität
• $b\equiv a\mod m$                       Symmetrie
• $a\equiv x\mod m$                      Transitivität
• $na\equiv nb\mod m$                 Skalarmultiplikation
• $a+c\equiv b+d\mod m$      Addition
• $a-c\equiv b-d\mod m$      Subtraktion
• $ac\equiv bd\mod m$                  Multiplikation
• $a^{n}\equiv b^{n}\mod m$                  Potenzregel
• $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 bzw. der Fermatsche Primzahltest.

Ferner sind Kongruenzen bzw. Restklassen oft hilfreich, wenn man Berechnungen mit sehr großen Zahlen durchführen muß.

Beispiele:

Mit welcher Ziffer endet die Zahl 333²²²?

333 ≡ 3 mod 10
Daraus folgt mit der Potenzregel (a=333, b=3, m=10, n=222): 333²²² ≡ 3²²² mod 10
Es gilt 3³ ≡ (-1) mod 10. Erneute Anwendung der Protenzregel (a=3³, b=-1, m=10, n=74) liefert: 3²²² = 3^3*74 ≡ (-1)⁷⁴ mod 10 = 1.
Die Endziffer ist also 1.

siehe auch: lineare Kongruenz, simultane Kongruenz