---

Geschrieben von Gast am 24.11.2009 um 09:05:

  Euklidischer Algorithmus

Hallo

Ich habe folgende Aufgabe:

Betrachten Sie die rekursive Variante des Euklidischen Algorithmus. Sei
.

a) Beweisen Sie, dass für den Rest r der Division von m durch n gilt:
r< (m/2)

b) Beweisen sie, dass in Rekursionstiefe 1+2k für den aktuellen Rest r und das ursprüngliche m gilt:



c) Zeigen Sie mit dem Wissen aus a und b, dass die maximale Tiefe des rekursiven Euklidischen Algorithmus höchstens 1+2 * log(basis2)(m) beträgt.

a habe ich hinbekommen, bei b würde ich eine induktion über k machen, nur weiß ich nicht wie der induktionsschritt funktionieren soll.
zu c, da weiß ich auch leider überhaupt nicht wie ich das beweisen soll.

LG
estrella28