Divisionsalgorithmus/Restefolge direkt/Aufgabe/Lösung

Bei ${}i=0$ fällt dies mit der Definition im Divisionsalgorithmus zusammen. Sei also die Aussage für ein ${}r_{-i}$ schon bewiesen. Nach dem Divisionsalgorithmus ergibt sich das nächste ${}r_{-i-1}$ über die Division mit Rest

${}10r_{-i}=z_{-i}b+r_{-i-1}\,.$

Wir lösen nach ${}r_{-i-1}$ auf und erhalten unter Verwendung der Induktionsvoraussetzung

${}{\begin{aligned}r_{-i-1}&=10r_{-i}-z_{-i}b\\&=10(10^{i}a-xb)-z_{-i}b\\&=10^{i+1}a-10xb-z_{-i}b\\&=10^{i+1}a-b(10x-z_{-i}).\end{aligned}}$

Umstellen ergibt

${}10^{i+1}a=b(10x-z_{-i})+r_{-i-1}\,,$

was bedeutet, dass der Rest bei der Division von ${}10^{i+1}a$ durch ${}b$ gleich ${}r_{-i-1}$ ist, wie behauptet.

Zur gelösten Aufgabe