ūüéď Ui, fast schon Pr√ľfungszeit? Hier geht's zur Mathe-Pr√ľfungsvorbereitung.
Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

Kongruenz von Zahlen

Bild

Zwei ganze Zahlen sind genau dann kongruent modulo nn, wenn sie bei Division durch die nat√ľrliche Zahl nn den gleichen Rest ergeben.

Kongruenz nat√ľrlicher Zahlen

Bild

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

Warum ist das so?

Weil 2424 und 3131 kongruent modulo 77 sind. Dies bedeutet, dass 2424 und 3131 bei Division durch 77 denselben Rest ergeben (nämlich 33).

Es ist nämlich

24=3‚čÖ7¬†Rest¬†3¬†24=3\cdot7~\text{Rest}~3 ~ sowie

31=4‚čÖ7¬†Rest¬†331 = 4 \cdot 7 ~ \text{Rest} ~ 3

Es gibt 77 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 nn festlegst, bez√ľglich derer du die Kongruenz betrachtest. Ob zwei Zahlen kongruent zueinander sind, ist also abh√§ngig von der Zahl nn (dem Modul) und dem Rest, den sie bei der Division durch nn ergeben. Ist dieser Rest bei beiden Zahlen gleich, dann sind die Zahlen kongruent modulo nn, andernfalls sind sie inkongruent modulo nn.

Merke

Allgemein schreibst du aa ist kongruent zu bb modulo nn folgendermaßen:

In Klammern gibst du ganz am Ende der Formel an, bez√ľglich welchen Moduls nn die Kongruenz gilt.

Beispiel

1) Aus der Rechnung von oben:

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

Gegenbeispiele

Erklärung:

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

1515 hat also einen anderen Rest als 2626, wenn man beide Zahlen durch 77 teilt. 1515 und 2626 sind nicht kongruent.

Kongruenz negativer, ganzer Zahlen

Was ist mit den Zahlen 124124 und ‚ąí124-124? Sind diese kongruent modulo 1010?

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

Aber die Zahlen 125125 und ‚ąí125-125 sind, obwohl die gleiche Argumentation gilt, dennoch kongruent modulo 1010.

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 nn". Diese ist hier:

Merke

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

Allgemein lautet diese Definition also folgenderma√üen, f√ľr alle ganzen Zahlen aa und bb und f√ľr jede nat√ľrliche Zahl nn:

Der senkrechte Strich | bedeutet "teilt". Die Zahl nn teilt die Differenz a‚ąíba - b. Oder die Differenz a‚ąíba-b ist durch nn teilbar.

Beispiel

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

Defintion des "Rests"

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

DefinitionRest

Der Rest bei Division einer ganzen Zahl aa durch eine nat√ľrliche Zahl nn ergibt sich als diejenige Zahl rr, f√ľr die

wobei kk eine ganze Zahl ist.

Du stellst also die Zahl aa als Vielfaches von nn dar plus eine möglichst kleine, aber nichtnegative Zahl rr. Du kannst jede ganze Zahl auf diese Weise eindeutig darstellen.

Schau dir das folgende Beispiel an.

Beispiel

Wenn du die Definition mit a=‚ąí124a = -124 und n=10n=10 anwendest, erh√§ltst du

Der Rest betr√§gt also r=6r = 6, ist also verschieden vom Rest r=4r=4 bei a=124a = 124. Daher sind 124124 und ‚ąí124-124 nicht kongruent modulo 10.

Bei den Zahlen 125125 und ‚ąí125-125 dagegen betr√§gt der Rest in beiden F√§llen 55. Daher sind diese beiden Zahlen kongruent modulo 1010.

Operation mod

Die Operation ‚Äämod‚Ää\bmod liefert genau diesen Rest, der sich bei Division einer ganzen Zahl aa durch nn ergibt

Beispielsweise ist 24‚Äämod‚Ää7=324 \bmod 7 = 3. Denn 2424 ergibt bei Division durch 77 den Rest 33. Damit ist automatisch 24‚Č°3¬†(mod¬†7)24\equiv 3 ~ (\text{mod}~7). Beachte aber den Unterschied zwischen der Operation ‚Äämod‚Ää\bmod und der Kennzeichnung einer Kongruenz durch ‚Äämod‚Ää\bmod in Klammern. Es ist beispielsweise auch 24‚Č°10‚ÄČ‚Ā£(mod7)24 \equiv 10 \!\pmod 7.

Rechnen mit Kongruenzen

Das Sch√∂ne an der Relation "kongruent modulo nn" 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 nn sind. Wenn also au√üerdem

gilt, dann gilt auch

Im Grunde genommen ist dir dies vertraut, denn zum Beispiel ist ja 14‚Č°4(mod10)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‚Č°4+13(mod10)14 + 23 \equiv 4 + 13 \pmod{10}.

Verkn√ľpfungstreu bez√ľglich Multiplikation

Die Verkn√ľpfungstreue gilt auch f√ľr die Multiplikation:

Modulo nn reduzieren

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

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

Beispiel 1

Du willst zum Beispiel ausrechnen, welcher Wochentag in 22 Jahren und 1212 Tagen ist. Es ist

Hierbei reduzierst du die vorkommenden Zahlen so fr√ľh wie m√∂glich modulo 77, also zum Beispiel reduzierst du 365365 zu 11, denn es ist 365‚Č°1(mod7)365 \equiv 1 \pmod 7.

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

Beispiel 2

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

Also Donnerstag, wenn heute Mittwoch ist.


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 ‚Üí Was bedeutet das?