## Points to remember

• An algorithm is a series of well defined steps which gives a procedure for solving a type of problem. The word algorithm comes from the name of the 9th century Persian mathematician al-Khwarizmi.
• A lemma is a proven statement used for proving another statement.
• Euclid’s Division Lemma : Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.
• Euclid’s division algorithm : Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers. This is based on Euclid’s division lemma. According to this, the HCF of any two positive integers c and d, with c > d, is obtained as follows:
1. Step 1 : Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.
2. Step 2 : If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.
3. Step 3 : Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.
• Euclid’s division algorithm works because HCF (c, d) = HCF (d, r) where the symbol HCF (c, d) denotes the HCF of c and d, etc.

# Exercise 1.1 Real Numbers | CBSE Class 10th Mathematics | Solutions

1. Use Euclid’s division algorithm to find the HCF of :
(i) 135 and 225    (ii) 196 and 38220   (iii) 867 and 255

Solution : To find the HCF of two given numbers say c and d , first we select the greater of two numbers. Then we take grater number say 'c' as dividend and smaller say'd' as divisor. Applying Euclid’s division lemma, to c and d, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d. If r = 0, divisor is the HCF of two numbr. If r ≠ 0, we apply the division lemma to 'd' as dividend and r (remainder) as divisor in next step. We continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

Solution (i) HCF of 135 and 225

Clearly out of given numbers 135 and 225, 225>135. Therefor, taking greter number 225 as dividend , smaller number 135 as divisor and applying Euclid’s division lemma, to 225 and 135. So, we find whole numbers, q and r such that 225 = 135 × q + r, 0 ≤ r < 135. if r = 0, divisor is the HCF of two numbr. If r ≠ 0, we apply the division lemma to 135 as Dividend and r (remainder) as Divisor in next step. We continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

 225 = 135 × 1 + 90 135 = 90 × 1 + 45 90 = 45 × 2 + 0
 135 ) 225 ( 1 135 90 ) 135 ( 1 90 45 ) 90 ( 2 90 0
There for, HCF (135, 225) = 45

Solution (ii)  HCF of 196 and 38220

Here 38220 > 196.
Therefor, taking greter number 38220 as Dividend , smaller number 196 as Divisor and applying Euclid’s division lemma we have :

 38220 = 196 × 195 + 0
 196 ) 38220 ( 195 196 1862 1764 980 980 0

There for, HCF (196, 38220 ) = 196

Solution (iii)  HCF of 867 and 255
As 867 > 255
Therefor taking 867 as Dividend and 255 as Divisor and applying Euclid’s division lemma, we have :

 867 = 255 × 3 + 102 255 = 102 × 2 + 51 102 = 51 × 2 + 0
 255  ) 867 ( 3 765 102 ) 255 ( 2 204 51 ) 102 ( 2 102 0

There for, HCF (867, 255 ) = 51

2. Show that any positive odd integer is of the form 6q + 1, or 6q + 3, or 6q + 5, where q is some integer.

Solution : Let 'c' be the positive number and d = 6
Then as per Euclid’s division algorithm
c = 6d + r, where q ≥ 0 and 0 ≤ r < 6 and remainders can be any number from 0, 1, 2, 3, 4, 5 etc.
Which means, c may be equal to 6q or 6q + 1 or 6q + 2 or 6q + 3 or 6q + 4 or 6q + 5, where q is quotient.
If c = 6q or 6q + 2 or 6q + 4, then a is an even integer. Also, an integer can be either even or odd.
Therefore, any odd integer is of the form 6q+1 or 6q + 3 or 6q + 5, where q is some integer.

3. 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?

Solution : Here to find the maximum number of columns in which army contingent of 616 members is to march behind an army band of 32 members in a parade, we have to find the HCF of 616 and 32.
 616 = 32 × 19 + 8 8 = 32 × 4 + 0
 32  ) 616 ( 19 32 102 ) 296 ( 2 288 8 ) 32 ( 4 32 0

Therefore, HCF of 616 and 32 is 8
Hence, maximum number of columns is 8

4. 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 integer m.
[Hint : Let x be any positive integer then it is of the form 3q, 3q + 1 or 3q + 2. Now square each of these and show that they can be rewritten in the form 3m or 3m + 1.]

Solution : We know that positive integer x can be expressed in the form of x = 3q or x= 3q + 1 or x = 3q + 2.
Here, we have to prove that the square of each of these can be written as in the form of 3m or 3m + 1.
Now,
 (3q)2 = 9q2 = 3(3q2) = 3 m, where m=3q2 (3q+1)2 = 9q2 + 6q + 1 = 3(3q2 + 2q) + 1 = 3m + 1, where m = 3q2+2q In the same way, (3q+2)2 = 9q2 + 12q + 4 = 3(3q2+4q + 1) + 1 = 3m + 1, where m = 3q2+4q + 1

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

5. Use Euclid’s division lemma to show that the cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8.

Solution : Let x be any positive integer, then it is of the form 3m, 3m+1, 3m+2. Here, we have to prove that the cube of each of them can be expressed in the form 9q, 9q+1 or 9q + 8.
 (3m)3 = 27m3 = 9(3m3) = 9q, where q = 3m3 (3m+1)3 = (3m)3 + 3(3m)2.1 + 3(3m).12+1 = 27m3 + 27m2 + 9m + 1 = 9(3m3 + 3 m 2 + m ) +1 = 9q + 1, where q = 3m3 + 3m2 + m Similarly, (3m+2)3 = (3m)3 + 3(3m)2. 2 + 3(3m).22 + 8 = 27m3 + 54m2 + 36m +8 = 9(3m3 + 6m2+4m) + 8 = 9q + 8, where q = 3m3 + 6m2+4m