# If $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, show that $a≡b$ $\mod \frac{m}{d}$

How would you show that if $ac≡bc$ $\mod m$ and $\gcd(c,m)=d$, then $a≡b$ $\mod \frac{m}{d}$?

Any help would be much appreciated!

You have marked this under proof writing. So I will attempt a model proof.

So $ac \equiv bc \mod m$, which means that $m | ac-bc$, and hence $m | c(a-b)$. Hence, $c(a-b)=km$ for some integer $k$. Now, Given that $\gcd(c,m) =d$, it follows that $c=xd$ and $m=yd$ for some co-prime integers $x$ and $y$. Hence, $$c(a-b) = km \implies xd(a-b) = kyd \implies x(a-b) = ky$$ Note that $x | ky$ from the above. Now, because $x$ is co-prime to $y$, it follows that $x |k$ and hence $\frac{k}{x}$ is an integer. Now, $$(a-b) = \frac{k}{x}y$$ and hence $a-b$ is a multiple of $y$. Hence $a \equiv b \mod y$. But $y = \frac{m}{d}$, hence $a \equiv b \mod \dfrac{m}{d}$.

• Thank you for taking the time to help me!! How can you say that $x$ and $y$ are co-prime? – user342661 Aug 6 '16 at 2:46
• Suppose $x$ and $y$ are not co-prime. Then let $x = gw$ and $y=gz$, where $g \neq 1$. Then note that $c=xd=gwd$,and $m = yd = gzd$. Note that $gd$ divides both $x$ and $y$ and is greater than $d$ because $g>1$. This contradicts the fact that $d$ is the gcd of $m$ and $c$. Hence $x$ and $y$ are co-prime. – астон вілла олоф мэллбэрг Aug 6 '16 at 2:51
• You are welcome. – астон вілла олоф мэллбэрг Aug 6 '16 at 4:16

Assuming integers for all variables, and $c' = c/d$, $m' = m/d$ :

\begin{align} ac \equiv bc \pmod m &\iff \exists k ~~ ac - bc = km \\ % &\iff \exists k ~~ ac'd - bc'd \equiv km \\ % &\iff \exists k ~~ a - b \equiv (k/c')(m/d) \end{align}

So we have to establish that $k / c'$ is an integer. From $\gcd(c, m) = d$ we can infer $\gcd(c', m') = 1$, so

$$ac - bc = km$$ $$ac'd - bc'd \equiv k(m'd)$$ $$c'(a - b) = km'$$

So $c'$ divides $k$, so $k/c'$ is an integer.

$$\exists j ~ a - b = j(m/d)$$ $$a \equiv b \pmod {m/d}$$

By definition $$\ ac\equiv bc\pmod{\! m}\!\iff\! m\mid ac\!-\!bc = c(\overbrace{a\!-\!b}^{\large n}).\$$ Applying basic gcd laws

$$m\mid cn\!\iff\! m\mid cn,mn\!\!\!\overset{\rm\color{#0a0}{\,\ U}}\iff\! \color{#c00}m\mid (cn,mn)\!\overset{\rm\color{#90f}{D}}=\! (c,m)n\! =\! \color{#c00}dn\!\iff\! {\color{#c00}{\frac{m}{d}}}\,{\Large \mid}\, n \qquad$$

where we've employed $$\,\rm\color{#0a0}{U} =$$ gcd Universal property  and  $$\rm\color{#90f}{D}$$ = gcd Distributive law.

Remark  As I explain carefully here, in fractional language this can be written as

$$ac\equiv bc\!\!\!\!\pmod{\!m}\iff a\equiv \dfrac{bc}c\!\!\!\!\pmod{\!m}\equiv\!\!\!\!\!\!\!\!\underbrace{\dfrac{bc/\color{#c00}d}{c/\color{#c00}d}\equiv b\!\!\!\pmod{\!m/\color{#c00}d}}_{\textstyle {\rm cancel}\ \color{#c00}d\!=\!(c,m)\ \textit everywhere}\qquad$$

The common divisor $$\,\color{#c00}d = (c,m)\,$$ must be cancelled everywhere (top, bottom and modulus), leaving the new denominator $$\,c/d\,$$ coprime to the new modulus $$\,m/d,\,$$ thus invertible so cancellable. More generally, the fraction exists $$\iff d\,$$ divides the top (numerator) - always true in this case.

By definition, $ac\equiv bc \pmod{m}$ means that there exists a $k\in\mathbb{Z}$ such that $ac=bc+km$. If $d=\gcd(c,m)$, let $c=sd$ and $m=td$ (note now that $\gcd(s,t)=1$). This means that \begin{aligned} ac &\equiv bc \pmod{m} \Longleftrightarrow \\ ac &= bc+km \Longleftrightarrow \\ asd &= bsd+ktd \Longleftrightarrow \\ as &= bs+kt, \end{aligned} so $as\equiv bs \pmod{t}$, or in other words $as\equiv bs \pmod{m/d}$. But since $\gcd(s,t)=1$ we can conclude that $a\equiv b \pmod{m/d}$, and we are done.