Proof:Euclidean division algorithm
From CS2800 wiki
We prove this by weak induction on . Let be the statement "for all , there exists satisfying (1) and (2) above." We will show and assuming .
In the latter case, we can let and . Then . Again it is clear that .In either case, we have shown that there exist and satisfying (1) and (2), as required.