Größter gemeinsamer Teiler

Der größte gemeinsame Teiler (ggT) ist die größte natürliche Zahl, durch die sich zwei oder mehr Zahlen ohne Rest teilen lassen. Er ist ein wichtiges Werkzeug in der Arithmetik, um beispielsweise Brüche vollständig zu kürzen oder Aufteilungsaufgaben zu lösen. Die Schreibweise für den größten gemeinsamen Teiler von zwei natürlichen Zahlen a und b lautet: text{ggT}(a, b) Da die Reihenfolge der Zahlen keine Rolle spielt, gilt: text{ggT}(a, b) = text{ggT}(b, a) Um den ggT systematisch zu bestimmen, nutzt man die Primfaktorzerlegung : Bestimme den text{ggT}(12, 9) . Weg 1: Teiler auflisten Teilermenge von 12: T {12} = {1, 2, mathbf{3}, 4, 6, 12 } Teilermenge von 9: T {9} = {1, mathbf{3}, 9 } Die gemeinsamen Teiler sind 1 und 3 . Der größte davon ist 3 . text{ggT}(12, 9) = 3 Die Verteilung der Teiler lässt sich im Venn-Diagramm darstellen (die Schnittmenge enthält die beiden gemeinsamen Teiler 1 und 3 ): Anwendung: Brüche kürzen Mit dem ggT kürzen wir den Bruch frac{9}{12} in einem einzigen Schritt vollständig: frac{9}{12} = frac{9 div 3}{12 div 3} = frac{3}{4} Bestimme den ggT von größeren Zahlen: text{ggT}(220, 132) . Schritt 1: Primfaktorzerlegung Wir zerlegen beide Zahlen in ein Produkt aus Primzahlen: 220 = 2 cdot 2 cdot 5 cdot 11 132 = 2 cdot 2 cdot 3 cdot 11 Schritt 2: Gemeinsame Faktoren wählen Die Primfaktoren, die in beiden Produkten vorkommen, sind: zweimal die 2 und einmal die 11 . Schritt 3: Produkt bilden text{ggT}(220, 132) = 2 cdot 2 cdot 11 = 44 Die Zahl 44 ist som