Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.
share|improve this question
5  
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
add comment

3 Answers

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?

share|improve this answer
4  
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
1  
@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
add comment

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.

share|improve this answer
2  
You did notice that the problem is tagged "homework", right? –  Gerry Myerson Oct 24 '12 at 2:39
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.