Euklidischer-Algorithmus: Beweis Ungleichung Nachfolger |
10.11.2013, 14:54 | sleeepyjack | Auf diesen Beitrag antworten » | ||
Euklidischer-Algorithmus: Beweis Ungleichung Nachfolger Hallo zusammen! Gestellt ist folgende Aufgabe: Beim Bestimmen des ggT zweier natürlicher Zahlen mit dem Euklidischen-Algorithmus entstehen die Zahlen . Zeigen Sie: mit Zur Erinnerung nochmal der Euklidische-Algorithmus: euklid(a,b){ IF(b==0)THEN return a; ELSE return euklid(b,a mod b); ENDIF } Danke für die Hilfe im Voraus! Meine Ideen: Mein Ansatz ist, dass ich zuerst versuche zu ersetzen. Hierzu lässt sich aus dem Algorithmus ableiten, dass ist und somit Dies ergibt folgende Ungleichung: Nun lässt sich hieraus folgendes ableiten: Für gilt Leider fehlt mir ab hier das Gehirnschmalz um die Ungleichung zu belegen. Weiß vielleicht jemand wie es weitergehen könnte? |
||||
10.11.2013, 15:38 | Captain Kirk | Auf diesen Beitrag antworten » | ||
Hallo, ich würd hier folgendes machen: Da und für belibige i folgt aus
dass . Ersetze mittels (*) im Term und setze die obere Ungleichung ein. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|