Ok, jetzt brauchen wir genau diesen Beweis für die nächsten Schritte. Also wir können jetzt davon ausgehen, wenn A B teilt, dass wir wissen, wie die Primfaktorzerlegung aussieht. Nämlich, dass alle MPs leider gleich in MPs sind. Und umgedreht.

So, jetzt bewegen wir uns mal auf die Primfaktorzerlegung eines größten gemeinsamen Teilers hin. Und dann machen wir mal ein Beispiel.

Mal kurz überlegen. Nehmen wir nochmal die 180, die hatten wir schon mal gehabt. 180 ist 2² mal 3² mal 5 hoch 1.

Und dann nehmen wir nochmal eine andere. Nehmen wir mal die 600.

Primfaktorzerlegung der 600. Was ist die Primfaktorzerlegung der 600?

2 hoch 3 mal, genau, richtig. 2 hoch 3 mal 3 hoch 1 mal 5 hoch 2. Die 100 kriegen wir leicht hin, da ist auf jeden Fall die 5² drin.

Und die 2² und dann nochmal 6 ist 2 mal 3. Was ist denn der GGT von A und B?

Der GGT ist 2. G größer. Ja, der größte gemeinsame Teiler. Der kleinste gemeinsame Teiler wäre die 1. Der größte gemeinsame Teiler?

5. 5? Gibt es noch größer? 5? 60. 60, genau. GGT ist 60. Was ist die Primfaktorzerlegung der 60? 2² mal 3 mal 5.

So, 2² mal 3 mal 5. Genau, 4 mal 15. Fällt Ihnen etwas auf?

Schauen Sie sich mal die Primfaktorzerlegungen an der beiden Zahlen und die Primfaktorzerlegungen des größten gemeinsamen Teilers.

Moment, langsam, ich muss mal wiederholen wegen dem Film. Ich schau mir die Exponenten an und Sie haben gesagt, das muss reinpassen. Und die 2², die passt jetzt hier in beide Reihen und in das hier gerade so. Das heißt, Sie nehmen hier den kleineren von beiden

und schreiben ihn da unten hin. Genau. Und dann? Geht's weiter? Bei der 3? Ja. Also 3 hoch 1 passt da rein und passt da rein. Deswegen kann der größte gemeinsame Teiler beide hier teilen.

3² dürfte es nicht mehr sein, weil der würde nur noch da reinpassen, aber nicht da. Er passt gerade so in den kleineren von beiden rein. Also ich nehme mir einfach den kleineren von beiden, den kleinen Exponenten von beiden, okay? Ja, genau, geht eben weiter hier. Nehme ich mir hier wieder den kleineren von beiden. Ich nehme mir jeweils den kleineren von beiden Exponenten,

die zur jeweiligen Primzahl passen, bastel die zusammen und komme auf den größten gemeinsamen Teiler. So, und das ist auch tatsächlich das, was wir gleich zeigen werden. Seien a und b Element n ohne 1

mit a gleich Produkt hier wie eben. Und b genauso.

Dann ist oder dann gilt der größte gemeinsame Teiler von a und b hat die folgende Primfaktorzerlegung.

Ich nehme p hoch und jetzt nehme ich den kleineren von beiden Exponenten jeweils. Minimum von mp und np. Minimum bedeutet einfach, nimm die kleinste Zahl von denen, die hinten drin stehen.

Also wenn mp kleiner ist als np, dann ist min mp np gleich mp. Und wenn np kleiner ist, dann ist es eben np. Und wenn die beiden gleich sind, dann ist es sowieso wurscht, dann ist es einer von beiden. Also immer den kleineren von beiden nehmen und als Exponenten zufügen

und dann kriegen sie die entsprechende Primfaktorzerlegung des größten gemeinsamen Teilers. Ja? Doch. Sehr schön. Ah, wundervolle Frage. Muss man das jetzt nicht beweisen? Genau. Ja, das darf man nicht einfach so hinschreiben.

Das ist ein Satz, der bewiesen werden muss. Ja, das ist ein Satz. Schreiben wir mal Satz drüber hier. Und jetzt kommt der Beweis.

So, und zwar teilen wir den Beweis in zwei Teile ein. Wir sagen erst mal, dieses g hier, das genau so gebastelt wird, ist ein gemeinsamer Teiler von a und b.

Wir gucken erst mal, ist dieses komische Produkt hier überhaupt in der Menge der gemeinsamen Teiler von a und b? Und dann zeigen wir noch, dass es der größte ist. Also erst mal zeigen wir, dass dieses g Element ist in ta geschnitten mit tb.

