Question

A group of $616$ students is to march behind an army band of $32$ members in a parade. The two groups must march in the same number of columns. What can be the maximum number of columns in which they march?

• A. $3$
• B. $8$
• C. $12$
• D. $4$

Answer 1

Answer: (B)

$8$

It is given that there is a group of $616$ students march behind an army band of $32$ members in a parade. We use euclid's algorithm in this problem.

Let us first state Euclid’s division algorithm:

To obtain the HCF of two positive integers, say $c$ and $d$, with $c>d$, follow the steps below:

Step 1 : Apply Euclid’s division lemma, to $c$ and $d$. So, we find whole numbers, $q$ and $r$ such that $c=dq+r,0\le r<d$.

Step 2 : If $r=0$, $d$ is the HCF of $c$ and $d$. If $r\ne 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.

Now, let us apply the Euclid’s division algorithm to $616$ and $32$ as follows:

$616=32\times 19+8$

Since the remainder is $8$ which is not equal to $0$. Therefore, we again apply Euclid’s division algorithm to $32$ and $8$ as shown below:

$32=8\times 4+0$

Since the remainder is $0$, therefore, the HCF of $616$ and $32$ is $8$.

Hence, the maximum number of columns in which they march is $8$ columns.