Can you count the number of soldiers..

You are given that there are less than 1000 soldiers assembled in a battle field. They have done three 'count off's. (Each one remembers the number the last soldier shouted out and shouts out the next number if it is less than the 'count off' number or starts with number one). They have carried out 'count off by sevens', then 'count off by tens' and finally 'count off by thirteen'. The numbers the last soldier in the assembly shouted out were one, three and eight respectively. The commander wants to know the exact soldier count.

The answer is 463!

Notice 7, 10 and 13 are relatively prime in pairs. You can apply the Chinese Remainder Theorem! The three congruences x ~ 1 (mod 7), x ~ 3 (mod 10) and x ~8 (mod 13) have common solutions, where x is the exact soldier count. Any two common solutions are congruent modulo 910 (that is 7 * 10 * 13).

Using number theory, we can show that x ~ 463 (mod 910). The solutions are 463, 1373 (463 + 910), 2283 and so on. Since there are less than 1000, the answer is 463.

(Note: I have used '~' as the congurence symbol, but we usually use 'equivalent' notation for that)

(Courtesy: The Art of War by Sun Tsu in the 17th century; adapted from the Wagstaff's Number Theory book)

Isn't it cool..

Here are some more similar challenges:
Eggs in the basket
Five pirates and a monkey