3
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you for taking the time to help me!! How can you say that $x$ and $y$ are co-prime? $\endgroup$ – user342661 Aug 6 '16 at 2:46
  • 2
    $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Aug 6 '16 at 2:51
  • $\begingroup$ You are welcome. $\endgroup$ – астон вілла олоф мэллбэрг Aug 6 '16 at 4:16
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy