1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

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

Open in App
Solution

## 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 n2 - 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 n2 - 1 = (4q + 1)2 - 1 = 16q2 + 8q + 1 – 1 = 16q2 + 8q = 8q ( 2q + 1) ⇒ n2 - 1 is divisible by 8 [ since 8q ( 2q + 1) is divisible by 8] Case II When n = 4q + 3 In this case, we have n2-1 = (4q + 3)2 - 1 = 16q2 + 24q + 9 – 1 = 16q2 + 24q + 8 ⇒ n2 - 1 = 8(2q2 + 3 q + 1) ⇒ n2 - 1 is divisible by 8 [ since 8(2q2 + 3 q + 1) is divisible by 8] Hence, n2 - 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.

Suggest Corrections
7
Join BYJU'S Learning Program
Related Videos
Playing with 2 - Digit and 3 - Digit Numbers
MATHEMATICS
Watch in App
Explore more
Join BYJU'S Learning Program