The goal of this exercise is to prove the following theorem inseveral steps.
Theorem: Let ? and ? be natural numbers. Then, there existunique
integers ? and ? such that ? = ?? + ? and 0 ? ? < ?.
Recall: that ? is called the quotient and ? the remainder of thedivision
of ? by ?.
(a) Let ?, ? ? Z with 0 ? ? < ?. Prove that ? divides ? if andonly if ? = 0.
(b) Use part (a) to prove the uniqueness part of the theorem. Thatis, show thatiftherearetwopairs? ,? ?Zand? ,? ?Zsatisfying?=? ?+
11221
?,0?? (c) Prove that there exist such ? and ? when ? divides ?.
(d) Prove that there exist such ? and ? when ? does not divide ? byapplying the Well-Ordering Principle to the set
? = {? ? N: ? = ? ? ?? ??? ???? ? ? Z}.
