Wo sind wir, wo haben wir vor den Ferien aufgehört? Wir haben aufgehört mit dem größten gemeinsamen Teiler und dem kleinsten gemeinsamen Vielfachen. Größter gemeinsamer Teiler beispielsweise, erinnern sich, hatten wir folgendermaßen definiert.

Wir nehmen, haben zwei Zahlen A und B, zwei natürliche Zahlen. Wir betrachten die Teilermenge der beiden Zahlen, schneiden die beiden Teilermengen, damit haben wir die gemeinsamen Teiler, beide Zahlen. Und dann nehmen wir aus dieser Schnittmenge der beiden Teilermengen die größte Zahl.

Und das ist der größte gemeinsame Teiler. Also ich habe die Menge der gemeinsamen Teiler und dann den größten gemeinsamen Teiler. Heute machen wir nahtlos weiter und zwar beschäftigen wir uns mit der Bestimmung des größten gemeinsamen Teilers. Nehmen wir mal ein Beispiel. Sie haben zwei Zahlen, 693 und 286 zum Beispiel.

Und jetzt wollen Sie davon den größten gemeinsamen Teiler bestimmen. Gucken ob das die Zahlen sind, die ich mir belegt hatte, genau.

Wie würden Sie vorgehen, größter gemeinsamer Teiler, wie kann man den bestimmen? Genau, das ist eine Möglichkeit, man bildet von beiden Zahlen die Primfaktorzerlegung.

Wie geht man da vor? Primfaktorzerlegung bilden, genau. Man teilt erstmal durch die kleinste bekannte Primzahl, zwei, so lange bis Sie nicht mehr durch zwei teilen können.

Dann nehmen Sie drei, dann nehmen Sie fünf, sieben und so weiter. Alle Primzahlen nach der Reihe bis Sie eine vollständige Primfaktorzerlegung beider Zahlen haben. Und wie kann man dann den größten gemeinsamen Teiler bestimmen, wenn man die Primfaktorzerlegung beider Zahlen hat?

Laufen wir mal ein bisschen warm hier, melden sich nur zwei von 100, kann doch gar nicht sein, ja? Bitte? Die größten beiden Zahlen, die nicht mehr zerlegt werden können, was meinen Sie damit?

Sie bilden aus dieser Primfaktorzerlegung die größte Zahl aus den jeweiligen Primfaktoren, die noch in beiden drin sind.

Oder anders formuliert? Ja? Sie gucken, welche Primzahlen Sie in beiden Zerlegungen drin haben. Genau, wenn Sie jetzt die Primfaktorzerlegung haben mit den jeweiligen Exponenten, da gab es eine Regel. Der kleinere von beiden, das ist alles äquivalent.

Genau, als Formulierung, also Sie gucken sich die Primfaktorzerlegung an mit den jeweiligen Exponenten bei den Primzahlen, nehmen jeweils den kleineren von beiden und damit haben Sie den größten gemeinsamen Teiler, wenn Sie diese Primfaktorzerlegung dann bilden. So, das ist allerdings ziemlich aufwendig. Wenn wir jetzt hier mal schauen, bei den Zahlen geht es noch, da ist man relativ schnell fertig.

Aber jetzt nehmen wir mal eine Zahl von dieser Größe hier.

So, jetzt bilden Sie mal eine Primfaktorzerlegung davon. Ach so, naja, gut, vielleicht nehmen wir die schon gerade, das ist vielleicht ein bisschen ungünstig, nehmen wir die da. Jetzt fangen Sie an, hier Primfaktorzerlegungen zu machen.

Sehr aufwendige Geschichte. Stellen Sie sich mal vor, die erste Primzahl, die da echte Primzahl ist 83 oder so. Das ist wahnsinnig aufwendig. Okay, kann man sich vorstellen, Computer schaffen das auch noch relativ schnell. Aber jetzt nehmen Sie beispielsweise mal eine Zahl mit einer Million Stellen.

Da sind Sie beschäftigt, da sind sogar Computer beschäftigt. Eine Primfaktorzerlegung zu erstellen von sehr, sehr, sehr, sehr, sehr großen Zahlen ist ein schwieriges Problem.

Auf diesem Problem beruht praktisch die gesamte Internetverschlüsselung. Es gibt Verschlüsselungsverfahren, RSA nennt man das. Das beruht auf der Tatsache, dass es schwierig ist, sehr, sehr, sehr, sehr, sehr, sehr große Zahlen in ihre Primfaktoren zu zerlegen.

Insbesondere, wenn diese Primfaktoren auch sehr große Zahlen sind. Nebenbei bemerkt, das ist ein schwieriges Problem, vermutet man. Es hat noch niemand gezeigt, dass es ein schwieriges Problem ist.

