Real Numbers
Mathematics Class Tenth
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
Reference: