Kongruenz von Zahlen

Kongruenz natürlicher Zahlen

Wichtig ist, dass du zunächst die Zahl $n$ festlegst, bezüglich derer du die Kongruenz betrachtest. Ob zwei Zahlen kongruent zueinander sind, ist also abhängig von der Zahl $n$ (dem Modul) und dem Rest, den sie bei der Division durch $n$ ergeben. Ist dieser Rest bei beiden Zahlen gleich, dann sind die Zahlen kongruent modulo $n$, andernfalls sind sie inkongruent modulo $n$.

Defintion des "Rests"

Einen Rest von $-4$ oder $-5$ wie in dem vorigen Beispiel gibt es eigentlich gar nicht. Denn ein Rest ist immer nichtnegativ. Er kann $0$ sein, oder er ist positiv. Die Definition lautet:

Du stellst also die Zahl $a$ als Vielfaches von $n$ dar plus eine möglichst kleine, aber nichtnegative Zahl $r$. Du kannst jede ganze Zahl auf diese Weise eindeutig darstellen.

Schau dir das folgende Beispiel an.

Operation mod

Die Operation $\bmod$ liefert genau diesen Rest, der sich bei Division einer ganzen Zahl $a$ durch $n$ ergibt

Beispielsweise ist $24 \bmod 7 = 3$. Denn $24$ ergibt bei Division durch $7$ den Rest $3$. Damit ist automatisch $24\equiv 3 ~ (\text{mod}~7)$. Beachte aber den Unterschied zwischen der Operation $\bmod$ und der Kennzeichnung einer Kongruenz durch $\bmod$ in Klammern. Es ist beispielsweise auch $24 \equiv 10 \!\pmod 7$.

Rechnen mit Kongruenzen

Das Schöne an der Relation "kongruent modulo $n$" ist, dass sie verknüpfungstreu bezüglich der Verknüpfungen Addition und Multiplikation ist.

Verknüpfungstreu bezüglich Addition

Im Einzelnen bedeutet dies Folgendes: Wenn

gilt, dann bleibt die Kongruenz erhalten, wenn du auf der linken und auf der rechten Seite der Kongruenz jeweils die gleiche Zahl addierst:

Und die Zahlen, die du addierst, brauchen noch nicht einmal gleich zu sein - es genügt, wenn sie kongruent modulo $n$ sind. Wenn also außerdem

gilt, dann gilt auch

Im Grunde genommen ist dir dies vertraut, denn zum Beispiel ist ja $14 \equiv 4 \pmod {10}$, und wenn du auf der linken Seite 23 und auf der rechten Seite 13 addierst, also zwei Zahlen, die ebenfalls kongruent modulo 10 sind, dann bleibt die Kongruenz erhalten: $14 + 23 \equiv 4 + 13 \pmod{10}$.

Verknüpfungstreu bezüglich Multiplikation

Die Verknüpfungstreue gilt auch für die Multiplikation:

Modulo $n$ reduzieren

Besonders interessant ist es , wenn du auf beiden Seiten der Kongruenz jeweils Zahlen addierst (oder subtrahierst), die kongruent 0 modulo $n$ sind - denn 0 kannst du ohne Weiteres jederzeit addieren oder subtrahieren, ohne dass sich etwas ändert.

Eine Zahl ist kongruent 0 modulo $n$, wenn sie ein Vielfaches von $n$ ist. Wenn du von einer Zahl ein Vielfaches von $n$ subtrahierst, dann sagt man auch, du reduzierst sie modulo $n$.

Beispiel 1

Du willst zum Beispiel ausrechnen, welcher Wochentag in $2$ Jahren und $12$ Tagen ist. Es ist

Hierbei reduzierst du die vorkommenden Zahlen so früh wie möglich modulo $7$, also zum Beispiel reduzierst du $365$ zu $1$, denn es ist $365 \equiv 1 \pmod 7$.

Das Ergebnis am Ende ist $0$, also derselbe Wochentag wie heute.

Beispiel 2

Und welcher Wochentag ist heute in $2^{999}$ Tagen?

Also Donnerstag, wenn heute Mittwoch ist.