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

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$.
-
It is encouraged that you show your progress when asking about homework problems – Jean-Sébastien Oct 24 '12 at 1:13
Your number (possible positive) satisfies $x\equiv 2 \pmod 3$, $x\equiv 3 \pmod 4$ and $x\equiv 4 \pmod 5$. – Sigur Oct 24 '12 at 1:14

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?

-
Calculate $3\cdot 4\cdot 5$. – Berci Oct 24 '12 at 1:20
In this case, all the remainders are zero! – Sigur Oct 24 '12 at 1:23
@Sigur: Dear Sigur, I think that Berci had enough step in mind after making the suggested calculation. Regards, – Matt E Oct 24 '12 at 2:33
@Sigur: I think you missed the point. – The Chaz 2.0 Oct 24 '12 at 2:34
Sorry, people!! – Sigur Oct 24 '12 at 12:28

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.

-

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}$

-