Question

Q1. (Euclidean Algorithm) Let n be any natural number and m be a positive number. Then show that there exists natural numbers q and r such that 0 ≤ r < m and n = qm + r

Answer 1

Answer:

Proof.

We fix q and use induction on n. We first prove the base case n=0. If we set m=0 and r=0 then we have n=0⋅q+0=0 but 0≤0<q, so we are done with the base case.

Now suppose inductively that n=m⋅q+r for some natural numbers m, r such that 0≤r<q and n=mq+r. We wish to show that there exist natural numbers m′ and r′ such that n+1=m′⋅q+r′ where 0≤r′<q.

From the inductive hypothesis we have n+1=mq+(r+1).

Since r<q, r+1≤q that is r+1=q or r+1<q.

If r+1=q, we set m′=m+1 and r′=0 then m′⋅q+r′=(m+1)⋅q+0 but n+1=(m+1)⋅q+0, so n+1=m′⋅q+r′ and 0≤r′<q.

If however r+1<q then we set m′=m and r′=r+1 then we have that n+1=m′⋅q+r′ and 0≤r′<q.