Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