Es hat aber bislang auch noch niemand ein einfaches Verfahren gefunden. Es könnte passieren, dass irgendwann mal jemand drauf kommt, dass es doch ganz einfach ist, eine große Zahl in ihre Primfaktoren zu zerlegen. Und dann kann man sich das Verschlüsselungsverfahren RSA schenken. Deswegen arbeitet man auch fieberhaft an anderen Verfahren.

Aber RSA ist eins der gebräuchlichsten Verschlüsselungsverfahren im Internet. Das heißt, Primfaktorzerlegung erstellen von sehr großen Zahlen ist schwierig oder aufwendig, dauert lange. Wenn man den GGT bestimmen will, wäre es nett, wenn man eine andere Möglichkeit hätte.

Und das schauen wir uns heute an. Ich werde Ihnen heute ein Verfahren vorstellen, mit dem man sehr schnell den größten gemeinsamen Teil bestimmen kann. Und bevor wir das machen, müssen wir uns erstmal etwas anderes anschauen.

Nämlich Division mit Rest. Ich schreibe Ihnen erstmal die Definition hin.

Oder den Satz, was bedeutet, dass eine Zahl dividierbar ist mit Rest durch eine andere. Dann machen wir ein paar Beispiele dazu.

Zwei Zahlen, eine aus Z, eine aus N. Sie könnten sich hier auch auf N einschränken. Wir werden später auch A nur aus N wählen.

Aber theoretisch kann man es ein bisschen allgemeiner fassen mit A aus Z. Also A-Element aus Z und B aus N. Dann existiert genau ein Zahlenpaar Q und R aus N.

Quatsch aus Z mit A ist gleich Q mal B plus R und kleiner gleich R kleiner B.

Division mit Rest. Seien A aus Z und B aus N, also ich habe zwei Zahlen A und B, eine aus Z und eine aus N. Dann gibt es genau ein Zahlenpaar Q und R, sodass A folgendermaßen dargestellt werden kann. A ist Q mal B plus R. Ich habe A und B gegeben und ich finde jetzt das Q so, dass Q mal B plus R A ergibt.

Aber R muss zwischen Null und B liegen. Also kann Null sein, darf aber nicht B sein. Er muss hier dazwischen liegen. Machen wir mal ein Beispiel, was es bedeutet hier. Nehmen wir mal A 15 und B 6.

So und die nennen wir jetzt mal bitte Q und R.

Bleiben wir noch einen Moment. Wir müssen ein paar abschreiben und denken und so. Genau. Q ist 2 und R ist 3. Q ist 2 und R ist 3, denn 15 ist gleich Q mal B 2 mal 6 plus 3.

Hätte man Q auch anders wählen können?

Ja? Wie denn zum Beispiel? 1. Ja dann ist 1 mal 6 plus 9. Warum geht das nicht? R muss kleiner B sein. Genau, also R muss kleiner sein als 6.

So, genau. Machen wir ein anderes Beispiel. Nehmen wir jetzt mal A gleich minus 15 und B gleich 6. Nennen Sie jetzt mal Q und R.

Schwierig. Ja. Q minus 2, R minus 3.

Warum? R darf nicht kleiner Null sein. Oder hatten Sie R gleich 3 gesagt? Genau, R darf nicht kleiner Null sein. Also R muss zwischen Null und B liegen. Sie haben gesagt was?

Minus 3 und 3. Denn minus 15 ist gleich minus 3 mal 6. Das ist minus 18 plus 3. Minus 3 und 3. So. Okay. Also man muss eine Zerlegung von A so finden, dass das was übrig bleibt, der Rest.

Dass der Rest eben kleiner ist als das, wodurch ich dividiere letztlich. Division mit Rest. Man dividiert A durch B und es bleibt was übrig, was kleiner ist als B, sonst wäre es ja nicht der Rest.

Sonst habe ich falsch dividiert. Und ein bisschen ungewöhnlich ist, wenn man A aus Z-Welt, also A-Negativ-Welt aus negativen ganzen Zahlen, aber da kann man sich auch dran gewöhnen mit ein bisschen Übung. Jetzt ist das hier ein Satz, muss man auch beweisen.

Und das machen wir jetzt. Wir haben zwar so intuitiv eine Begründung oder eine Vorstellung davon, dass es genau einen Zahlenpanel geben kann. Wir können kein anderes finden, aber weil wir Mathematiker sind und wenn wir so einen Satz aufstellen, muss man den Satz auch beweisen, damit wir sicher sind, dass es auch stimmt.

Machen wir jetzt mal. Satz beweisen.