Proof of $ac ≡ bc \pmod {m} \longleftrightarrow a ≡ b \pmod {\dfrac{m} {\gcd(c,m)}}$

Question

Not really sure how to go about this problem, especially since there is a bi-conditional nested in a larger conditional statement. If anyone could show me how to progress I'd really appreciate it.

Show that if $m$ is an integer greater than $1$ and $a, b, c$ are integers, then $$ac ≡ bc \pmod {m} \longleftrightarrow a ≡ b \pmod {\dfrac{m} {\gcd(c,m)}}$$

Answer 1

"Show that if $m$ is an integer greater than $1$ and $a, b, c$ are integers, then..."

This conditional is not really a part of the statement. It just sets the context of the statement. It tells you "We are working with integers here, not rational or real numbers". This is a very important assumption, but that's it. Think about it as given assumptions that set the stage for the biconditional, not as a conditional we need to prove.

As for the biconditional, I would suggest that you rephrase the modular arithmetic into statements about divisibility. Try one of the following rephrasings:

• $m\mid (ac-bc)\iff \frac{m}{\gcd(m, c)}\mid (a-b)$
• $\frac{ac-bc}m$ is an integer $\iff\frac{a-b}{\gcd(m, c)}$ is an integer
• There is an integer $x$ such that $ac-bc = xm\iff$ there is an integer $y$ such that $a-b = \frac {ym}{\gcd(m, c)}$

Answer 2

Set $d=\gcd(c,m)$, $\,c'=\dfrac cd$, $\,m'=\dfrac md$. The assertion can be translated as $$\exists k\in\mathbf Z,\; ac'd =bc'd+km'd\iff \exists k\in\mathbf Z,\; ac'=bc'+km'\iff ac'\equiv bc'\mod m',$$ and the latter is equivalent to $ a\equiv b\mod m'$, since $c'$ is a unit $\bmod m'$.