Question

Proof of Euclid's division lemma and also Euclid's division algorithm

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.

Examples Euclids division lemma
1) Show that n² - 1 is divisible by 8, if n is an odd positive integer.
Solution :
We know that any odd positive integer is of the form 4q + 1 or 4q + 3 for some integer q.
So, we have the following cases :
Case I When n = 4q + 1
In this case, we have
n² - 1 = (4q + 1)² - 1 = 16q² + 8q + 1 – 1
= 16q² + 8q
= 8q ( 2q + 1)
⇒ n² - 1 is divisible by 8 [ since 8q ( 2q + 1) is divisible by 8]
Case II When n = 4q + 3
In this case, we have
n²-1 = (4q + 3)² - 1
= 16q² + 24q + 9 – 1
= 16q² + 24q + 8
⇒ n² - 1 = 8(2q² + 3 q + 1)
⇒ n² - 1 is divisible by 8 [ since 8(2q² + 3 q + 1) is divisible by 8]
Hence, n² - 1 is divisible by 8.
--------------------------------------------------------------------
2) Show that every positive even integer is of the form 2q, and that every positive odd integer is of the form 2q + 1, where q is some integer.
Solution :
Let ‘a’ be any positive integer and b = 2. Then, by Euclid’s division Lemma there exists integers q and r such that
a = 2q + r , where 0 ≤ r < 2
Now, 0 ≤ r < 2 ⇒ 0 ≤ r ≤ 1 ⇒ r = 0 or r = 1 [ since r is and integer]
∴ a = 2q or a = 2q + 1
If a = 2q, then ‘a’ is an even integer.
We know that an integer can be either even or odd. Therefore, any odd integer is of the form of 2q + 1.