Find an integer $x$ satisfying the congruence:

Question

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

Answer 1

The smallest answer is 52

Java program for proving this

Answer 2

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

Answer 3

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

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

Let $N = 3 \times 5 \times 11 = 165$. Then $55=\dfrac N3,\; 33= \dfrac N5;$ and $15 = \dfrac N{11}$. The table consists of those three numbers modulo $3, 5, $ and $11.$ We need for the diagonal, $[1\; 3\; 4],$ to become $[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} & \mod 3 & \mod 5 & \mod{11}\\ \hline 55 & 1 & 0 & 0\\ -33 & 0 & 2 & 0\\ 30 & 0 & 0 & 8\\ \hline 52 & 1 & 2 & 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$.