How to solve a system of linear congruences?

Question

I am confused on how to go forward with solving this question. It is:

If a number x is divided by 5, it leaves a remainder of 3. If x is divided by 7, it leaves a remainder of 2. If x is divided by 3, it leaves a remainder of 1. What is x?

My method is that I check the units digits of each multiple, so in this case, the units digit of the number can only be equal to 8. It's because a multiple of 5 plus 3 either ends in 8 or 3, but a multiple of 3 plus 1 cannot end in 3. I then brute force using other values that the question give.

I have already solved it to 58 (I think it is right), but I am looking for a quicker method than my previous one.

Answer 1

Hint $\,\bmod 3,5,7\!:\ 2x\equiv 11\iff \bmod 105\!:\ 2x\equiv 11\equiv 116\iff \bbox[5px,border:1px solid #c00]{x\equiv 58}\ \ $

Remark $ $ This method works for residues and moduli in arithmetic progression, as here, i.e.

$$\begin{align} &x\equiv 2\!\!\pmod{7}\\ &x\equiv 3\!\!\pmod{5}\\ &x\equiv 4\!\!\pmod{3}\end{align}\qquad\qquad\qquad\qquad$$

Note progressions $\, 7,5,3 = 7\!-\!2k\ $ and $\ 2,3,4 = 2\!+\!k,\,$ i.e. $\,x\equiv 2\!+\!k\pmod{7\!-\!2k}\,$ so

$\!\!\bmod\, \color{#c00}{7\!-\!2k}\!:\,\ x\equiv 2\!+\!k\iff 2x\equiv 4\!+\!\color{#c00}{2k}\equiv 4\!+\!\color{#c00}7\equiv 11\,$ hence

$7,5,3\mid 2x\!-\!11\iff 105\mid 2x\!-\!11$ $\iff 105\mid 2x\!-\!11\!-\!105=2(x\!-\!58)\iff 105\mid x\!-\!58$

For further discussion of this method see this answer and its linked questions (coincidentally that boils down to the modular fraction $\,x\equiv -11/2,\,$ i.e. the negative of above).

Typically human-devised CRT exercises involve small numbers - which increases the probability that such linear progression structure will be evident.

Answer 2

Here is a solution using Bezout coeffecients and isomorphisms as in the Chinese remainder theorem:

$x\cong3\pmod5$ and $x\cong2\pmod7$. Since $-4\cdot5+3\cdot7=1$, we get $x\cong-20\cdot2+21\cdot3\cong23\pmod{35}$.

Then $x\cong1\pmod3$ and $x\cong23\pmod{35}$. We solve with Bezout coefficients again. $3\cdot12-1\cdot 35=1$. So $x\cong36\cdot23-35\cdot1\cong793\cong58\pmod{105}$.

Granted @Bill, er, @Gone's solution is better.