Bei
fällt dies mit der Definition im Divisionsalgorithmus zusammen. 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.