# Prove that the smallest integer producing remainders 2,4,6,1 when divided by 3,5,7,11 respectively is 419.

Prove that the smallest integer producing remainders 2,4,6,1 when divided by 3,5,7,11 respectively is 419.

Here's what I did. x/3 --->Remainder 2. x/5 --->Remainder 4. x/7 --->Remainder 6. x/11 ---->Remainder 1. Notice that adding 1 to x makes things perfectly divisible by 3,5,7,11. So, x+1=LCM(3,5,7,11)=>x=1154, which is not the smallest integer.

• Is it $2,4,6,1$ оr $2,4,6,10$ if it's the first then $x+1$ is divisible by $3,5,7$ but not by $11$. – kingW3 Jun 28 '17 at 19:21

You correctly noted that $x+1$ is divisible by $3,5,7$ but it isn't with $11$ because $x$ gives $1$ as the remainder and $x+1$ gives $2$ as a remainder not $0$.
So it is divisible by $105$ and it must give a remainder of $2$ when divided by $11$ by trial and error it's easy to notice that the first such number is $420$ hence $x=419$.
To prove it, you just need to compute the remainders to show that $419$ works. Then note that solutions recur every $3\cdot 5 \cdot 7 \cdot 11=1155$ so there is no positive integer less than $419$ that works. As stated, the question is wrong because $419-1155=-736$ is smaller than $419$ and it works, too.