Also dieses g ist ein gemeinsamer Teiler. Und zweitens, g ist der größte gemeinsame Teiler von a und b. Also erst mal gucken, ist er überhaupt in der Menge der gemeinsamen Teiler? Und dann zeigen wir noch, aha, ist sogar der größte da drin.

Q1. Also wir wollen zeigen, dass der hier drin ist. Wir wissen folgendes. Wir wissen unser Exponent hier, jeweils für alle Primzahlen natürlich des Schenkelwerts.

Also der Exponent zu einer Primzahl von g ist auf jeden Fall mal kleiner gleich dem mp. Und außerdem ist der Exponent genau der gleiche, ist auch kleiner gleich dem np.

Die Exponenten der Primfaktorzerlegung von g, diese hier, sind jeweils kleiner gleich dem np und kleiner gleich dem np. Logisch, ne? Ich nehme vom np und np das kleinere von beiden.

Das ist ja das min. Und das kleinere von beiden ist natürlich kleiner gleich den beiden. Wenn Sie zwei Zahlen haben, Sie nehmen die kleinere von beiden Zahlen, dann ist die kleinere von beiden Zahlen kleiner gleich dieser beiden Zahlen. Drei und fünf nehmen die kleinere drei, drei ist kleiner gleich drei und drei ist kleiner gleich fünf.

Das bedeutet aber, mit dem Teilbarkeitskriterium, wenn alle Exponenten von g kleiner gleich np sind, dann bedeutet das g teilt a. Und das hier bedeutet nach dem Teilbarkeitskriterium g teilt b.

Haben wir ja gesagt, Teilbarkeitskriterium, wenn alle Exponenten kleiner gleich sind, dann teilt die eine Zahl die andere. Das ist die Rückrichtung vom Teilbarkeitskriterium. So und g teilt a und g teilt b. Daraus folgt g ist Element der gemeinsamen Teilermenge von a und b.

Das war leicht. Oh Gott, das darf man niemals sagen. Das darf man niemals sagen, auch niemals im Unterricht sagen, das war leicht. Wenn Sie dann da sitzen und denken, oh, das war schwer und dann sagt der Dozent vorne, das war leicht, dann sind Sie deprimiert.

Ich muss ganz anders machen. Das war jetzt ganz schön knifflig. Ganz schön knifflig hier die Sache.

So, jetzt gehen wir zum Teil Nummer zwei. Jetzt zeigen wir, also jetzt wissen wir, dieses g hier, das wir uns gebastelt haben, ist in der gemeinsamen Teilermenge. Und jetzt zeigen wir noch, dass es der größte gemeinsame Teile ist. Wie machen wir das?

Wir zeigen, dass alle Elemente in der Menge der gemeinsamen Teile kleiner gleich diesem g sind. Also ich nehme die Menge der gemeinsamen Teile und sage, ich nehme mal irgendein beliebiges Element aus ta geschnitten tb raus. Ich nehme mir irgendeinen gemeinsamen Teiler und zeige, der ist kleiner als mein g.

So mache ich das folgendermaßen. Mein t ist ja jetzt in der Teilermenge von a, also teilt ta. Weil ta teilt, geht es nach dem Teilbarkeitskriterium.

Oder sagen wir mal, das müsst ihr vielleicht noch eine Primfaktorzerlegung überlegen. Mit t ist gleich die Primfaktorzerlegung hoch tp. Weil ta teilt, gilt nach dem Teilbarkeitskriterium für alle p, dass tp kleiner gleich np ist.

Außerdem teilt tb. Daraus folgt, dass tp kleiner gleich np ist.

Nach dem Teilbarkeitskriterium. So, und wenn jetzt alle tp kleiner sind, also wenn tp kleiner als np ist und kleiner als np, dann ist es auch kleiner als den kleineren von beiden. Es ist ja kleiner als beiden, also es ist auch kleiner als den kleineren von beiden.

Also folgt daraus, tp kleiner als min. mp, np. Ich nehme den kleineren von beiden, das ist ja entweder der oder der und jedes Mal ist tp kleiner als der. Okay, daraus folgt tp.

Das gilt für alle Primzahlen, das heißt tp kleiner als min, mp, np, das ist aber gerade der Exponent von g. Und das bedeutet nach dem Teilbarkeitskriterium, dass tg teilt. Und weil tg teilt, folgt daraus, dass t kleiner als g ist.

Und daraus folgt, dass alle Elemente, weil das hier oben fest aber beliebig war, alle Elemente aus der gemeinsamen Teilermenge sind kleiner als dem g. Also das g ist der größte gemeinsame Teiler.

Ach, ist das schön. Das ist doch super, oder? Ah, ist das toll.