# solving a problem on dividing items into piles

there have been many complex modular arithmetic problems, like this one from a book i read, called 1001 mathematics(great book on math, i must say):

A girl has a certain number of pennies. When they are divided in 5's, 3 are left over. when they are divided in 4's, 2 are left over. when they are divided in 3's, 1 is left over. how many pennies could there be?(28)

the way i solved this is by using modular arithmetic, which took a long while. i got this equation:

\begin{align} &X \mod 3=1\\ &X \mod 4=2\\ &X \mod 5=3\\ &X=28 \\ &28 \mod 3=1\\ &28 \mod 4=2\\ &28 \mod 5=3 \end{align}

this took me about 10 minutes. but for more complex ones, this is super slow. is there any faster way to do this?

The 'search by sieving' method is fairly easy to understand and a fairly quick method (certainly beats your 10 minutes!), and goes as follows:

So start with X = 3, and keep adding 5 (for if we keep adding 5, then whatever number we have will remain 3 mod 5) until we get X mod 4 = 2:

3 mod 4 = 3 -> not good, so add 5:

8 mod 4 = 0 -> not good, so add 5:

13 mod 4 = 1 -> not good, so add 5:

18 mod 4 = 2 -> good!

OK, so now we have the 5 and 4 in place, keep adding 4*5 = 20 to X if needed until X mod 3 = 1 (by adding 20 at a time, we make sure that the number remains = 3 mod 5 and = 2 mod 4):

18 mod 3 = 0 -> not good, so add 20:

38 mod 3 = 2 -> not good, so add 20:

58 mod 3 = 1 -> good!

OK, we have our solution: 58

... although any solution plus 3*4*5 = 60 will be a solution as well, so 118, 178, 238, etc. are all solutions as well! In fact, there are infinitely many solutions (58 + 60k), but 58 is the smallest one.

Finally, an observant person may have immediately noticed that if X would be increased by 2, you'd get 0 mod 5, 0 mod 4, and 0 mod 3 ... which you get every 5*4*3 = 60. So, 60-2 = 58 would be an immediate solution. But obviously that really only worked nicely in this particular case.

• what an interesting method!! it is like my method, but in a compact format. – Alexander Day May 1 '17 at 23:21