Week 3

I am a little bit behind, but here is the proof of the uniqueness of quotient and remainder Prof. Heap mentioned in last Friday's (Sept 19's) class.

P(m): \forall n \in N\{0}, if \exists q and r \in N such that m = q*n + r and 0 <= r < n, then q and r are unique.
Claim: \forall m \in N, P(m).
Proof (by contradiction): assume m \in N. First we know that by the Principle of Well-Ordering, the set R = {r \in N \exists q \in N, m = q*n + r} has a least element, call it r_1 and the q corresponding to this r_1 is q_1. Then m = q_1*n + r_1. If q_1 and r_1 are unique, then there exist a pair q_2 and r_2 such that m = q_2*n + r_2 and 0 <= r_2 < m =" q_1*n" r_1 =" q_2*n"> r_1. Rearrange the above equation, we get (q_1 - q_2)*n = r_2 - r_1 > 0. So q_1 > q_2. Say q_1 = q_2 + k where k is some natural number greater than 0. Then m = q_1*n + r_1 = (q_2 + k) *n + r_1 = q_2*n + (r_1 + k*n) = q_2*n + r_2. So r_2 = r_1 + k*n > n, contradicts to that 0 <= r_2 < n. So q_1 and r_1 are unique.
So \forall m \in N, P(m).