Euclid's Division Lemma

MATHS Real Numbers Euclid's Division Lemma Euclid’s Division Alogrithm : Algorithm: An algorithm is a series of well defined steps which provide a procedure of calculation repeated successively on the results of earlier steps till the desired result is obtained. Euclid’s division algorithm is an algorithm to compute the highest common factor (HCF) of two given positive integers. For any two positive integers a and b, there exist unique integers q and r satisfying a = bq + r, where 0  r < b. For Example (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, 1 MATHS 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 number b in which q is the quotient obtained and r is the remainder. Thus, dividend = divisor × quotient + remainder  a = bq +r H.C.F. (Highest Common Factor) The H.C.F. of two or more positive integers is the largest positive integer that divides each given positive number completely. i.e., if positive integer d divides two positive integers a and b then the H.C.F. of a and b is d. For Example (i) 14 is the largest positive integer that divides 28 and 70 completely; therefore H.C.F. of28 and 70 is 14. (ii) H.C.F. of 75, 125 and 200 is 25 as 25 divides each of 75, 125 and 200 completely and so on. Using Euclid’s Division Lemma For Finding H.C.F. Consider positive integers 418 and 33. Step-1 Taking bigger number (418) as a and smaller number (33) as b express the numbers as a = bq + r  418 = 33 × 12 + 22 Step-2 Now taking the divisor 33 and remainder 22; apply the Euclid’s division algorithm to get: 33 = 22 × 1 + 11 [Expressing as a = bq + r] 2 MATHS Step-3 Again with new divisor 22 and new remainder 11; apply the Euclid’s division algorithm to get: 22 = 11 × 2 + 0 Step-4 Since, the remainder = 0 so we cannot proceed further. Step-5 The last divisor is 11 and we say H.C.F. of 418 and 33 = 11 Ex.1 Show that any positive odd integer is of the form 6q + 1 or, 6q + 3 or, 6q + 5, where q is some integer. Sol. Let ‘a’ be any positive integer and b = 6. Then, by Euclid’s division lemma there exists integers ’a’ and ‘r’ such that a = 6q + r, where 0  r < 6.  a = 6q or, a = 6q + 1 or, a = 6q + 2 or, a = 6a + 3 or, a = 6q + 4 or, a = 6q + 5. [ 0  r < 6 Þ r = 0, 1,2,3,4,5]  a = 6q + 1 or, a = 6q + 3 or, a = 6q + 5. [ a is an odd integer,   6q, a  6q + 2, a  6q + 4] Hence, any odd integer is of the form 6q + 1 or, 6q + 3 or, 6q + 5. Ex.2 Use Euclid’s Division Lemma to show that the cube of any positive integer is of the form 9m, 9m + 1 or 9 m + 8, for some integer q. Sol, Let x be any positive integer. Then, it is of the form 3q or, 3q + 1 or, 3 + 2. 3 MATHS Case - I When x = 3q  x3 = (3q)3 = 27q3 = 9(3q3) = 9m, where m = 9q3 Case - II when x = 3q + 1  x3 = (3q + 1)3  x3 = 2q3 + 27q2 + 9q + 1  x3 = 9q (3q2 + 3q + 1) + 1  x3 = 9m + 1, where m = q (3q2 + 3q + 1). Case -III when x = 3q + 2  x3 = (3q + 2)3  x3 = 27q3 + 54q2 + 36q + 8  x3 = 9q(3q2 + 6q + 4) + 8  x3 = 9m + 8, where m = 3q2 + 6q + 4) Hence, x3 is either of the form 9m of 9m + 1 or 9m + 8. Ex.3 Prove that the square of any positive integer of the form 5q + 1 is of the same form. Sol. Let x be any positive’s integer of the form 5q + 1. When x= 5q + 1 x2 = 25q2 + 10q + 1 4 MATHS x2 = 5(5q + 2) + 1 Let m = q (5q + 2). x2 = 5m + 1. Hence, x2 is of the same form i.e. 5m + 1. Ex.4 Use Euclid’s division algorithm to find the H.C.F. of 196 and 38318. Sol. Applying Euclid’s division lemma to 196 and 38318. 38318 = 195 × 196 + 98 196 = 98 × 2 + 0 The remainder at the second stage is zero. So, the H.C.F. of 38318 and 196 is 98. Ex.5 If the H.C.F. of 657 and 963 is expressible in the form 657x + 963 × (-15), find x. Sol. Applying Euclid’s division lemma on 657 and 963. 963 = 657 × 1 + 306 657 = 306 × 2 + 45 306 = 45 × 6 + 36 45 = 36 × 1 + 9 36 = 9 × 4 + 0 So, the H.C.F. of 657 and 963 is 9. Given : 657x + 963 × (-15) = H.C.F. of 657 and 963. 5 MATHS 657 x + 963 × (-15) = 9 657 x = 9 + 963 × 15 657 x = 14454 x= 14454=22. 657 6 MATHS 7