1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.