Find a number $x<100$ that satisfies three congruences.

Question

Find a number $x<100$ for which all three statements are true:

• When $x$ is divided by $3$, the remainder is $2$.
• When $x$ is divided by $4$, the remainder is $3$.
• When $x$ is divided by $5$, the remainder is $4$.

Answer 1

The number $-1$ is less than 100, and all three statements are true. If you don't like $-1$, can you see how to fix it?

Answer 2

Hint $\rm\,\ 3,4,5\:|\:x\!+\!1 \iff lcm(3,4,5)\:|\:x\!+\!1\iff 60\:|\:x\!+\!1\iff x\equiv -1\equiv 59\pmod{60}$

Answer 3

Basically, to solve this, you want to look at the Chinese Remainder Theorem. For this problem, you have a system of three congruencies:

$x\equiv 2 \pmod 3$
$x\equiv 3 \pmod 4$
$x\equiv 4 \pmod 5$

Now, for the Chinese Remainder Theorem, the GCD of all of the modulus must be 1, so $GCD(3, 4, 5)$. If you examine 3, 4, and 5, you will notice that all three are relatively prime. Thus their GCD will be 1.

So, now, the theorem states that a solution exists a solution to

$x\equiv a_1 \pmod {m_1}$
$x\equiv a_2 \pmod {m_2}$
$x\equiv a_3 \pmod {m_3}$

Which is

$x\equiv a_1(m_2 m_3)\overline{(m_2 m_3)} \pmod {m_1}$
$+ a_2(m_1 m_2)\overline{(m_1 m_3)} \pmod {m_2}$
$+ a_3(m_1 m_2)\overline{(m_1 m_2)} \pmod {m_3}$
$\pmod{m_1 m_2 m_3}$

Where $\overline{(m_2 m_3)}\pmod{m_1}$ is the inverse of $m_2 m_3$ in mod $m_1$. If you simply plug in the numbers from the original problem, you now get (I am going to leave off the final modulus for the moment, but the overall answer will be in mod 3*4*5=60:

$x\equiv 2(4*5)\overline{(4*5)} \pmod {3}$
$+ 3(3*5)\overline{(3*5)} \pmod {4}$
$+ 4(3*4)\overline{(3*4)} \pmod {5}$

$x\equiv 2(20)\overline{(20)} \pmod {3}$
$+ 3(15)\overline{(15)} \pmod {4}$
$+ 4(12)\overline{(12)} \pmod {5}$

$x\equiv 40\overline{(2)} \pmod {3}$
$+ 45\overline{(3)} \pmod {4}$
$+ 48\overline{(2)} \pmod {5}$

Now, the inverse of 2 in mod 3 is 2, because $2*2=4$, $4 \pmod 3 = 1$. Similarly, you're able to find that $\bar{3}\pmod 4 = 3$ and $\bar{2}\pmod 5=3$

$x\equiv 40*2$
$+ 45*3$
$+ 48*3$

$x\equiv 80 + 135 + 144$

$x\equiv 359$

Now, accounting for the mod that I left off at the beginning, we get

$x\equiv 359 \pmod {60}$

$x\equiv 59 \pmod {60}$

So, there's what the value is, below 100, 59 should satisfy those three linear congruencies.