Größter gemeinsamer Teiler (ggT): Definition, Methoden und Zusammenhang mit kgV

ggT (Größter gemeinsamer Teiler), auch Greatest Common Divisor (GCD) genannt, ist die größte positive Ganzzahl, die zwei oder mehr Zahlen ohne Rest teilt.

Beispiel: ggT von 12 und 18

• Teiler von 12: 1, 2, 3, 4, 6, 12
• Teiler von 18: 1, 2, 3, 6, 9, 18
• ggT = 6

Berechnungsmethoden

1. Euklidischer Algorithmus (am effizientesten)

 18 ÷ 12 = 1 Rest 6 12 ÷ 6 = 2 Rest 0 → ggT = 6 

2. Primfaktorzerlegung

• 12 = 2² × 3
• 18 = 2 × 3²
• ggT = Produkt der niedrigsten Potenzen gemeinsamer Primzahlen = 2¹ × 3¹ = 6

Zusammenhang mit kgV

Für zwei beliebige positive Ganzzahlen gilt: ggT × kgV = Produkt der Zahlen

Beispiel: ggT(12,18) = 6 → kgV = (12 × 18) / 6 = 36

Hinweis: Der Quelltext berechnete das kgV fälschlich mit 1296; der korrekte Wert ist 36.