1

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?

Alexander Day
  • 885

1 Answers1

1

See https://en.wikipedia.org/wiki/Chinese_remainder_theorem

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

Start with X mod 5 = 3.

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118