Brain-Teaser 457

From The Sunday Times, 15th February 1970 [link]

The Duke of Teresa and Baron von Barin agreed to have a march-past of their respective men-at-arms to celebrate the wedding of the Duke’s son with Baron’s daughter. Each troop would march past in column of three (i.e. 3 men per file). The Duke has a few thousand men and the Baron about half as many.

On the appointed day however, one of the Duke’s men could not go on parade and so the men were ordered into column of four, but 3 men were left over, whereupon they formed column of five and 4 men were left over, and this pattern of behaviour persisted as the Duke consecutively increased the number per file until all the men made an exact number of files.

Meanwhile, the Baron has the same problem. One man reported sick and he consecutively increased the number per file and in column of four had 3 left over, column of five had 4 left over, etc., and eventually he reached a number per file that left no man spare.

The Baron’s men proceeded to march past but the Duke was in a dilemma as each body of troops had a different number of men per file. He immediately solved this by ordering his men to form files with the same number of men as the Baron’s. This they did without any men being left over.

How many men respectively had the Duke and the Baron on parade?