# 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

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{#c00}{\,\ U}}\iff\! m\mid (cn,mn)\!\overset{\rm\color{#0a0}{D}}=\! (c,m)n\!\iff\! \smash[b]{\frac{m}{\underbrace{(c,m)}_{\large d}}}\mid n = a\!-\!b$$

where $\,\rm\color{#c00}{U} =$ gcd Universal property  and  $\rm\color{#0a0}{D}$ = gcd Distributive law.

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}$ 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.