Euclidean division algorithm
While studying number theory, we will be primarily interested in the properties of the integers and natural numbers. This means that if we want to write something like " ", we'll have to be very careful to check that divides . This makes everything very complicated, so instead, we'll avoid dividing natural numbers.
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.
Note that even though this is a proof, it also contains an algorithm for finding the quotient and remainder. If , follow the instructions in the base case; if , then first find the quotient q' and remainder r' for and , then follow the instructions in the inductive step. Of course, while we are finding and , we may need to also find the quotient and remainder of and , and so on.
This is a general pattern: most proofs that something exists give you instructions for finding it. In fact, there are whole programming languages where instead of writing a program, you write a proof; after the computer checks your proof, it extracts a program for you (which is guaranteed to be correct!).