Can you determine the remainder when divided by 6?
By Matthew Cannon
An integer $x$ gives the same remainder when divided by both $3$ and $6$. It also gives a remainder of $2$ when divided by $4$, can you determine an unique remainder when $x$ is divided by $6$?
I feel like you can't since $x=4q+2$ for integer $q$. Listing out some $x$'s gives $x = 2, 6, 10, 14, 18, \cdots$. When you divide these numbers by 6 you get the remainders $2, 0, 4, 2, 0, 4, \cdots$ and when you divide these numbers by 3, you get $2, 0, 1, 2, 0, 1 \cdots$, so the remainders in common are $2$ and $0$, and so it's not enough to determine an unique remainder.
Could anyone show me a proper argument of this without actually having to list out all the numbers and manually "test" it?
$\endgroup$ 23 Answers
$\begingroup$You can solve this from general principles as follows.
Note $\,\ x\bmod 3 = x\bmod 6\iff x\equiv \color{#c00}{0,1,2}\pmod 6$
${\rm By\ \ CRT:}\quad \begin{align}x\equiv \color{#c00}a\pmod6\\x\equiv 2\pmod 4\end{align}\ \ {\rm is\ solvable}\iff \gcd(6,4)=2\mid a\!-\!2\iff 2\mid a$
Hence the above is solvable for both $\,a\equiv 0,2\pmod 6\ $ so $\ x\bmod 6\,$ can be $\,0\,$ or $\,2\,$.
$\endgroup$ 1 $\begingroup$You just need a pair number that satisfy the conditions and give different remainder when they are divided by $6$ to show that you can't do so uniquely.
$x=2$ gives the same remainder of $2$ when $x$ is divided by both $3$ and $6$ and gives a remainder when it is divided by $4$.
$x=6$ gives the same remainder of $0$ when $x$ is divided by both $3$ and $6$ and gives a remainder of $2$ when it is divided by $4$.
Hence, it is possible to obtain remainder of either $0$ or $2$.
$\endgroup$ $\begingroup$The only value possible is 2. Because x gives also a remainder of 2 when divided by 4. It means that we can exclude 0 as common remainder.
$\endgroup$
