# Find an integer $x$ satisfying the congruence:

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

-
– Lucian Apr 11 '14 at 17:14

Java program for proving this

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

-

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

-