Answer to Question #272612 in Combinatorics | Number Theory for Prathibha Rose

Question

Solve the following congruences x≡1 mod3, x≡2mod4

x≡3mod5

Answer 1

Let us solve the following system of congruences:

$\begin{cases} x≡1 \mod 3\\ x≡2\mod 4\\ x≡3\mod 5 \end{cases}.$

The first congruence is equivalent to the equality $x=1+3t,\ t\in\Z.$ Let us put this in the second conqruence. Then we have $1+3t\equiv 2 \mod 4.$ The last conqruence is equivalent to $-3t\equiv -1 \mod 4,$ and hence to $(4-3)t\equiv (4-1) \mod 4,$ that is $t\equiv 3 \mod 4.$ It follows that $t=3+4s,$ and hence $x=1+3(3+4s)=10+12s.$ Let us put this in the last conqruence. Then we get $10+12s≡3\mod 5,$ which is equivalent to $12s≡-7\mod 5,$ and hence to $2s≡-2\mod 5.$ It follows that $s\equiv-1\mod 5,$ and hence $s=-1+5k.$ We conclude that $x=10+12s=10+12(-1+5k)=-2+60k.$ Therefore, the solution of the system is $x\equiv -2\mod 60$ or $[-2]_{60}.$