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.

$$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|improve this question
2  
See Chinese remainder theorem. –  Lucian Apr 11 at 17:14

2 Answers 2

The smallest answer is 52

Java program for proving this

share|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 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. –  Darksonn Apr 11 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|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.