A section of soldiers are rehearsing for the march past for the National Day parade . If they march in pairs , one soldier will be without a partner . If they match in threes , fives or sevens , they will be a soldier short. Calculate the smallest possible number of soldiers for this section.

After I found LCM for 2,3,5,7 , why must I take the LCM number and minus it by 1 ?

  • $\begingroup$ Have you ever heard of the Chinese Remainder Theorem? The problem statement gives you the system $\begin{cases} x\equiv 1\pmod{2}\\x\equiv 2\pmod{3}\\x\equiv 4\pmod{5}\\x\equiv 6\pmod{7}\end{cases}$ Applying chinese remainder theorem, there will be a unique solution modulo $2\cdot 3\cdot 5\cdot 7$. In this case, it is easy to see that since each of the equivalencies in the system are congruent to $-1$, that $2\cdot 3\cdot 5\cdot 7-1$ is a solution, and since the solution is unique that it must be the only one. $\endgroup$ – JMoravitz Jan 17 '16 at 17:16

Look at it this way. If you just had one more soldier, then the total number of soldiers would be divisible by 2, 3, 5, and 7. So if you just had one more soldier, the smallest number of soldiers you would have is the LCM of 2, 3, 5, and 7.

However, you don't have one more soldier. So the number you do have is the LCM - 1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.