# $d = \gcd(c,m),\ ac≡bc\pmod{\! m}\Rightarrow a≡b\pmod {\!m/d}\$ [Congruence Division Rule]

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})\!\iff m\mid cn.\$$ Now apply

Lemma $$\ \ m\mid cn\iff m/(m,c)\mid n. \ \$$ Proof $$\,$$ Cancelling $$\,d = (m,c)\,$$ yields

$$m/d \mid (c/d)n\,\Rightarrow\, m/d\mid n\,$$ by Euclid's Lemma  & $$\,(m/d,c/d) \overset{\rm\color{#90f}{D}}= (m,c)/d = 1\ \$$ QED

Or: $$\,\ 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$$

where we used $$\,\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) - true here: $$\,d\!=\!(c,m)\mid c\mid bc$$

It may be clearer done in two steps:  first cancel $$\,d = (c,m)\,$$ $$\rm\color{#c00}{everywhere}$$ to reduce to the case of $$\rm\color{#0a0}{coprime}$$ $$\,\bar c,\bar m = c/d, m/d,\,$$ then cancel $$\,\bar c\,$$ by scaling by $$\,\bar c^{-1}$$ (exists $$\!\bmod \bar m$$ by $$\,\bar c\,$$ $$\rm\color{#0a0}{coprime}$$ to $$\,\bar m)$$

\begin{align} ac &\equiv bc\!\!\pmod{m}\\ \Rightarrow\ \ a\bar c&\equiv b\bar c\!\!\!\pmod{\bar m}\ \ \ {\rm via\ cancel\ } d = (c,m)\ \,\&\,\ \rm Lemma\\ \Rightarrow\ \ \ \ a &\equiv b\pmod{\bar m}\ {\rm\ \ by\ scaling\ by\ }\, \bar c^{-1} \end{align}

Lemma $$\,\ d\mid c,m,\,\ ac\equiv bc\pmod{\!m}\,\Rightarrow\, {ac/\color{#c00}d \equiv bc/\color{#c00}d\pmod{\!m/\color{#c00}d}}\$$ [cancel $$\,d\ \rm\color{#c00}{everywhere}$$]

\begin{align}{\bf Proof}\ \ \ \text{Cancel \,d\, from} \ ac = bc\! +\!km\Rightarrow\, ac/d &= bc/d \,+\, k\:m/d\\ \Rightarrow\, ac/d &\equiv bc/d\!\!\!\pmod{\!m/d} \\ {\rm i.e.}\ \ \ \ a\bar c\, &\equiv\, b\bar c\,\pmod{\!\bar m}\end{align}

Remark $$\$$ The (two-step) cancellation has a natural view as modular fraction reduction as explained in the remark in my other answer.

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.