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.