If $x \equiv 1 \pmod 3$ and $x \equiv 0 \pmod 2$, what is $x \pmod 6$?

Question

If you know what a number mod two different primes is (3 and 2) in this case, how can you tell what the mod is of the two products?

Answer 1

Use Chinese remainder theorem.

$$x \equiv 1 \pmod 3 \implies x = 3k + 1$$ $$x \equiv 0 \pmod 3 \implies x = 2n$$

Now we have:

$$3k + 1 = 2k$$

Work modulo $2$ and we have:

$$3k + 1 \equiv 0 \pmod 2$$ $$k \equiv -1 \equiv 1 \pmod 2 \implies k = 2m + 1$$

Now substitute and we have:

$$x = 3k + 1 = 3(2m + 1) + 1 = 6m + 4 \implies x \equiv 4 \pmod 6$$

Answer 2

Since $x\equiv 1\pmod 3$, $x=3k+1$, so, if $3k+1\equiv 0\pmod 2$, then...

Answer 3

Hint $\, $ If $\,m\,$ is odd then $\,x\equiv a\pmod m\iff x \equiv a,\ a\!+\!m\pmod{2m}.\,$ Since $\,m\,$ is odd we see that $\,a\,$ and $\,a+m\,$ have opposite parity, so one of them has the desired parity $\equiv b\pmod{2}.$

Therefore, $ $ for example, $\ x\equiv 1\pmod{3}\iff x\equiv 1,\color{#c00}4\pmod 6,\,$ so $\ x\equiv \color{#c00}4\,$ if $\,x\,$ is even.

More generally one can use the Chinese Remainder Theorem.

Answer 4

In this case the number mod 6 must be 0, 2, or 4, because it's 0 mod 2. And mod 6 it must be 1 or 4 because it's 1 mod 3. Hence it's 4 when modded by 6.

Answer 5

$x = 3a + 1$ and $x = 2b + 0$. So $3a - 2b + 1 = 0$

Let $c = a - b$. So $a + 2c + 1 = 0$.

Let $d = a + c$. So $d + c + 1 = 0$.

Let $e = d + c$. So $e + 1 = 0$ and $e = -1$.

Since $e = d + c$, $d = -1 - c$.

Since $d = a + c$, $-1 - c = a + c$ and $a = -1 - 2c$.

$x = 3a + 1 = 3(-1 - 2c) + 1 = -3 - 6c + 1 = -6c - 2$. So $x \equiv 4 \mod 6$