Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$$x \equiv \ 1 \pmod3$$ $$x \equiv \ 2 \pmod5$$ $$x \equiv \ 8 \pmod{11}$$

From the first, I have $x=3k+1$, $x=5j+2$ from the second and $x=11l+8$ from the third. Subbing the third into the second I get

$11l+8 \equiv 2 \pmod5$
$l \equiv -6\pmod5$
$l \equiv -1\pmod5$

So $l=5m-1$

Subbing back into the third equation I had, I get
$x=11(5m-1)+8=55m-3$

Thus $x \equiv -3\pmod{55}$.

I was only asked to find any integer x which satisfies the system of congruences, so any of x of that form should work; i.e. $x=52$.

I want to know if this is the smallest such $x$ which would work, or could I have approached the question in a different way and arrived at another answer?

If I'd been asked to find the smallest $x$, or all $x$, I'm not sure if this approach would have worked. Is there a way to confirm that this is the smallest such $x$, or that all $x$ of the form $x \equiv -3\pmod{55}$ are the only $x$ which satisfy the system?

share|cite|improve this question
2  
See Chinese remainder theorem. – Lucian Apr 11 '14 at 17:14

The smallest answer is 52

Java program for proving this

share|cite|improve this answer
    
Thanks for the code, that's a useful method of verification, but I'm trying to find a solid method to verify by hand that it is the smallest and all other $x$ of the same form are the only solutions; I was worried that feeling my way through by intuition I'd somehow miss some possible values of $x$. – user142340 Apr 11 '14 at 17:37
    
No problem, I didn't know how to do this by hand, but I knew I could contribute with this code and a solution to this particular problem. – Kristoffer Ryhl Apr 11 '14 at 17:56

$ 2\!-\!5 = \color{#c00}{-3} = 8\!-\!11\,$ so $\,x\equiv \color{#c00}{-3}\,$ mod $\,5,11\!\iff\! x\equiv -3\equiv 52\pmod{55},\,$ and $\,52\equiv1\pmod 3$

share|cite|improve this answer

For small moduli, I came up with this method. Make the following table.

\begin{array}{r|ccc} & 3 & 5 & 11\\ \hline 55 & 1 & 0 & 0\\ 33 & 0 & 3 & 0\\ 15 & 0 & 0 & 4\\ \end{array}

Here, $55=5 \times 11,\; 33=3 \times 11,\;$ and $15 = 3 \times 5.$ The table consists of those three numbers modulo $3, 5, $ and $11.$ We need for the diagonal, $[1\; 3\; 4],$ to be $[1\; 2\; 8],$

We can convert $3 \pmod 5$ to $2 \pmod 5$ by multiplying $33$ by $-1$.

We can convert $4 \pmod{11}$ to $8 \pmod{11}$ by multiplying $15$ by $2$.

\begin{array}{r|ccc} & 3 & 5 & 11\\ \hline 55 & 1 & 0 & 0\\ -33 & 0 & 2 & 0\\ 30 & 0 & 0 & 8\\ \end{array}

The number we seek is

$55-33+30 \pmod{3 \times 5 \times 11} = 52 \pmod{165}$

By the CRT, $52$ is the smallest such non negative number.

The smallest such negative number would therefore be $-113$.

share|cite|improve this answer

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.