Mathematik: Zahlentheorie: Kongruenzrechnung

Kongruenzrechnung

Sei m eine natürliche Zahl. Für ganze Zahlen a,b schreibt man: $a\equiv bmodm$ (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 amodm$
• $a\equiv bmodm\Rightarrow b\equiv amodm$
• $a\equiv bmodm,b\equiv cmodm\Rightarrow a\equiv cmodm$

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 bmodm$ und $c\equiv dmodm$. Dann gilt $ac\equiv bdmodm$, 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 $\overline{0}$ ("gerade") und $\overline{1}$ ("ungerade"). Es gilt $\overline{1}+\overline{1}=\overline{0}$.

Satz: Ist a eine zu m teilerfremde ganze Zahl, so hat für jede ganze Zahl b die Kongruenz $ax\equiv bmodm$ 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 1modm$. 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 0modm$.