Euklidischer Algorithmus

11.12.2015, 16:00	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)
11.12.2015, 16:47	HAL 9000	Auf diesen Beitrag antworten »
(a) ist überkompliziert formuliert, da man via $\begin{align} k_i=n_{i+1} \end{align}$ auf die $\begin{align} k_i \end{align}$ völlig verzichten kann: Es wird $\begin{align} \operatorname{ggT}(n_0,n_1) \end{align}$ bestimmt über die Iteration $\begin{align} n_{i+2} \end{align}$ ist Rest der Division von $\begin{align} n_i \end{align}$ durch $\begin{align} n_{i+1} \end{align}$ , damit ist schon mal $\begin{align} n_{i+2}<n_{i+1} \end{align}$ klar, die Folge $\begin{align} (n_i)_{i=1,2,\ldots} \end{align}$ ist demnach streng monoton fallend. Das ganze wird für $\begin{align} i=0,1,\ldots,r-1 \end{align}$ betrachtet, denn dann ist erstmalig $\begin{align} n_{r+1}=0 \end{align}$ und $\begin{align} n_r\neq 0 \end{align}$ der ggT. Die Behauptung $\begin{align} \max(n_i,k_i) \geq 2\cdot \max(n_{i+2},k_{i+2}) \end{align}$ kann man nun schreiben $\begin{align} \max(n_i,n_{i+1}) \geq 2\cdot \max(n_{i+2},n_{i+3}) \end{align}$ , was wegen $\begin{align} i\geq 1 \end{align}$ und der danach geltenden strengen Monotonie äquivalent zu $\begin{align} n_i \geq 2\cdot n_{i+2} \end{align}$ ist, und diese Ungleichung ist in zwei Zeilen begründbar.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »