Okay, jetzt bewegen wir uns auf eine Aussage hin, oder anders gesagt, jetzt

untersuchen wir mal, wie der GGT und das KGV zusammenhängen mit der Primfaktorzerlegung einer Zahl. Wir haben uns damit Primfaktorzerlegung

beschäftigt. Wenn ich so eine Primfaktorzerlegung von A und B habe, welche Primfaktorzerlegung hat dann der größte gemeinsame Teiler? Und welche Primfaktorzerlegung hat das kleinste gemeinsame Vielfache? Da bewegen wir uns jetzt mal darauf hin. Und bevor wir uns damit beschäftigen können, muss ich

noch etwas nachholen, was wir bislang nicht gemacht haben, nämlich wir müssen was beweisen, das sogenannte Teilbarkeitskriterium.

Teilbarkeitskriterium. Und zwar besagt das das Folgende. Fangen wir mal wieder an, hinzuschreiben, was man so braucht. Seien A, B, Element N ohne die 1, weil wir die Primfaktorzerlegung nur für Zahlen definiert haben, die größer

sind als 1. Seien A, B, Element N mit zwei Primfaktorzerlegungen. A hat mal folgende Primfaktorzerlegung. Ich nehme hier alle Primzahlen,

multipliziere sie alle Primzahlen, potenziere sie erst mal mit dem Exponenten mp, also mit dem Exponenten, der zur jeweiligen Primzahl gehört und multipliziere die alle miteinander. Das ist einfach allgemeine Darstellung der Primfaktorzerlegung. Und B hat ebenfalls eine Primfaktorzerlegung.

Wieder das Produkt über alle Primzahlpotenzen mit den jeweiligen

passenden Exponenten dazu. Gestern wurde ich darum gebeten, das nochmal kurz ein Beispiel zu erläutern. Sollte man machen. Ist schon sehr abstrakt die Geschichte hier mit dem Produktzeichen. Das mache ich mal da rechts, weil dann kann ich links schöne Beweise entwickeln. Also nehmen wir mal ein Beispiel, nehmen

wir mal die 180. A sei mal 180. Was ist denn die Primfaktorzerlegung in 180?

Na komm, das muss schnell gehen. 180 Primfaktorzerlegung. Richtig, sehr schön. 2 x 2 x 3 x 3 x 5. Also 2 x 2 x 3 x 3 x 5.

2 x 2 x 3 x 5. So, das heißt doch, mal 5 hoch 1 und jetzt kann ich mir folgendes denken. Hier hinten steht noch mal 7 hoch 0, mal 11 hoch 0, mal 13

hoch 0, mal 17 hoch 0, mal 19 hoch 0. Wie geht es weiter? Bitte? Nochmal? 23. Genau, 23 hoch 0, mal? Ja, genau und so

weiter. Primzahl bis 100 sollte man schon ratzfatz kennen hier. So, sie haben dieses YouTube-Video gesehen, was ich da reingestellt habe. 57 ist eine Primzahl. Da muss man schon ganz schön tief in die Gehirnschublade greifen.

Okay, okay. So, jetzt ist das doch hier nichts anderes, als dass sich eine Primzahl mit ihrem jeweils zugehörigen passenden Exponenten

derart multipliziere, also potenziere und das ganze multipliziere so, dass 180 rauskommt. Das heißt, letztlich habe ich doch hier P, die Primzahl P, wenn P gleich 2 ist, ist M, M von der 2 ist 2. Schreiben wir es mal so hin. M von der 3, also

Quatsch. Oh Gott, peinlich. M11 ist 0, M13 ist 0 und so weiter und so weiter.

Sehr gut aufgepasst, guter Test. Test bestanden. Okay, ja, also ich nehme mir alle Primzahlen her. 2, 3, 5, 7, 11 und so weiter. Potenziere sie mit dem entsprechenden Exponenten und bilde das Gesamtprodukt und kriege ich meine

Primfaktorzerlegung. Okay, also ich habe jetzt diese beiden Zahlen a und b in der Primfaktorzerlegung. Dann gelte a teilt b genau dann, wenn für alle P aus den

Primzahlen gilt mp kleiner gleich np. Eigentlich macht man das nicht so gerne über

die Indizes quantifizieren, aber naja gut, passt schon so. Also für alle a, b mit diesem Primfaktorzerlegung gilt a teilt b genau dann, wenn die Exponenten von a jeweils kleiner gleichen Exponenten von b. Was bedeutet das? Machen wir noch mal ein

Beispiel. Eins weiter nach links. Nehmen wir mal das Beispiel, wo a b teilt. Nehmen wir mal hier a gleich 12 und b gleich 36. Wie sind denn die

Primfaktorzerlegungen von der 12? 2² mal 3 hoch 1 und für das 36 2² mal 3².

a teilt b, außerdem gilt die jeweiligen Exponenten, also hier 2 kleiner gleich 2 und 1 kleiner gleich 2. Also die Exponenten von a sind jeweils kleiner gleich den Exponenten von b und hier hinten auch 0 kleiner gleich 0, 0 kleiner

