Congruence arithmetic proof of $2i \equiv 2j \pmod{2m}$ implies $i \equiv j \pmod{2m}$ or $i\equiv j + m \pmod{2m}$.

276 Views Asked by At

If $2i \equiv 2j \pmod{2m}$, then either $i \equiv j \pmod{2m}$ or $i + m \equiv j \pmod{2m}$. This is easy to show by using the definition, i.e. if $2m$ divides $2(i-j)$, then either $2m$ divides $(i-j)$ (the first congruence), or not, in which case we have $km = i - j$ with $k$ odd. But then $(k+1)m = i - j + m$ and $k+1$ is even, hence $2m$ divides $i - j + m$.

But is there a way to show this just using the congruence relations listed for example here or here, i.e. without explicitly unfolding the definition but just using the "congruence calculus"?

2

There are 2 best solutions below

0
On BEST ANSWER

By no. 12 on the Wolfram page, you have $i \equiv j \pmod{m}$, so $j-i \equiv 0 \pmod{m}$. Thus the entire problem reduces to showing that $k \equiv 0 \pmod{m}$ implies $k \equiv 0,m \pmod{2m}$. At this point I would depart from the lists of properties you linked to and say that, since $m | 2m$, there is a well-defined mapping from $Z_{2m}$ to $Z_m$ that takes an integer from its congruence class modulo $2m$ to its congruence class modulo $m$. We are interested in finding the inverse image of $0 \pmod{m}$ under this mapping. So we need only observe that the multiples of $m$ among $0,1,\dots 2m-1$ are precisely $0$ and $m$.

0
On

$$2i\equiv 2j\pmod{2m}\iff i\equiv j\pmod{m}$$

$$i=mk+j\iff \begin{cases}i=m(2t)+j\\\text{or}\\i=m(2t+1)+j\end{cases}$$

$$\iff \begin{cases}i=2mt+j\\\text{or}\\i=2mt+m+j\end{cases}\iff \begin{cases}i\equiv j\pmod{2m}\\\text{or}\\i\equiv m+j\pmod{2m}\end{cases}$$