Wie kann man das beweisen?
ggT(ggT(a,b),c)=ggT(a,ggT(b,c))
4 Antworten
Den ggT mehrerer Zahlen ermittelt man, in dem man die Primfaktorzerlegung der Zahlen betrachtet und die Primfaktoren mit den niedrigsten Exponenten auswählt. Dabe ist es egal, ob man alle Zahlen gleichzeitig betrachtet, oder erst zwei auswählt, die niedrigsten Exponenten auswählt und dann mit den anderen Zahlen fortfährt.
Ein Beispiel zur Erklärung
60 = 2^2 * 3^1 * 5^1
45 = 2^0 * 3^2 * 5^1
10 = 2^1 * 3^0 * 5^1
Man kann sofort sehen
ggT = 2^0 * 3^0 * 5^1 = 5
Man kann aber erst zwei beliebige zusammenfassen
ggT(60,45) = 2^0 * 3^1 * 5^1 = 15
und dann die dritte hinzufügen:
15 = 2^0 * 3^1 * 5^1
10 = 2^1 * 3^0 * 5^1
ggT = 2^0 * 3^0 * 5^1 = 5
Egal wie man vorgeht, man findt so immer die kleinsten Primfaktor-Exponenten aller beteiligten Zahlen.
Versuche zu zeigen, dass jeder Teiler der linken Seite auch ein Teiler der rechten Seite ist und umgekehrt. Nutze dafür die Eigenschaften vom ggT.
Davon folgt, dass beide Seiten gleich sein müssen.
Vielleicht durch (strukturelle) Induktion.
Ist das nicht einfach logisch dass - wenn es überhaupt einen ggT aller drei gibt - der ggT eines ggT einer Teilmenge mit einer dritten Zahl das selbe ist, egal wie ich sortiere?...