Mathematik: Zahlentheorie: Kongruenzrechnung

Kongruenzrechnung

Sei m eine natürliche Zahl. Für ganze Zahlen a,b schreibt man: $a\equiv b\mod m$ (sprich: a kongruent zu b modulo m), wenn m ein Teiler von a-b ist.

Beispiel: Eine Zahl ist gerade, wenn sie kongruent zu 0 modulo 2 ist; ungerade, wenn sie kongruent zu 1 modulo 2 ist.

Es ist leicht zu zeigen, dass dies eine Äquivalenzrelation ist, d.h. es gelten folgende Regeln:

• $a\equiv a\mod m$
• $a\equiv b\mod m\Rightarrow b\equiv a\mod m$
• $a\equiv b\mod m,b\equiv c\mod m\Rightarrow a\equiv c\mod m$

Kongruenz mod m teilt die ganzen Zahlen in die m Restklassen modulo m, die z.B. durch die Zahlen 0, 1, ..., m-1 vertreten werden.

Außerdem verträgt sich Kongruenz mit Addition und Multiplikation, d.h. die Restklasse einer Summe hängt nur von den Restklassen der Summanden ab, ebenso für das Produkt. Dies lässt sich leicht nachrechnen, hier für das Produkt:

Seien $a\equiv b\mod m$ und $c\equiv d\mod m$. Dann gilt $ac\equiv bd\mod m$, denn $ac-bd=a(c-d)+(a-b)d$ ist durch m teilbar, weil sowohl c-d wie a-b durch m teilbar sind.

Beispiel: Man bestimme die letzte Ziffer von 123*987.

Lösung: Rechne modulo 10, wegen 3*7=21 ist die letzte Ziffer des Produkts 1.

Die Restklassen bilden also einen Ring Z/mZ. Falls m eine Primzahl ist, ist dieser Ring sogar ein Körper, d.h. man kann dividieren. Dies folgt aus dem nächsten Satz.

Beispiel: Der Restklassenring modulo 2 besteht aus den Elementen ${\bar {0}}$ ("gerade") und ${\bar {1}}$ ("ungerade"). Es gilt ${\bar {1}}+{\bar {1}}={\bar {0}}$.

Satz: Ist a eine zu m teilerfremde ganze Zahl, so hat für jede ganze Zahl b die Kongruenz $ax\equiv b\mod m$ eine - bis auf Kongruenz mod m - eindeutige Lösung x.

Beweis:

Existenz: Nach Kapitel 2 gibt es ganze Zahlen r, s mit ra+sm=ggT(a,b)=1, also $ra\equiv 1\mod m$. Folglich löst x=rb die Kongruenz.

Eindeutigkeit: Ist y eine weitere Lösung, so folgt $x-y\equiv ra(x-y)\equiv rax-ray\equiv b-b\equiv 0\mod m$.