Ok, jetzt starten wir inhaltlich. Letzte Woche haben wir uns beschäftigt mit dem euklidischen Algorithmus. Der euklidische Algorithmus dient der Findung des größten gemeinsamen Teilers zweier ganzer Zahlen. Euklidischen Algorithmus haben wir durchgesprochen, wie der funktioniert

und so, das haben sie auch geübt in der Übung oder werden sie noch üben. Zur Definition oder zur Formulierung des Algorithmus haben wir die Division mit Rest benötigt. Und

mit der Division mit Rest machen wir heute weiter. Genauer gesagt, wir beschäftigen uns mit Resten. Ich schreibe mir mal die Kurzdefinition der Division mit Rest an der Tafel. Sie erinnern sich, Sie haben eine ganze Zahl A und eine natürliche Zahl

B. Also schreibt noch mal hin hier A aus Z, B aus N. Dann existieren eindeutig, es gibt nur ein paar, schreibt es trotzdem mal hin hier Q, QN Element Z, eindeutig

mit A ist gleich Q mal B plus R, nicht N, hier R. Also Q mal B plus R, wobei,

und das ist auch entscheidend, der Rest R liegt zwischen Null und B, darf aber nicht B werden, also zwischen Null und B minus 1, wenn man so will. Das ist die Division

mit Rest. Und am Ende der letzten Stunde habe ich Ihnen nur so ein bisschen angehängt zwei Operationsdefinitionen. Q bezeichnet man auch als A Div B. Also Div ist die

Division, die ganzzahlige Division, wenn Sie so wollen. Der Rest wird abgeschnitten. Und R ist A Mod B oder Modulo B. So, noch mal ein Beispiel. 27 ist gleich mal plus

R. Was ist Q und was ist R? Also A Div B, 27 Div 8 ist 3, genau. Und R, das heißt

A Mod B, 27 Mod 8 ist was? Auch 3, tolles Beispiel. Wenn ich 27 Mod 8 hinschreibe, dann kann ich schreiben, das ist gleich 3. 27 Mod 8 gibt den Rest an bei Division durch

8 und das ist in diesem Fall 3. Und jetzt schauen wir uns mal Zahlen an, die bezüglich der Division einer bestimmten Zahl denselben Rest ergeben. Nennen Sie mir nochmal eine

andere Zahl, die Mod 8 denselben Rest ergibt, ein Q. Q ist gleich A Div B, in dem Fall 3. Sagen Sie mir nochmal eine andere Zahl, die Mod 8 3 ergibt. Bitte? Mit 8, die Mod

8. 83, ja stimmt, das ist auch nicht einfacher. 36, 36. Ja, ich will aber zahlen die 3 Mod 8, also bei den 3 rauskommt der Rest. 11, genau. Jetzt noch einfacher. 3, genau. 3 ergibt

Mod 8 auch 3. Sagen Sie mir nochmal eine negative Zahl, die Mod 8 3 ergibt. Oh jetzt

ist aber kompliziert, jetzt suchen wir mal. Ja, Sie haben aber recht. Minus 29. Minus 29 Mod 8 ist gleich 3. Denn, können Sie es begründen? 8 mal minus 4, also minus 29

ist gleich minus 4 mal 8, das ist mein Q, ne? Plus 3, genau. Sie müssen bei den negativen

Zahlen immer erstmal überholen. Sie müssen erstmal ein bisschen kleiner werden als die Zahl noch, also Sie müssen hier auf die minus 32 kommen, um dann den Rest drauf zu addieren, denn der Rest ist immer positiv, ne? Genau. Ok, so. Jetzt betrachten

wir mal genau die Zahlen, die bezüglich eines Divisors denselben Rest ergeben. Also

hier teilen wir immer mit Division durch 8 und betrachten mal die Zahlen, die, wenn man durch 8 dividiert, denselben Rest ergeben, bei denen Mod 8 immer das Gleiche rauskommt. Und das ist die Definition von Konkruenz. Konkruenz sei m Element n und seien a, b

z. Wir haben zwei Zahlen a, b aus z und m aus n. Dann, schau mal hin, a Konkruent zu b Modulo m,

genau, dann werden Mod m gleich b Mod m. Also, ich habe zwei Zahlen a und b und a heißt

Konkruent zu b Modulo m, genau dann, wenn beide denselben Rest lassen, wenn man durch m teilt.

Da, ich teile a durch m, ich teile b durch m mit Rest, gucken wir die beiden Reste an, wenn die gleich sind, dann ist a Konkruent zu b Modulo m. Also durch m wird geteilt und ich schau mal an, wenn ich a durch m teile und b durch m teile, bleibt derselbe Rest. Wenn ja,

sind sie Konkruent, wenn nein, sind sie nicht Konkruent. Ok? Man schreibt dann auch Konkruent b, Konkruenzzeichen, es sind so drei Striche, ein gleicher Zeichen mit drei Strichen

und hinten dran Modulo m. So, jetzt müssen sie stark sein. Mod m hat zwei unterschiedliche

Bedeutungen sozusagen. Ich kann so schreiben, a Mod m, dann ist Mod ein Operator und sagt der Rest bei a durch m, das ist das Ergebnis dieses Ausdrucks hier und das Ergebnis dieses

Ausdrucks ist gleich das Ergebnis dieses Ausdrucks. Also ich kann Mod als Operator verwenden, a Mod m gibt mir den Rest. Wenn ich es so hinschreibe, dann dürfen sie nicht denken, dass hier b Mod m steht und hier auf der Seite sozusagen der Rest rauskommt oder so, sondern es ist so geklammert, wenn ich so hinschreibe. Das heißt einfach a Konkruent b und ich gebe

noch die Zusatzinformation durch welche Zahl ich teile. Zwei Zahlen sind ja nur dann Konkruent, also ich kann nur eine Aussage über Konkruenz machen, wenn ich auch weiß, wodurch ich teile. Zwei Zahlen können bezüglich einem m Konkruent sein und bezüglich eines anderen nicht. In

sofern muss man immer dazuschreiben, also das ist nur ein Dazuschreiben zu diesem Ausdruck hier, bezüglich welchem Diviso ich die ganze Geschichte denke. Man kann jetzt also

schreiben, wenn man ein Beispiel macht, nehmen wir mal das, was wir hier haben. Zum Beispiel 27 ist Konkruent minus 29 Modulo 8. Kann man so schreiben? Das bedeutet 27 und minus 20 lassen

bei Division durch 8 denselben Rest. Das ist also eine Aussage hier, die wahr oder falsch sein kann, während das hier keine Aussage ist, sondern da kommt ein Ergebnis raus, nämlich der

Rest. So, das ist also Konkruenz. Gibt es eine Frage an der Stelle? Kann ich nutzen um Kaffee zu trinken?

Nö, alles klar, gut.