Beweis: ggT(a, b, c) = ggT (ggT (a,b) , c) ?

Neue Frage »

Fanatiker Auf diesen Beitrag antworten »
Beweis: ggT(a, b, c) = ggT (ggT (a,b) , c) ?
Mit dem euklidischen Algorhythmus ist es bekanntlich einfach den größten gemeinsamen Teiler von drei Zahlen zu bestimmen. So kann man den größten gemeinsamen Teiler von den Zahlen 4, 12 und 36 beispielsweise dadurch bestimmen, in dem man erst den ggT von 4 und 12 berechnet und anschließend davon den ggT mit c bestimmt. Wie kann ich es aber als formel nun beweisen, dass:

ggT (a, b, c) = ggT (ggT (a,b) , c) ist ?

Es sagt ja nicht mehr als das aus, was ich grade schon beschrieben habe. Wie beweis ich dies nun jetzt ?
Elvis Auf diesen Beitrag antworten »

Beweis über die Primzerlegung sollte einfach sein.
Fanatiker Auf diesen Beitrag antworten »

Wie bekomme ich das denn über die PFZ heraus ?

An einem Beispiel kann ich das zeigen, aber nicht allgemein beweisen für diesen Beweis.
Ich weiss, dass beispielsweise die zahl 36 mit der PFZ zerlegt ergibt:

36 = 2 * 18 = 2 * 2 * 9 = 2 * 2 * 3 * 3, somit ist 36 = 2² * 3², wie will ich aber hier die PFZ anwenden ?
Elvis Auf diesen Beitrag antworten »

Fanatiker Auf diesen Beitrag antworten »

Sagt das jetzt nicht nur aus, dass der ggT von zwei Zahlen aus dem Minimum der PFZ gebildet wird ?

Also beispielsweise wäre der ggT von:
x =
code:
1:
2^{5} \cdot 4^{1} 

y =
code:
1:
2^{3} \cdot 4^{5} 

Somit wäre dann der ggT von den beiden Zahlen x und y gleich dem Minimum der beiden Zahlen, somit also:

ggT (x, y) =
code:
1:
2^{3} \cdot 4^{1} 


Aber wie bekomme ich den Beweis für die Aufgabe hin, denn letzteres versteh ich nur so ?

P.S. Sorry komme noch nicht so ganz mit Formeleditor und co klar...
HAL 9000 Auf diesen Beitrag antworten »

Durch die Primfaktordarstellung von Elvis wird deine Behauptung (auf Primfaktor-Exponentenebene) zurückgeführt auf das noch elementarere

,

was du nun natürlich noch zeigen kannst.
 
 
Elvis Auf diesen Beitrag antworten »

@Fanatiker

Dein Beispiel ist "nur zufällig" richtig. .

Bei der Primfaktorzerlegung geht es um (endliche) Produkte über Primzahlen, zum Beispiel
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »