Euklidischer Algorithmus

Neue Frage »

margareth_maggy Auf diesen Beitrag antworten »
Euklidischer Algorithmus
Meine Frage:
Hallo!

Ich bin heute den ganzen Tag mit aufgabe 2 beschäfttigt.

Kann mir jemand helfen?


Vielen Dank im Voraus!

Meine Ideen:
Euklidische Algorithmus benutzt man zur Bestimmung von ggT(n0,k0), was nach r Schritten beendet. Weiter seien ni,ki aus N für i aus (1,......r) definiert durch ni+1=ki und ki+1 ist der Rest von ni bei Division durch ki.
Die Zahlen ni,ki sind also die Zwischenergebnisse des euklidischen Algorithmus. Zeige, dass für i aus (1,.......r-2) gilt:

max(ni,ki)>= 2max(ni+2,ki+2)
HAL 9000 Auf diesen Beitrag antworten »

(a) ist überkompliziert formuliert, da man via auf die völlig verzichten kann: Es wird bestimmt über die Iteration

ist Rest der Division von durch ,

damit ist schon mal klar, die Folge ist demnach streng monoton fallend. Das ganze wird für betrachtet, denn dann ist erstmalig und der ggT.


Die Behauptung kann man nun schreiben , was wegen und der danach geltenden strengen Monotonie äquivalent zu ist, und diese Ungleichung ist in zwei Zeilen begründbar.
 
 
Neue Frage »
Antworten »



Verwandte Themen

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