Question

state the Euclid 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 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.
Cheers buddy

Answer 2

Euclid’s Division Lemma states that for any given positive integers a and b, there exists unique integers q and r such that a = bq + r, where 0 ≤ r < b