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?

159.9k+ views
Hint:Use the Euclidean Algorithm. Find the quotient and remainder of 616 and 32. By dividing 616 by 32 you’ll get the no. of columns. Then divide $\dfrac{32}{8}$. Finally you will find H.C.F (616, 32).

Complete step-by-step answer:
To get the maximum no. of columns, we need to find HCF.
To get the minimum no. of columns, we need to find LCM.
By using Euclidean Algorithm,
The greatest common divisor (GCD) of two integers A and B is the largest integer that divides both A and B.
The Euclidean Algorithm is a technique for quickly finding the GCD of two integers.
Here A=616 and B=32
$A\ne 0$ and $B\ne 0$
Here, $A>B$ i.e. $616>32$
Now use long division to find $\dfrac{616}{32}=19$ with a remainder of 8..

We can find that the remainder is not zero.
Hence it can be written as,
$616=32\times 19+8$
Similarly using long division find $\dfrac{32}{8}$

Here the remainder is zero.
$32=8\times 4+0$
Hence the HCF of 616 and 32 is 8.
$\therefore $Max no. of columns = HCF(616,32)=8

Note: Directly take the HCF(616,32) by prime factorization.
To find HCF, both numbers should have same common factors
$\therefore $HCF(616,32)= $2\times 2\times 2=8$