Divisionsalgorithmus/Restefolge direkt/Aufgabe/Lösung

Aus Wikiversity


Bei fällt dies mit der Definition im Divisionsalgorithmus zusammen. Es sei also die Aussage für ein schon bewiesen. Nach dem Divisionsalgorithmus ergibt sich das nächste über die Division mit Rest

Wir lösen nach auf und erhalten unter Verwendung der Induktionsvoraussetzung

Umstellen ergibt

was bedeutet, dass der Rest bei der Division von durch gleich ist, wie behauptet.