Modular and gcd proof

Question

Let $gcd(c,m)=g$

(c) Prove that $ec\equiv fc\pmod{m} \iff e\equiv f\pmod{m'} $

I'm not sure if there's a typo in the question and whether the $m'$ in the end should be $m$ or if its correct and I'm misunderstanding it.

EDIT : previous parts of the problem (I don't need proofs for these)

(a) Show that if $kc+lm=g$ then $gcd(k,l)=1$

(b) Show that if we write $m=m'g, c=c'g$, then $gcd(c',m')=1$

Answer 1

New Answer: A way to do it is to prove that $\gcd (m',c) = 1$ and then we have that $m' \mid c(e-f)$ and therefore $e \equiv f \pmod{m'}$.

Conversely, if $m' \mid e-f$, multiplying both sides by $g$, $m \mid (e-f)g$. Note that $c(e-f)$ is a multiple of $g(e-f)$ and then it follows that $m \mid $(e-f)c$.

Old Answer: If $g \neq 1$, the result if false for $m' = m$. Take $m = c = e = 2$ and $f = 3$. We have $2\cdot 2 \equiv 2\cdot 3 \pmod{2}$ but $2 \not\equiv 3 \pmod{2}$.

On the other hand, try to prove that given integers $a$, $b$, $m$, if $m \mid ab$ and $\gcd (m,a) = 1$ then $m \mid b$. This is known as Euclid's Theorem, it is going to make your problem a lot easier (considering that $m' = m$).

Answer 2

$ec \equiv fc \mod m \implies$

$ec = fc + km$ for some $k$ $\implies$

$ec' = fc' + km'$ for $c' = c/g; m' = m/g$ $\implies$

$e = f + \frac{km'}{c'}$ and as $\gcd(c',m') = 1$ we know $c' | k$ $\implies$

$e = f + \frac {k}{c'}m' \implies$

$e \equiv f \mod m'$.

===

$e \equiv f \mod m' \implies$

$e = f + km'$ for some $k$ so

$ec = fc + kcm' = fc + kc'gm' = ec + fc + kc'm \implies$

$ec \equiv fc \mod m$.

===

Note $0*c \equiv c*m'= c'*m \mod m$ but $0 \not \equiv m' \mod m$ if $g >1$, so that is definately an $m'$ and $m$ in the stating.