There is a general and his army of 13 soldiers (14 people in total) raided an enemy base. After conquering the base, they tried to divide the supplies they found into 14 equal portions. However, when they divide up the supplies they end up with 9 extra portions.
They remembered that one solider had been killed in the raid. So they redivided the supplies for 13 soldiers. This time they only had 5 left over portions.
Then they recalled that 2 more soldiers had been killed and they only had to divide the supplies 11 ways. This time they divided it equally with no extra supplies left.
Assuming that there was 5000 portions of supplies what's the least number of portions of supplies that the soldiers had taken?
-Having a hard time with this problem, after several failed attempts I came to my professor who recommended I use the Chinese Remainder Theorem. This unfortunately, was not very helpful and I'm still having a tough time figuring this out. Any help is greatly appreciated.
This can easily be computed by hand too. The conditions are $$ x = 9 \mod 14\,\,(1) \\ x = 5 \mod 13 \,\,(2)\\ x = 0 \mod 11 \,\,(3)$$ Going from the bottom-up, the numbers satisfying $(3)$ are $$ x \in \{11,22,33,\dots\}$$ Of these, the numbers satisfying $(2)$ are $$ x \in \{44,187,330,\dots\}$$ (The remainders repeat with periodicity 13).
Of these, the numbers satisfying $(1)$ are $$ x \in \{1045,3047,5049,\dots\}$$ (The remainders repeat with periodicity 14).
Clearly, the lowest number satisfying all conditions is $$x = 1045$$