gleich 0 und so weiter und so weiter und so weiter. a teilt b, wenn die Exponenten kleiner gleich sind. Ist hier mal ein Exponent größer bei a als der Exponent von b, kann a b nicht teilen, weil der, weil sozusagen diese Primzahlpotenz dann enthalten ist. Nehmen wir mal ein anderes Beispiel. a gleich 9 ist 3² und b

gleich 12 ist 2 hoch 1 mal 3. Quatsch, 2 hoch 2 mal 3 hoch 1. Hier ist der Exponent der 3 bei a größer als der Exponent der 3 bei b.

Das heißt 3² ist nicht in b drin, dementsprechend kann a auch b nicht teilen. Also die Exponenten von a, die Exponenten der Primzahl bei a sind alle

kleiner gleich den jeweiligen zugehörigen Exponenten bei b. So, jetzt beweisen wir das mal. Wie beweist man eine Äquivalenz? Gibt es mehrere Möglichkeiten. Eine Möglichkeit wäre, ich beginne mal auf der linken Seite und forme so lange Äquivalenz um, forme um, bis ich auf der rechten Seite rauskomme. Alternative ist, welche? Ja, nicht sie mal. Genau, erst mal die eine

Richtung, dann die andere Richtung. Machen wir erst mal die eine Richtung. Beweisen wir mal diese Richtung hier. Von links nach rechts. Wie beweist man das?

Eine Implikation, man geht mal von der linken Seite aus und versucht dann zu zeigen, dass auch die rechte gilt. Also gehen wir von der linken Seite aus. Es gelte a teilt b. Jetzt müssen wir mal schauen, dass wir da rechts

rauskommen. Es gelte a teilt b. Was können wir sagen, wenn ab teilt? Ja, richtig, genau. B ist c mal a. Nehmen wir eine andere. C ist wurscht.

Oder wollen wir q nehmen? Ja, nehmen wir q. Dann existiert ein q aus n mit a mal q gleich b. Das ist einfach die Teilbarkeitsrelationsdefinition, die

wir da eingesetzt haben. So, jetzt schreiben wir uns mal unsere q hin. q muss ja auch eine Primfaktorzerlegung haben. Sei q gleich p hoch kp jeweils.

Ich nehme ja alle Primfaktoren, multipliziere sie miteinander und dann kommt kp als Exponenten nehmen wir mal. Und jetzt setzen wir einfach mal hier ein.

Dann ist a mal, dann machen wir es auf die nächste Zeile, a mal q gleich die Primfaktorzerlegung von a.

Ich schenke mir jetzt mal das p Element p da unten drunter. Sie wissen, das wird jetzt die ganze Zeit so sein. Es steht immer p Element p, also über alle Primzahlen das Produkt. Ich schenke mir das jetzt mal, dann wird das so unübersichtlich. Also ich nehme hier p hoch mp, das ist a. Jetzt ist q

gleich p hoch kp, das Produkt über alle Primzahlen noch kp und da kommt b raus. Oder jetzt fahren wir das erst mal hier um. Dieses Produkt mal dieses Produkt, das sind ja alle Primzahlen als Produkt hingeschrieben, mal und hier wieder alle Primzahlen als Produkt mit jeweils Exponenten. Da kann ich das Kommutativgesetz anwenden.

Ich kann hier die 2 hoch mp nehmen, 2 hoch m2 und da die 2 hoch k2 und zusammen multiplizieren, was letztlich dazu führt und mit der 3, der 5, der 7, der 11 auch, dass ich hier mit dem Kommutativgesetz und dem Zusammenfassen von Potenzen hier die

Exponenten addieren kann. Das können Sie sich einfach mal so hinschreiben, wenn Sie es mal beispielhaft für ein paar Primzahlen einfach mal das Produkt auflösen, Kommutativgesetz anwenden und dann immer 2 zusammenfassen. Wenn man 2 Potenzen

miteinander multipliziert, dann muss man die Exponenten addieren und dann kann man das so zusammenfassen. Und das Ganze ist dann ja schließlich die Primfaktorzerlegung von b und die ist p hoch np. Jetzt wissen wir, Primfaktorzerlegungen sind eindeutig,

d.h. mp plus kp gleich np. Daraus folgt mp plus kp gleich np. Die Primfaktorzerlegung

von b ist eindeutig. Ich habe eine eindeutige Anzahl von 2, eine eindeutige Anzahl von 3, eine eindeutige Anzahl von 5 und so weiter. D.h. np muss dieselbe Anzahl sein wie mp plus kp. Außerdem wissen wir, kp ist größer gleich 0. Alle kp sind größer gleich 0. Ich habe keine

negativen Anzahlen von Primzahlen in meiner Primfaktorzerlegung von c. Wenn ich die Primfaktorzerlegung von q habe, habe ich keine negativen Anzahlen hier oben drin stehen. Das heißt meine kp sind größer gleich 0. Und wenn ich jetzt hier eine Summe habe aus 3

natürlichen Zahlen, inklusive der 0, und das kp ist größer gleich 0, dann muss das mp kleiner gleich dem np sein. Und das ist genau das, was hier oben zu zeigen war.