Proof of Euclid's Division Lemma: Uniqueness and Existence of Quotient and Remainder
Euclid's Division Lemma is a fundamental principle in number theory, stating that for any integers a and b where b > 0, there exist unique integers q (quotient) and r (remainder) such that:
a bq r where 0 ≤ r .
Proof of Existence
To prove the existence of such integers q and r, we proceed as follows:
Consider the set S {a - bk | k ∈ mathbb{Z}, a - bk ≥ 0}. This set consists of all non-negative integers that can be obtained by subtracting multiples of b from a.
Since a is a fixed integer and b is positive, the set S is non-empty. At the very least, if a ≥ 0, then a itself is in S.
The set S is bounded below by 0, hence it has a minimum element, say r. This implies:
r a - bq for some integer q.
By construction, we have r ≥ 0.
Bound on r:
We need to show that r .
- Assume for contradiction that r ≥ b. Then:
r a - bq ≥ b.
- This implies:
a - bq ≥ b which means:
a ≥ bq 1.
- Set q' q 1. Then:
a bq' r' ≤ bq r a since r' a - b(q 1) and r' .
- This leads to a contradiction, as r' a - b(q 1) would mean we could take q' as a new quotient and r' a - bq' as the new remainder, which would contradict the minimality of r, which contradicts r ≤ r'. Thus, our assumption that r ≥ b must be false, leading to:
r .
Proof of Uniqueness
Now we show that q and r are unique. Suppose there exist two pairs (q_1, r_1) and (q_2, r_2) such that:
a bq_1 r_1 bq_2 r_2 where 0 ≤ r_1 and 0 ≤ r_2 .
Setting the two expressions for a equal gives:
bq_1 r_1 bq_2 r_2 which implies:
bq_1 - q_2 r_2 - r_1.
Rearranging gives:
r_2 r_1 b(q_1 - q_2).
Since 0 ≤ r_1 and 0 ≤ r_2 , the right-hand side must also satisfy 0 ≤ r_2 . This can only happen if |q_1 - q_2| 0, otherwise, b(q_1 - q_2) would push r_2 outside the bounds of 0 and b. Therefore, q_1 q_2 and consequently, r_1 r_2.
Conclusion
We have shown that for any integers a and b with b > 0, there exist unique integers q and r such that:
a bq r where 0 ≤ r .
This completes the proof of Euclid's Division Lemma.