Kongruenz von Zahlen

Kongruenz natürlicher Zahlen

Du kennst dich mit Kongruenz modulo $7$ bereits gut aus: Du weißt, dass Heiligabend und Silvester immer auf den gleichen Wochentag fallen.

Warum ist das so?

Weil $24$ und $31$ kongruent modulo $7$ sind. Dies bedeutet, dass $24$ und $31$ bei Division durch $7$ denselben Rest ergeben (nämlich $3$ ).

Es ist nämlich

$24=3\cdot7~\text{Rest}~3 ~$ sowie

$31 = 4 \cdot 7 ~ \text{Rest} ~ 3$

Es gibt $7$ Wochentage, und wenn Heiligabend, also der 24. Dezember, auf einen Mittwoch fällt, dann fällt auch Silvester, also der 31. Dezember, auf einen Mittwoch.

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$ .

Merke

Allgemein schreibst du $a$ ist kongruent zu $b$ modulo $n$ folgendermaßen:

\displaystyle a\,\equiv\,b \pmod n

In Klammern gibst du ganz am Ende der Formel an, bezüglich welchen Moduls $n$ die Kongruenz gilt.

Beispiel

1) Aus der Rechnung von oben:

\displaystyle 24\,\equiv\,31 \pmod 7

2) Alle positiven Zahlen, die auf dieselbe Ziffer enden, sind kongruent modulo 10, du kannst die Kongruenz mehrerer solcher Zahlen in eine Zeile schreiben:

\displaystyle 14\,\equiv\,84\,\equiv\,124\,\equiv\,4\,\equiv\,54 \pmod{10}

Gegenbeispiele

\displaystyle 15\,\not\equiv\,26 \pmod 7

Erklärung:

$15:7=2\ \text{Rest}\ 1$ , aber $26:7=3\ \text{Rest}\ 5$ .

$15$ hat also einen anderen Rest als $26$ , wenn man beide Zahlen durch $7$ teilt. $15$ und $26$ sind nicht kongruent.

Kongruenz negativer, ganzer Zahlen

Was ist mit den Zahlen $124$ und $- 124$ ? Sind diese kongruent modulo $10$ ?

Beide enden auf die Ziffer 4. Aber die erste Zahl ergibt bei Division durch 10 den Rest 4, die andere den Rest $- 4$ , also nicht den gleichen Rest. Also sind sie nach dem bisher Erklärtem nicht kongruent modulo $10$ , und das ist auch korrekt.

Aber die Zahlen $125$ und $- 125$ sind, obwohl die gleiche Argumentation gilt, dennoch kongruent modulo $10$ .

Wie kann das sein? Kannst du der Mathematik nicht mehr trauen?

Doch, aber du brauchst eine genaue Definition von "Rest" und am besten auch noch eine bessere Definition von "kongruent modulo $n$ ". Diese ist hier:

Merke

Zwei ganze Zahlen sind kongruent modulo $n$ , wenn ihre Differenz durch $n$ teilbar ist.

Allgemein lautet diese Definition also folgendermaßen, für alle ganzen Zahlen $a$ und $b$ und für jede natürliche Zahl $n$ :

\displaystyle a\,\equiv\,b \pmod n ~~~\Leftrightarrow ~~~ n~|~a-b

Der senkrechte Strich | bedeutet "teilt". Die Zahl $n$ teilt die Differenz $a - b$ . Oder die Differenz $a - b$ ist durch $n$ teilbar.

Beispiel

Wenn du diese Definition anwendest, siehst du, dass $124 - (- 124) = 248$ nicht durch 10 teilbar ist, $125 - (- 125) = 250$ dagegen sehr wohl.

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:

DefinitionRest

Der Rest bei Division einer ganzen Zahl $a$ durch eine natürliche Zahl $n$ ergibt sich als diejenige Zahl $r$ , für die

\displaystyle a = k \cdot n + r ~~~ \text{mit} ~~~ 0\le r\lt n

wobei $k$ eine ganze Zahl ist.

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.

Beispiel

Wenn du die Definition mit $a = - 124$ und $n = 10$ anwendest, erhältst du

\displaystyle -124=-13\cdot10+6~~~\text{mit}~~~0\le6<10

Der Rest beträgt also $r = 6$ , ist also verschieden vom Rest $r = 4$ bei $a = 124$ . Daher sind $124$ und $- 124$ nicht kongruent modulo 10.

Bei den Zahlen $125$ und $- 125$ dagegen beträgt der Rest in beiden Fällen $5$ . Daher sind diese beiden Zahlen kongruent modulo $10$ .

Operation mod

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

\displaystyle a\bmod n = r~~~\Leftrightarrow~~~a=k\cdot n+r~~\wedge~~0\le r<n

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

\displaystyle a ~\equiv~ b \pmod n

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

\displaystyle a + c ~\equiv~ b + c \pmod n

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

\displaystyle c ~\equiv~ d \pmod n

gilt, dann gilt auch

\displaystyle a+c ~\equiv~ b+d \pmod n

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:

\displaystyle a \equiv b \pmod n ~~~ \wedge ~~~ c \equiv d \pmod n ~~~\Rightarrow ~~~ a \cdot c \equiv b \cdot d \pmod n

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

\displaystyle 2 \cdot 365 + 12 ~\equiv~ 2 \cdot 1 + 5 ~\equiv~ 7 ~\equiv~ 0 \pmod 7

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?

\displaystyle 2^{999} ~\equiv~ (2^3)^{333} ~\equiv~ 8^{333} ~\equiv~ 1^{333} ~\equiv~ 1 \pmod 7

Also Donnerstag, wenn heute Mittwoch ist.

Kongruenz natürlicher Zahlen

Kongruenz negativer, ganzer Zahlen

Defintion des "Rests"

Operation mod

Rechnen mit Kongruenzen

Verknüpfungstreu bezüglich Addition

Verknüpfungstreu bezüglich Multiplikation

Modulo nnn reduzieren

Modulo $n$ reduzieren