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

-