ggT, kgV und die Produktformel

Primfaktorzerlegung und Exponenten · Abschnitt 31 von 64

Satz

Minimum und Maximum

Schreibe die Exponenten einer Primzahl $p$ in $a$ und $b$ als $r$ und $s$ . Im ggT steht $p^{\min(r,s)}$ , im kgV steht $p^{\max(r,s)}$ .

Gelöstes Beispiel

Beispiel mit 72 und 120

$72=2^3\cdot3^2$ und $120=2^3\cdot3\cdot5$ . Daher ist der ggT $2^3\cdot3=24$ und das kgV $2^3\cdot3^2\cdot5=360$ .

Beweis

Jetzt ist die Produktformel bewiesen

Für jede Primzahl gilt $\min(r,s)+\max(r,s)=r+s$ . Im Produkt aus ggT und kgV tritt sie daher genauso oft auf wie in $ab$ . Die eindeutige Primfaktorzerlegung liefert $\operatorname{ggT}(a,b)\operatorname{kgV}(a,b)=ab$ .

Entscheidungsweg

Welches Verfahren ist sinnvoll?

1
Nur ggT großer Zahlen → meist euklidischer Algorithmus.
2
ggT und kgV bei gut zerlegbaren Zahlen → Primexponenten.
3
Teileranzahl oder genaue Teilerstruktur → Primfaktorzerlegung.
4
Kleine anschauliche Zahlen → Teiler- oder Vielfachenlisten bleiben eine gute Kontrolle.