When is $x\equiv a\bmod n$ then $x\equiv a\bmod kn$ true?

Question

I was just experimenting and it seems like this sometimes works

$32\equiv 2\bmod 3$ and $32\equiv 2\bmod 6$ but $32\not\equiv 2\bmod 9$.

What was special at the start for it to work and why didn't it work $\bmod 9?$

Answer 1

well, $x \equiv a \mod n$ implies that $x=mn+a$ for some $m \in \mathbb Z$

$x \equiv a \mod kn$ if there exists some $j$ so that $x=jkn+a$.

So, I guess whenever $n(kj-m)=0$, so for $n \neq 0$, this means that $m=kj$, or $k \mid m$

In other words, if $k \mid x-a$ (it divides $m$ or $n$.)

Answer 2

Suppose $x \equiv a \pmod{n}$. Then you can write $x = a+bn$ for some integer $b$. If $x \equiv a \pmod{kn}$, you can write $x = a + ckn$ for some integer $c$. But that means that $ck=b$ implying that $k$ divides $b$.

So, for your example, $32 \equiv 2 \pmod{3}$. This is equivalent to writing $32 = 2+10\cdot 3$. So, it will also be true that $32 \equiv 2 \pmod{6}$, $32 \equiv 2 \pmod{15}$, and $32 \equiv 2 \pmod{30}$. This corresponds to $3\cdot 2^05^0, 3\cdot 2^15^0, 3\cdot 2^05^1, 3\cdot 2^15^1$. Basically, all of the factors of $b=10$ yield valid multiples for 3.

Answer 3

$x \equiv a \mod n \iff n|x -a \iff x = a + jn$ for some integer $j$.

$x \equiv a \mod nk \iff nk|x-a \iff x = a + jkn$ for some integer $j$.

So $x \equiv a \mod nk \implies x \equiv a \mod n$. (That's clear isn't it? If $nk|x -a$ then $n|x-a$ and if $x = a + jkn = a + (jk)n$ then .... $x = a + (jk)n$.)

But the other direction need not be true.

If $n|x-a$ then $kn|x-a$ if $k|\frac {x-a}n$ which may or may not occur.

So $32 \equiv 2 \mod 6\implies 32 \equiv 2 \mod 3$ and $32 \equiv 2 \mod 2$.

$32 \equiv 2 \mod 3$ does not imply $32 \equiv 2 \mod 6$ (but as $2|\frac {32 - 2}{3} = 10$, it DOES any way). And it does not imply that $32 \equiv 2 \mod 9$ (and as $3 \not \mid \frac {32 -2}3 = 10$ it does not.)

(But note: $5|\frac {32-2}3 = 10$ so $32 \equiv 2 \mod 15$.... neat.)

So:

If $n|x-a$ and if $k|\frac {x-a}n$ then $x \equiv a \mod n$ and $x\equiv a \mod kn$.

If $n\not \mid x-a$ then $x \not \equiv a \mod n$ and $x \not \equiv a \mod kn$.

And if $n|x-a$ but $k \not \mid \frac {x-a}n$ then $x \equiv a \mod n$ but $x \not \equiv a \mod kn$.