CRT MODBasic Intermediate
2013


Problem - 1869
Farmer Hank has fewer than $100$ pigs on his farm. If he groups the pigs five to a pen, there are always three pigs left over. If he groups the pigs seven to a pen, there is always one pig left over. However, if he groups the pigs three to a pen, there are no pigs left over. What is the greatest number of pigs that Farmer Hank could have on his farm?

Answer     78

Let the number of pigs be $n$, then the conditions are $$\left\{  \begin{array}{l} n \equiv 3 \pmod{5} \\ n \equiv 1 \pmod{7} \\ n\equiv 0\pmod{3} \end{array} \right.$$

The standard way to solve such a system of congruent relations is to use the Chinese Remainder Theorem which gives the answer as $$x\equiv 3\times 21 \times 1 + 1\times 15\times 1 \equiv \boxed{78} \pmod{105}$$

Alternatively, given a range is provided (less than $100$), it is possible to guess it out. Firstly, by the first relation, we know $x$ must end with either $3$ or $8$. Then, by the second relation, we know it is necessary to check multiples of $7$ which end with $2$ or $7$. The largest such number less than $100$ is $77$. Finally, we find $77+1=\boxed{78}$ indeed is a multiple of $3$. Hence it is the final answer.

report an error