Question

State and prove Euclid's Division Lemma.

Answer 1

Euclids division lemma :

Let ‘a’ and ‘b’ be any two positive integers. Then there exist unique integers ‘q’ and ‘r’ such thata = bq + r, 0 ≤ r ≤ b.If b | a, then r=0. Otherwise, ‘r’ satisfies the stronger inequality 0 ≤ r ≤ b.

Proof

: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 ofthis arithmetic progression. Then, there exists a non-negative integer ‘q’ such that,a – bq = r ⇒ a = bq + rAs, r is the smallest non-negative integer satisfying the above result. Therefore, 0 ≤ r≤ bThus, we havea = bq1 + r1 , 0 ≤ r1 ≤ bWe shall now prove that r1 = r and q1 = qWe 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 = rNow, r1 = r⇒ -r1 = r⇒ a – r1 = a – r⇒ bq1 = bq⇒ q1 = q Hence, the representation a = bq+ r, 0≤ r ≤ b is unique.

Answer 2

Answer:

, bxt yr aj aj tzbjzthxt u as