The division algorithm states that for a fixed positive integer and for every integer , there exist nonnegative integers and such that
Prove this by induction.
Proof. Let be a fixed positive integer. If then letting , the statement is true (since ).
Now assume the statement is true for some . By the induction hypothesis we know there exist nonnegative integers and such that
Thus, adding 1 to both sides we have,
Since we know . If , then , and the statement still holds with the same choice of and in place of .
On the other hand, if , then and we have,
Hence, the statement holds again, but with in place of and with (which is valid since if then we have ). Therefore, if the division algorithm holds for , then it also holds for . Hence, it holds for all