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
  • 2
    $\begingroup$ You are correct that there isn't a unique value. $\endgroup$ Commented Nov 11, 2016 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
    Commented Nov 11, 2016 at 3:15

3 Answers 3

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$
1
  • $\begingroup$ This is exactly what I was looking for. Thank you @Bill Dubuque. $\endgroup$ Commented Nov 11, 2016 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$
0
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .