\n
Step 2: Remainder r which is 90 \u2260\u00a00,
\nwe apply Euclid’s division lemma to b =135 and r = 90 to find whole numbers q and r
\nsuch that 135 = 90 x q + r, \u00a00 \u2264\u00a0r<90
\nOn dividing 135 by 90 we get quotient as 1 and remainder as 45
\ni.e 135 = 90 x 1 + 45<\/p>\n
Step 3:Again remainder r = 45 \u2260\u00a00
\nso we apply Euclid’s division lemma to b =90 and r = 45 to find q and r
\nsuch that 90 = 90 x q + r, \u00a0 \u00a00 \u2264\u00a0r<45
\nOn dividing 90 by 45 we get quotient as 2 and remainder as 0
\ni.e 90 = 2 x 45 + 0<\/p>\n
Step 4:\u00a0Since the remainder is zero, the divisor at this stage will be HCF of (135, 225).
\nSince the divisor at this stage is 45, therefore, the HCF of 135 and 225 is 45.<\/p>\n
(ii)\u00a0\u00a0 \u00a0196 and 38220
\nStep 1:\u00a0\u00a0Since 38220 > 196, apply Euclid’s division lemma
\nto a =38220 and b=196\u00a0 to find\u00a0 whole numbers q and r
\nsuch that 38220 = 196 q + r, 0 \u2264\u00a0r < 196
\nOn dividing 38220 we get quotient as 195 and remainder r as 0
\ni.e 38220 = 196 x 195 + 0
\nSince the remainder is zero, divisor at this stage will be HCF
\nSince divisor at this stage is 196, therefore, HCF of 196 and 38220 is 196.<\/p>\n
NOTE: HCF( a,b) = a if a is a factor of\u00a0 b. Here, 196 is a factor of\u00a0 38220 so HCF is 196.<\/p>\n
(iii)\u00a0\u00a0 \u00a0867 and 255
\nStep 1:\u00a0Since 867 > 255,
\napply Euclid’s division lemma, to a =867 and b=255 to find q and r
\nsuch that 867 = 255q + r, 0 \u2264\u00a0r<255
\nOn dividing 867 by 255 we get quotient as 3 and remainder as 102
\ni.e 867 = 255 x 3 + 102<\/p>\n
Step 2:\u00a0Since remainder 102 \u2260\u00a00,
\nwe apply the division lemma to a=255 and b= 102 to find whole numbers q and r
\nsuch that 255 = 102q + r where 0 \u2264\u00a0r<102
\nOn dividing 255 by 102 we get quotient as 2 and remainder as 51
\ni.e 255 = 102 x 2 + 51<\/p>\n
Step 3:\u00a0Again remainder 51 is non zero,
\nso we apply the division lemma to a=102 and b= 51\u00a0 to find whole numbers q and r
\nsuch that 102 = 51 q + r where 0\u00a0 r < 51
\nOn dividing 102 by 51 quotient is 2 and remainder is 0
\ni.e 102 = 51 x 2 + 0
\nSince the remainder is zero, the divisor at this stage is the HCF
\nSince the divisor at this stage is 51,therefore, HCF of 867 and 255 is 51.<\/p>\n
Concept Insight: To crack such problem remember to apply Euclid’s division Lemma which states that “Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, where 0 \u2264\u00a0r < b” in the correct order.
\nHere, a > b. Euclid’s algorithm works since Dividing ‘a’ by ‘b’, replacing ‘b’ by ‘r’ and ‘a’ by ‘b’ and repeating the process of division till remainder 0 is reached, gives a number which divides a and b exactly.
\ni.e\u00a0\u00a0\u00a0 HCF(a,b) =HCF(b,r)
\nNote that do not find the HCF using prime factorization in this question when the method is specified and do not skip steps.<\/p>\n<\/div>\n
Question 2<\/b>
\n<\/strong>Show that any positive odd integer is of the form 6q<\/i> + 1, or 6q<\/i> + 3, or 6q<\/i> + 5, where q<\/i> is some integer.<\/p>\nSolution:
\n<\/strong>Let a be any odd positive integer we need to prove that a is of the form 6q + 1\u00a0, or\u00a0 6q + 3\u00a0, or\u00a06q + 5\u00a0, where q is some integer. Since a is an integer consider b = 6 another integer applying Euclid’s division lemma
\nwe get a = 6q + r \u00a0for some integer q \u2264\u00a00, and r = 0, 1, 2, 3, 4, 5\u00a0 since
\n0 \u2264\u00a0r < 6.
\nTherefore, a = 6q or 6q + 1 or 6q + 2 or 6q + 3 or 6q + 4 or 6q + 5
\nHowever since a is odd so a cannot take the values 6q, 6q+2 and 6q+4
\n(since all these are divisible by 2)
\nAlso, 6q + 1 = 2 x 3q + 1 = 2k1 + 1, where k1 is a positive integer
\n6q + 3 = (6q + 2) + 1 = 2 (3q + 1) + 1 = 2k2 + 1, where k2 is an integer
\n6q + 5 = (6q + 4) + 1 = 2 (3q + 2) + 1 = 2k3 +\u00a0 1, where k3 is an integer
\nClearly, 6q + 1, 6q + 3, 6q + 5 are of the form 2k + 1, where k is an integer.
\nTherefore, 6q + 1, 6q + 3, 6q + 5 are odd numbers.
\nTherefore, any odd integer can be expressed is of the form
\n6q + 1, or 6q + 3, or 6q + 5 where q is some integer<\/p>\n\n
Concept Insight:\u00a0\u00a0In order to solve such problems\u00a0 Euclid’s division lemma is applied to two integers a and b the integer b must be taken in accordance with what is to be proved, for example here the integer b was taken 6 because a must\u00a0 be of the form 6q + 1, 6q + 3, 6q + 5.
\nBasic definition of even and odd numbers and the fact that addition and, multiplication of integers is always an integer are applicable here.<\/p>\n<\/div>\n
Question 3<\/b>
\n<\/strong>An army contingent of 616 members is to march behind an army band of 32 members in a parade. The two groups are to march in the same number of columns. What is the maximum number of columns in which they can march?<\/p>\nSolution:
\n<\/strong>Maximum number of columns in which the Army contingent and the band can march will be given by HCF (616, 32) We can use Euclid’s algorithm to find the HCF.<\/div>\n\n
Step 1: since 616 > 32 so applying Euclid’s division lemma to a= 616 and b= 32 we get integers q and r as 32 and 19
\ni.e 616 = 32 x 19 + 8<\/p>\n
Step 2: since remainder r =8 \u2260\u00a00 so again applying Euclid’s\u00a0 lemma to 32 and 8 we get\u00a0 integers 4 and 0 as the quotient and remainder i.e 32 = 8 x 4 + 0<\/p>\n
Step 3: Since remainder is zero so divisor at this stage will be the HCF.
\nThe HCF (616, 32) is 8.
\nTherefore, they can march in 8 columns each.<\/p>\n
Concept Insight:\u00a0\u00a0In order to solve the word problems first step is to interpret the problem and identify what is to be determined. The key word “Maximum” means we need to find the HCF. Do not forget to write the unit in the answer.<\/p>\n<\/div>\n
Question 4<\/b>
\n<\/strong>Use Euclid\u2019s division lemma to show that the square of any positive integer is either of form 3m<\/i> or 3m<\/i> + 1 for some integer m.<\/p>\nSolution:
\n<\/strong>Let a be any positive integer we need to prove that a2<\/sup>\u00a0is of the form 3m or 3m + 1 for some integer m.
\nLet b = 3 be\u00a0 the other integer so applying Euclid’s division lemma\u00a0 to a and b=3
\nWe get a = 3q + r for some integer q \u2265\u00a00and r = 0, 1, 2
\nTherefore, a = 3q or 3q + 1 or 3q + 2
\nNow Consider a2<\/sub><\/sup>
\n
\n<\/strong>Where k1<\/sub>\u00a0= 3q2<\/sup><\/sub>, k2<\/sub>\u00a0=3q2<\/sup><\/sub>+2q\u00a0\u00a0 and k3<\/sub>\u00a0= 3q2<\/sub><\/sup>+4q+1\u00a0 since q ,2,3,1 etc are all integers so is their sum and product.
\nSo k1<\/sub>\u00a0k2<\/sub>\u00a0k3<\/sub>\u00a0are all integers.
\nHence, it can be said that the square of any positive integer is either of the form 3m or 3m + 1 for any integer m.
\n<\/strong><\/p>\nConcept Insight: In order to solve such problems\u00a0 Euclid’s division lemma is applied to two integers a and b the integer b must be taken in accordance with what is to be proved, for example here the integer b was taken 3 because a must be of the form 3m or 3m + 1. Do not forget to take a2<\/sup>. Note that variable is just notation and not the absolute value.
\n<\/strong><\/p>\nQuestion 5<\/b>
\n<\/strong>Use Euclid\u2019s division lemma to show that the cube of any positive integer is of the form 9m<\/i>, 9m <\/i>+ 1 or 9m<\/i> + 8.<\/p>\nSolution:
\n<\/strong>Let a be any positive integer and b = 3
\na = 3q + r, where q \u2265\u00a00 and 0\u2264\u00a0r < 3
\n
\nTherefore, every number can be represented as these three forms. There are three cases.<\/p>\nCase 1:\u00a0\u00a0\u00a0\u00a0When a = 3q,
\n
\nWhere m is an integer such that m = \u00a03q3<\/sup><\/p>\nCase 2:\u00a0\u00a0When a = 3q + 1,
\na3<\/sub><\/sup>\u00a0= (3q +1)3<\/sub><\/sup>
\na3<\/sub><\/sup>\u00a0= 27q3<\/sub><\/sup>\u00a0+ 27q2<\/sub><\/sup>\u00a0+ 9q + 1
\na3<\/sub><\/sup>\u00a0= 9(3q3<\/sub><\/sup>\u00a0+ 3q2<\/sub><\/sup>\u00a0+ q) + 1
\na3<\/sub><\/sup>\u00a0= 9m + 1
\nWhere m is an integer such that m = (3q3<\/sup>\u00a0+ 3q2<\/sup>\u00a0+ q)<\/p>\nCase 3:\u00a0 When a = 3q + 2,
\na3 = (3q +2)3<\/sup>
\na3 = 27q3<\/sup>\u00a0+ 54q2<\/sup>\u00a0+ 36q + 8
\na3 = 9(3q3<\/sup>\u00a0+ 6q2<\/sup>\u00a0+ 4q) + 8
\na3 = 9m + 8
\nWhere m is an integer such that m = (3q3<\/sub><\/sup>\u00a0+ 6q2<\/sub><\/sup>\u00a0+ 4q)
\nTherefore, the cube of any positive integer is of the form 9m, 9m + 1,\u00a0or 9m + 8.<\/p>\nConcept Insight: In this problem, Euclid’s division lemma can be applied to integers a and b = 9 as well but using 9 will give us 9 values of r and hence as many cases so solution will be lengthy. Since every number which is divisible by 9 is also divisible by 3. so 3 is used. Do not forget to take a3 and all the different values of a i.e
\n<\/p>\n