# If $x \equiv a \mod{n}$, then either $x \equiv a \mod{2n}$, or $x \equiv a + n \mod{2n}$

My rationale was the following. If $$n$$ is even, then

$$n \mid x - a \implies n \mid x - a - n \implies n \mid \frac{1}{2} (x - a - n) \implies 2n \mid x - a - n$$

so $$x \equiv a + n \mod{2n}$$. On the other hand, if $$n$$ is odd, $$(n:2)=1$$. Hence the Chinese remainder theorem guarantees that the linear congruence system

$$\begin{cases} x \equiv a \mod{n} \\ x \equiv a \mod{2} \end{cases}$$

has a unique solution modulo $$2n$$. We know the solution is $$x \equiv a(2+n) \mod{2n}$$, which is congruent to $$n \equiv a(2 - n) \mod{2n}$$.

Given that $$n$$ is odd, $$(2+n:2-n)=1$$. Therefore $$x \equiv a \mod{2n}$$.

Is this more or less correct?

• Something is fishy here. Take $n=4, x =3, a = 3$. Your proof says that since $n$ is even, 3 is congruent to 7 mod 8, which is not correct. Can you find the error? – user113102 May 28 '19 at 19:12

I don't quite see what you are doing. Let $$x-a = tn \; .$$
If $$t$$ is even, let $$t = 2 s,$$ so $$x-a = s(2n)$$ so $$x \equiv a \pmod {2n}$$
If $$t$$ is odd, write $$t = 2r + 1,$$ so $$x-a = tn = (2r+1)n = 2rn + n \; ,$$ $$x-a = r(2n) + n,$$ $$x= a + n + r (2n)$$ $$x \equiv a +n \pmod {2n}$$
\phantom{.}\\{\bf Hint}\ \ x\equiv a\pmod{\!n} \iff \overbrace{x = a + n\,k}^{\large\text{for some } k\ \in\ \Bbb Z} \iff \left\{ \begin{align} &x =\smash[t]{\overbrace{a+n(2j)}^{\large \color{#c00}a\ \ +\ \ 2n\,j}}\ \ \ \ \ \ \ \, {\rm if}\ \ k = \,2j\ \ \ \ \ \ \rm is\ even\\ &x = \smash[b]{\underbrace{a+n(1\!+\!2j)}_{\large \color{#c00}{a+n}\ \ +\ \ 2n\,j}}\ \ {\rm if}\ \ k = 1\!+\!2j\ \ \rm is\ odd\\[-1em] \phantom{.} \end{align}\right.
by $$\ k = r\! +\! 2j\$$ for $$\, r = 0\,$$ or $$\,1\,$$ by Division with Remainder.