Question

how can we prove Euclid's division lemma?

Answer 1

Consider the following arithmetic progression …, a – 3b, a – 2b, a – b, a, a + b, a + 2b, a + 3b, … Clearly, it is an arithmetic progression with common difference ‘b’ and it extends infinitely in both the directions. Let ‘r’ be the smallest non-negative term of this arithmetic progression. Then, there exists a non-negative integer ‘q’ such that, a – bq = r ⇒ a = bq + r As, r is the smallest non-negative integer satisfying the above result. Therefore, 0 ≤ r ≤ b Thus, we have a = bq1 + r1 , 0 ≤ r1 ≤ b We shall now prove that r1 = r and q1 = q We have, a = bq + r and a = bq1 + r1 ⇒ bq + r = bq1 + r1 ⇒ r1 – r = bq1 – bq ⇒ r1 – r = b(q1 – q) ⇒ b | r1 – r ⇒ r1 – r = 0 [ since 0 ≤ r ≤ b and 0 ≤ r1 ≤ b ⇒ 0 ≤ r1 - r ≤ b ] ⇒ r1 = r Now, r1 = r ⇒ -r1 = r ⇒ a – r1 = a – r ⇒ bq1 = bq ⇒ q1 = q Hence, the representation a = bq + r, 0≤ r ≤ b is unique.