Real Numbers

Mathematics Class Tenth

10th-Math-home


Theorem: Euclid's Division Lemma

Theorem of Euclid’s Division Lemma States that Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b

Euclid’s division algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.

To obtain the HCF of two positive integers, say c and d, with c > d, the steps given below are followed:

Step (1) Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = d q + r, 0 ≤ r < d.

Step (2) If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.

Step (3) Continue the process till the remainder is zero. The divisor at this stage will be the required HCF.

NCERT Exercise 1.1 solution

Question (1) Use Euclid’s division algorithm to find the HCF of:

(i) 135 and 225

Solution

Here, given 135 and 225, in which 225 > 135.

After applying the Euclid’s Division Lemma, we get

225 = 135 × 1 + 90

Here, since the remainder 90 ≠ 0, thus again by applying Euclid’s Division Lemma, we get

135 = 90 × 1 + 45

Here, again since, remainder 45 ≠ 0, thus again by applying Euclid’s Division Lemma, we get

90 = 2 × 45 + 0

Here, the remainder, became equal to zero (0), thus, the divisor 45 is the HCF of 135 and 225.

Thus, Answer = 45

(ii) 196 and 38220

Solution

Here, in the given pair of integers, 38220 > 196

Thus, after applying the Euclid's division Lemma, we get

38220 = 196 × 195 + 0

Here, since the remainder becomes zero, and the divisor is 196, thus, HCF of the given pair of integers is 196.

Thus, Answer = 196.

(iii) 867 and 255

Solution

Here given pair of integers = 867 and 255

Since, 867 > 255, thus by applying Euclid's Division Lemma, we get

867 = 255 × 3 + 102

Since, remainder 102 ≠ 0 thus, after applying Euclid's Division Lemma again to 255 and 102, we get

255 = 102 × 2 + 51

Since, here remainder 51 ≠ 0, after applying Euclid's Division Lemma again to 102 and 51, we get

102 = 51 × 2 = 0

Here, since the remainder becomes zero, thus the process is stopped and divisor, 51 is the HCF for the given pair of integers 867 and 255.

Thus, Answer = 51

Question: (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 a be any positive integer and b = 6.

Therefore, according to Euclid's Division Lemma,

a = 6q + r for some integer a ≥ 0

And r = 0, 1, 2, 6, 4, 5 because 0 ≤ r < 6

∴ a = 6q or 6q + 1 or 6q + 3 or 6q + 4 or 6q + 5.

And, 6q + 1 = 2 × 3q + 1 =2k1 + 1 where k1 is a positive integer

And, 6q + 3 = (6q + 2) + 1 = 2(3q + 1) + 1 = 2k2 + 1, where k2 is an integer

Similarly, 6q + 5 = (6q + 4) + 1 = 2(3q + 2) + 1 = 2K3 + 1 where k3 is an integer

Clearly, 6q + 1, 6q + 3, 6q + 5 are of the form 2k + 1, where k is an integer.

Therefore, 6q + 1, 6q + 3 and 6q + 5 are not exactly divisible by 2, i.e. are odd numbers.

Thus, these given expressions of numbers are odd numbers.

And therefore, any odd integer can be expressed in the form of 6q + 1, or 6q + 3 or 6q + 5 Proved

Question: (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, the HCF of given numbers 616, and 32 will give the maximum number of columns in which the army can march.

After using Euclid's Division Lemma to 616 and 32 we get

616 = 32 × 19 + 8

Here, since remainder 8≠ 0 thus by continuing Euclid's Division Lemma to 32 and 8, we get

32 = 8 × 4 + 0

Here, since the remainder becomes zero, thus HCF of the given numbers 616 and 32 is 8.

Thus, the army can march in8 columns each.

Hence, Answer = 8.

Question: (4) Use Euclid's Division lemma to show that the square of any positive integer is either of the form 3 m or 3m + 1 for some integer m.

[Hint : Let x by any positive integer then it is of the form 3q, 3q + 1 or 3q + 2q. Now square each of these and show that they can be rewritten in form 3m or 3m + 1.]

Solution:

Let a by any positive integer and b = 3.

Then a = 3q + r for some integer q ≥ 0

And r = 0, 1, 2 because 0 ≤ r < 3

Therefore, a = 3q or 3q + 1 or 3q + 2

Or,

a2 = (3q)2 or (3q + 1)2 or (3q + 2)2

⇒ a2 = 9 q2 or 9 q2 + 6q + 1 or 9 q2 + 12q + 4

⇒ a2 = 3 × (3q2) or 3 (3q2 + 2q) + 1 or 3 (3q2 + 4q) + 1

⇒ a2 = 3k1 or 3k2 + 1 or 3k3 + 1

Where, k1, k2 and k3 are some positive integers.

Thus, it can be said that the square of any positive integer is either of form 3m or 3m + 1.

Question: (5) Use Euclid's Division Lemma to show that the cube of any positive integer is of the form 9 m, 9m + 1 or 9m + 8.

Solution

Let a by any positive integer and b = 3

a = 3q + r where q ≥ 0 and 0 ≤ r < 3

∴ a = 3q or 3q + 1 or 3q + 2

Now,

Case-I:

When a = 3q

∴ a3 = (3 q)3 = 27q3

= 9(3q3) = 9m

Where, m is an integer and = 3q3

Case-II:

When, a = 3q + 1

⇒ a3 = (3q + 1)3

⇒ a3 = 27q3 + 27q2 + 9q + 1

⇒ a3 = 9 (3q3 + 3q2 + q) + 1

⇒ a3 = 9m + 1

Where, m is an integer and is equal to 3q3 + 3q2 + q

Case-III:

When, a = 3q + 2

⇒ a3 = (3q + 2)3

⇒ a3 = 27 q3 + 54 q2 + 36 q + 8

⇒ a3 = 9 (3q3 + 6q2 + 4q) + 8

⇒ a3 = 9m + 8

Where, m is an integer and is equal to 3q3 + 6q2 + 4q

Therefore, the cube of any positive integer is of the form 9m, 9m + 1 or 9m + 8 Proved

MCQs Test

Back to 10th-Math-home



Reference: