0

Let a, b, c be positive integers satisfying: $$ a \equiv 0 \;(mod\;3)\\ b \equiv 0 \;(mod\;5)\\ c \equiv 0 \;(mod\;7)\\ a+b \equiv 0 \;(mod\;67)\\ b+c \equiv 0 \;(mod\;17)\\ c+a \equiv 0 \;(mod\;73)\\ $$

This problem requires the smallest possible value of a + b + c.

My approach was to solve this congruence equation with an attempt to obtain some general formulae for a, b and c but it did not seem to work.

I would like to know how simultaneous equations in different congruence can be solved in general (if there is any reference for that) or whether there is any trick to handle this particular problem without considering the general problem.

ichallas
  • 55

1 Answers1

0

Hint

Let $a+b+c=x$, then the last three congruences can be written as \begin{align*} x \equiv c \pmod{67}\\ x \equiv a \pmod{17}\\ x \equiv b \pmod{73} \end{align*} Since the modulii are relatively prime use Chinese Remainder Theorem. Of course you will need to incorporate the first three congruences ultimately, but that will be an easy task.

Anurag A
  • 41,067
  • Thank you so much for the help. I am still working on it since I have almost no experience – ichallas Oct 12 '16 at 14:09
  • I used the Chinese Remainder Theorem and obtained an expression like x = 177323c + 677320a + 67175b (mod 6717*73). I attempted to replace c with 7m, a with 3n ,b with 5k. However, I got some really huge numbers. And I even verified that solutions satisfying this one congruence made may not be a solution for the original problem. Would you provide some more help on this problem? – ichallas Oct 15 '16 at 06:16