**Q1. Use Euclid’s division algorithm to find the HCF of:**

(i) 135 and 225 (ii) 196 and 38220 (iii) 867 and 255

(i) 135 and 225 (ii) 196 and 38220 (iii) 867 and 255

**Solution: (i) 135 and 225 **** Step 1**

Since 225 > 135, we can apply Euclid’s division lemma to a = 225 and b = 135 to find q and r such that:

225 = 135q + r, 0 ≤ r < 135

So, dividing by 135 we get 1 as the quotient and 90 as remainder.

i.e., 225 = 135 × 1 + 90**Step 2**

Remainder r is 90 and is not equal to 0, we can apply Euclid’s division lemma to a = 135 and b = 90 to find q and r such that

135 = 90q + r, 0 ≤ r < 90

So, dividing by 90 we get 1 as the quotient and 45 as remainder.

i.e., 135 = 90 × 1 + 45**Step 3**

Remainder r is 45 and is not equal to 0, we can apply Euclid’s division lemma to a = 90 and b = 45 to find q and r such that

90 = 45q + r, 0 ≤ r < 45

So, dividing by 45 we get 2 as the quotient and 0 as remainder.

i.e., 90 = 45 × 2 + 0**Step 4**

Since the remainder is zero, the divisor at this stage will be HCF of (135, 225)

Since the divisor at this stage is 45, therefore, the HCF of 135 and 225 is 45.

**(ii) 196 and 38220****Step 1**

Since 38220 > 196, we can apply Euclid’s division lemma to a = 38220 and b = 196 to find q and r such that:

38220 = 196q + r, 0 ≤ r < 196

So, dividing by 196 we get 195 as the quotient and 0 as remainder.

i.e., 38220 = 196 × 195 + 0**Step 2**

Since the remainder is zero, the divisor at this stage will be HCF of (38220, 196)

Since the divisor at this stage is 196, therefore, the HCF of 38220 and 196 is 196.

**(iii) 867 and 255****Step 1**

Since 867 > 255, we can apply Euclid’s division lemma to a = 867 and b = 255 to find q and r such that:

867 = 255q + r, 0 ≤ r < 255

So, dividing by 255 we get 3 as the quotient and 102 as remainder.

i.e., 867 = 255 × 3 + 102**Step 2**

Remainder r is 102 and is not equal to 0, we can apply Euclid’s division lemma to a = 255 and b = 102 to find q and r such that

255 = 102q + r, 0 ≤ r < 102

So, dividing by 102 we get 2 as the quotient and 51 as remainder.

i.e., 255 =102 × 2 + 51**Step 3**

Remainder r is 51 and is not equal to 0, we can apply Euclid’s division lemma to a = 102 and b = 51 to find q and r such that

102 = 51q + r, 0 ≤ r < 51

So, dividing by 51 we get 2 as the quotient and 0 as remainder.

i.e., 102 = 51 × 2 + 0**Step 4**

Since the remainder is zero, the divisor at this stage will be HCF of (867, 225)

Since the divisor at this stage is 51, therefore, the HCF of 135 and 225 is 51.

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

Solution 2.

**Q3. 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 3.

**Q4. 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 4

**Q5. 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 1

**Exercise 1.2›**