GgT finden mit dem Algorithmus des Euklid

Neue Frage »

schildval Auf diesen Beitrag antworten »
GgT finden mit dem Algorithmus des Euklid
Meine Frage:
Hallo, einige können es bestimmt nicht mehr sehen, aber hier ist noch eine Frage zum Algorithmus des Euklid (falls jemand die Lösung weiß oder weiß, wo sie steht, wird Löschung beantragt).

Es heißt ja für ggT(a,b): oder allgemein .

Woher weiß ich, dass der Teiler von a&b auch der gleiche Teiler von r1&b ist? Teilen mit Rest ist kein einfaches Multiplizieren oder Dividieren. Mit der allgemeinen Gleichung finde ich nur, dass es einen Teiler auf beiden Seiten gibt. Aber das könnte ja immer ein anderer sein, oder immer zwei verschiedene abwechselnd.

Meine Ideen:
Ist der gemeinsame Teiler in der Division mit Rest definiert? Wenn ja, dann kenne ich diese Definition nicht und wäre dankbar für Hinweise.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von schildval
Woher weiß ich, dass der Teiler von a&b auch der gleiche Teiler von r1&b ist?

Erstaunt1

"Der Teiler" ??? Womöglich meinst du: Warum gilt ?

An sich eine Grundeigenschaft des ggT, dieses für alle ganzen Zahlen , aber richtig, irgendwann mal sollte man diesen elementaren Beweis mal führen...
 
 
schildval Auf diesen Beitrag antworten »
RE: GgT finden mit dem Algorithmus des Euklid
Na ja "Teiler", weil ich davor noch gar nicht weiß, ob der ggT(r1,b) auch der gesuchte Wert ist, und das ganze kommt mir eh etwas rekursiv vor, auch wenn es das nicht ist. Aber o.k. das macht wieder einmal sehr schön sehr simpel sehr viel Sinn in dieser Hinsicht!

Gott *Thema-Wegräum-Zauber*
HAL 9000 Auf diesen Beitrag antworten »

Gut, hier der Beweis von :

1) Jeder gemeinsame Teiler von und ist auch ein Teiler von , damit ist er auch ein gemeinsamer Teiler von und .

2) Jeder gemeinsame Teiler von und ist auch ein Teiler von , damit ist er auch ein gemeinsamer Teiler von und .

Zwei Paare mit derselben Menge gemeinsamer Teiler besitzen definitionsgemäß dann auch denselben größten gemeinsamen Teiler.
Neue Frage »
Antworten »



Verwandte Themen

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