Euclid Division Lemma - Real Numbers, Class 10 Mathematics PDF Download

EUCLID'S DIVISION LEMMA OR EUCLID'S DIVISION ALGORITHM

For any two positive integers a and b there exist unique integers q and r such that
a = bq + r, where 0 ≤ r < b.

Let us consider a = 217, b = 5 and make the division of 217 by 5 as under :

e.g. (i)

Consider number 23 and 5, then :

23 = 5 × 4 + 3

Comparing with a = bq + r

we get, a = 23, b = 5, q = 4, r = 3 and 0 ≤ r < b (as 0 < 3 < 5)

(ii) 

Consider positive integers 18 and 4

18 = 4 × 4 + 2

For 18 (= a) and 4 (= b) we have q = 4, r = 2 and 0 ≤ r < b

In the relation a = bq + r, where 0 ≤ r < b is nothing but a statement of the long division of number a by b in which q is the quotient obtained and r is the remainder.

Ex. 1 Use Euclid's division lemma to show that the square of any positive integer is either of the form 3m or 3m +1 for some interger m.

Sol. 

Let a and b are two positive integers such that a is greater than b, then :

a = bq + r; where q and r are also positive integers and 0 ≤ r < b

Taking b = 3, we get:

a = 3q7 + r; where 0 ≤ r < 3

⇒ The value of positive integer a will be

3q + 0, 3q + 1 or 3q + 2

i.e., 3q, 3q + 1 or 3q + 2.

Now we have to show that the square of positive integers 3q, 3q + 1 and 3q + 2 can be expressed as  3m or 3m + 1 for some integer m.

∴ Square of 3q = (3q)²

= 9q² = 3(3q²) = 3m; where m is some integer and m = 3q²

Square of 3q + 1 = (3q + 1)²

= 9q² + 6q + 1

= 3(3q² + 2q) + 1 = 3m + 1 for some integer and m = 3q² + 2q.

Square of 3q + 2 = (3q + 2)²

= 9q² + 12q + 4

= 9q² + 12q + 3 + 1

= 3(3q² + 4q + 1) + 1 = 3m + 1 for some integer and m = 3q² + 4q + 1.

∴ The square of any positive integer is either of the form 3m or 3m + 1 for some integer m.

Ex. 2 Show that one and only one out of n; n + 2 or n + 4 is divisible by 3, where n is any positive integer.

Sol. 

Consider any two positive integers a and b such that a is greater than b, then according to Euclid's division algorithm

a = bq + r; where q and r positive integers and 0 ≤ r < b

Let a = n and b = 3, then

a = bq + r ⇒ n = 3q + r; where 0 ≤ r < 3.

r = 0 ⇒ n = 3q + 0 = 3q

r = 1 ⇒ n = 3q + 1

and r = 2 ⇒ n = 3q + 2

If n = 3q; n is divisible by 3

If n = 3q + 1; then n + 2 = 3q + 1 + 2

= 3q + 3; which is divisible by 3

⇒ n + 2 is divisible by 3

If n = 3q + 2; then n + 4 = 3q + 2 + 4

= 3q + 6; which is divisible by 3

⇒ n + 4 is divisible by 3

Hence, if n is any positive integer, then one and only one out of n, n + 2 or n + 4 is divisible by 3.

APPLICATION OF EUCLID'S DIVISION LEMMA FOR FINDING H.C.F OF POSITIVE INTEGERS

Algorithm :

Consider positive integers 418 and 33

Step.(a) Taking bigger number (418) as a and smaller number (33) as b.

Express the numbers as a = bq + r

418 = 33 × 12 + 22

Step.(b) Now taking the divisor 33 and remainder 22, apply the Euclid's division method to get.

33 = 22 × 1 + 11 [Expressing as a = bq + r]

Step.(c) Again with new divisior 22 and new remainder 11, apply the Euclid's division algorithm to get

22 = 11 × 2 + 0

Step.(d) Since, the remainder = 0 so we can not proceed further.

Step.(e) The last divisor is 11 and we say H.C.F. of 418 and 33 = 11

Ex.3 Use Euclid's algorithm to find the HCF of 4052 and 12576.

Sol.

Using a = bq + r, where 0 ≤ r < b.

Clearly, 12576 > 4052 [a = 12576 , b = 4052]

⇒ 12576 = 4052 × 3 + 420

⇒ 4052 = 420 × 9 + 272

⇒ 420 = 272 × 1 + 148

⇒ 272 = 148 × 1 + 124

⇒ 148 = 124 × 1 + 24

⇒ 124 = 24 × 5 + 4

⇒ 24 = 4 × 6 + 0

The remainder at this stage is 0. So, the divisor at this stage, i.e., 4 is the HCF of 12576 and 4052.

Ex.4 Use Euclid's algorithm to find the HCF of 1848 and 3058.

Sol. Two numbers 1848 and 3058, where 3058 > 1848

3058 = 1848 × 1 + 1210

1848 = 1210 × 1 + 638 [Using Euclid's division algorithm to the given number 1848 and 3058]

1210 = 638 × 1 + 572

638 = 572 × 1 + 66

572 = 66 × 8 + 44

66 = 44 × 1 + 22

44 = 22 × 2 + 0

Therefore HCF of 1848 and 3058 is 22.

HCF (1848 and 3058) = 22

Ex.5 Use Euclid's algorithm to find the HCF of 1331 and 22.

Let us find the HCF of the numbers 1331 and 22.

1331 = 22 × 60 + 11

22 = 11 × 2 + 10

∴ HCF of 1331 and 22 is 11

⇒ HCF (22, 1331) = 11

Hence the HCF of the three given numbers 1848, 3058 and 1331 is 11.

HCF (1848, 3058, 1331) = 11

Ex.6 Using Euclid's division, find the HCF of 56, 96 and 404 [Sample paper (CBSE)-2008]

Sol. Using Euclid's division algorithm, to 56 and 96.

96 = 56 × 1 + 40

56 = 40 × 1 + 16

40 = 16 × 2 + 8

16 = 8 × 2 + 0

Now to find HCF of 8 and 404

We apply Euclid's division algorithm to 404 and 8

404 = 8 × 50 + 4

8 = 4 × 2 + 0Hence 4 is the HCF of the given numbers 56, 96 and 404.