Question

explain and proof euclids division lemma theorm​

Answer 1

A Euclids division lemma is a proven statement which is used to prove other statements. Consider the division of positive integer by positive integer, say 58 by 9. ... In fact, this holds for every pair of positive integers as proved in the following lemma.

Answer 2

Euclids division lemma : Let ‘a’ and ‘b’ be any two positive integers. Then there exist unique integers ‘q’ and ‘r’ such that

a = 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 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.