ggT, Beweis

Neue Frage »

Wombat91 Auf diesen Beitrag antworten »
ggT, Beweis
Ich müsste beweisen, dass der ggT(a,b)=ggT(a-b,b) für zwei beliebige gilt. Hättet mir da vielleicht einen Tipp, wie ich das angehen soll?
Vielen Dank!
system-agent Auf diesen Beitrag antworten »

Du könntest einmal aufschreiben wie ihr den ggT definiert habt oder welche Charakterisierungen du davon kennst.
Shortstop Auf diesen Beitrag antworten »

Also, ich würds mal so angehen:

Sei x der ggT(a,b). Dann teilt x also sowohl a als auch b.



Insbesondere folgt also, dass



Nun bleibt zu zeigen, dass x auch der größte gemeinsame Teiler von (a-b) und b ist.

Das könntest du per Widerspruch machen Augenzwinkern
Wombat91 Auf diesen Beitrag antworten »

Ach so...
Wenn also x a und b teilt, dann wäre ja:, d.h. und das würde bedeuten, dass x auch ein Teiler von a-b ist. Jetzt sollte ich noch zeigen, dass dieses x auch wirklich der ggT ist. Sei also ein y>x vorhanden, dann könnte man y als ein Vielfaches von x ausdrücken.

sowie:
Es muss aber auch gelten, dass .
Ist das soweit richtig? Wie mache ich jetzt weiter? Entschuldigung, wegen meinem Unwissen, habe noch nie einen Widerspruchsbeweis geführt!
Vielen Dank!
Shortstop Auf diesen Beitrag antworten »

Zitat:
Original von Wombat91
Ach so...
Wenn also x a und b teilt, dann wäre ja:, d.h. und das würde bedeuten, dass x auch ein Teiler von a-b ist.


Richtig.

Zitat:
Original von Wombat91
Sei also ein y>x vorhanden, dann könnte man y als ein Vielfaches von x ausdrücken.


Das stimmt so nicht.

Beispiel: 3 und 4 sind Teiler von 12, 4 ist größer als 3 aber es existiert keine natürliche Zahl n mit 3*n=4.

Aber: Angenommen, es gäbe so ein y, welches a-b teilt. Zieh den Bruch mal auseinander und schau, was du über die beiden Teile sagen kannst. Denk dran, y müsste ja dann auch b teilen.
René Gruber Auf diesen Beitrag antworten »

Eine leichte Variation des Beweises, diesmal direkt:

Wenn man nachweist, dass jeder gemeinsame Teiler von und auch ein gemeinsamer Teiler von und ist, und umgekehrt (!), dann ist man bereits fertig:

Denn dann ist die Menge der gemeinsamen Teiler von und gleich der Menge der gemeinsamen Teiler von und , insbesondere sind dann auch die Mengenmaxima gleich.
 
 
Wombat91 Auf diesen Beitrag antworten »

@kvnb: Stimmt! Hab mir das falsch überlegt!
Das kann aber nicht sein, weil es kein b gibt, das y teilt? Stimmt das so?

Danke schon mal!
Shortstop Auf diesen Beitrag antworten »

Doch. Laut Annahme ist y>x und y Teiler von (a-b) und b.

Also folgt:



Was kannst du dann über sagen?

Und das steht im Widerspruch zu ?
Wombat91 Auf diesen Beitrag antworten »

Ah, ja Hammer Das wird ja vorausgesetzt. Es geht also wegen dem a nicht!
Danke vielmals für eure Hilfe!!!
ggT Guy Auf diesen Beitrag antworten »

Ich komme beim allerletzten Schritt nicht weiter.

Was kann man über sagen? Wozu steht das im Widerspruch?
Neue Frage »
Antworten »



Verwandte Themen

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