1
$\begingroup$

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$
  • 2
    $\begingroup$ You are correct that there isn't a unique value. $\endgroup$ – Thomas Andrews Nov 11 '16 at 3:08
  • $\begingroup$ The best I can think of as an alternative is splitting $x = 4q + 2$ into three cases: $x = 12r + 2$, $x = 12r + 6$, $x = 12r + 10$, and then showing that the first two cases both make $x$ give the same remainder when divided by $3$ and $6$ and therefore is not uniquely determined. However this hardly feels like an improvement from writing everything out. $\endgroup$ – 2012ssohn Nov 11 '16 at 3:15
1
$\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$
  • $\begingroup$ This is exactly what I was looking for. Thank you @Bill Dubuque. $\endgroup$ – user3184733 Nov 11 '16 at 5:48
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.