Vachmi
Use Euclid's division algorithm to find the HCF of :
(i) 135 and 225 (ii) 196 and 38220 (iii) 867 and 255
Solution
(i) 135 and 225
As 225 > 135, applying Euclid's division algorithm,
225 = 135 x 1 + 90
As remainder 90 ≠ 0, again using Eulid's division algorithm,
135 = 90 x 1 + 45
Again as remainder 45 ≠ 0, we can write,
90 = 2 x 45 + 0
As remainder is now 0, HCF of 135 and 225 is 45.
(ii) 196 and 38220
Applying Euclid's division algorithm
38220 = 196 x 195 + 0
As the remainder is 0, HCF of 196 and 38220 is 196.
(iii) 867 and 255
Applying Euclid's division algorithm,
867 = 255 x 3 + 102
255 = 102 x 2 + 51
102 = 51 x 2 + 0
Therefore, HCF of 867 and 255 is 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 a be any positive integer and b = 6.
Using Euclid's algorithm,
a = 6q + r for integer q ≥ 0 and r = 0, 1, 2, 3, 4, 5 because 0 ≤ r < 6.
∴ a = 6q or 6q + 1 or 6q + 2 or 6q + 3 or 6q + 4 or 6q + 5
6q + 1 = (6q + 0) + 1 = 2 (3q + 0) + 1 = 2k1 + 1, where k1 is a positive integer
6q + 3 = (6q + 2) + 1 = 2 (3q + 1) + 1 = 2k2 + 1, where k2 is a positive integer
6q + 5 = (6q + 4) + 1 = 2 (3q + 2) + 1 = 2k3 + 1, where k3 is a positive integer
Clearly, 6q + 1, 6q + 3, 6q + 5 are of the form 2k + 1, where k is an integer.
As these expressions represent odd numbers, 6q + 1, 6q + 3, 6q + 5 are not divisible by 2.
Hence any odd integer can be expressed in the form 6q + 1, or 6q + 3, or 6q + 5
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
Maximum number of columns in which the Army contingent and the band can march = HCF (616, 32)
Appplying Euclid's algorithm to find the HCF.
As 616 > 32, applying Euclid's division algorithm, a = 616 and b = 32,
616 = 32 x 19 + 8
As remainder = 8, again applying Euclid's division algorithm,
32 = 8 x 4 + 0
As the remainder is 0, so divisor at this stage will be HCF.
∴ HCF(616, 32) = 8
∴ they can march in 8 columns.