Proving that $ka \equiv kb \pmod{m} \iff a \equiv b \pmod{m/\gcd(k,m)}$ I'm having some trouble proving the following proposition:

Let $m \in \mathbb N$ and $a,b,k \in \mathbb Z$, then:
$$ka \equiv kb \pmod{m} \iff a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$$

I began by trying to prove that $a \equiv b \pmod{\frac{m}{\gcd(k,m)}} \implies ka \equiv kb \pmod{m}$ but I got stuck with:
$$a\gcd(k,m) \equiv b \gcd(k,m) \pmod{n}$$
Then I also tried to prove that $ka \equiv kb \pmod{m} \implies a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$ But I also was not able to conclude anything. This is my first time learning modular arithmetic and I'm still confused with the concepts and have no intuition with this at all, this is perhaps why I'm having some trouble solving these types of questions. How can I prove this?
 A: Let $d:=\gcd(m,k)$.
If $\frac{m}{d}\mid a-b$ then $a-b=l(\frac{m}{d})$ for some $l\in\mathbb{Z}$ and so $$k(a-b)=\underbrace{l\left(\frac{k}{d}\right)}_{\in\mathbb{Z}} m.$$
This proves $m\mid k(a-b)$.
Conversely, if $m\mid k(a-b)$ then $k(a-b)=nm$ for some $n\in\mathbb{Z}$ and so
$$\frac{k}{d}(a-b)=n\cdot\frac{m}{d}.$$
Now note that $k/d$ and $m/d$ are coprime. Can you conclude from here?
A: Lemma. Let $k,m\in\mathbb N$ and $n\in\mathbb N_0$. Then $mn \equiv 0\pmod k$ is equivalent to $\operatorname{gcd}(k,m)n \equiv 0\pmod k$.
Proof. The direction $\impliedby$ is clear. For $\implies$, write $m=v_m\operatorname{gcd}(k,m)$, $k=v_k\operatorname{gcd}(k,m)$ and $mn = Ck$ for some $v_m, v_k\in\mathbb N$, $C\in\mathbb N_0$.
Then $$v_m\operatorname{gcd}(k,m) n = mn=C v_k \operatorname{gcd}(k,m),$$ so $$n=\frac{C}{v_m} v_k,$$ which, since $v_m$ and $v_k$ are co-prime by definition of GCD, implies that $C$ is divisible by $v_m$ (exercise: fully formulate this argument*).
Hence $$\operatorname{gcd}(k,m)\cdot n=\frac{C}{v_m} k \equiv 0\pmod k.$$
$\square$

Now assume that $ka\equiv kb\pmod m$, then WLOG $ka = kb + m n$ for some $n\in\mathbb N_0$ so that $$a=b+\frac{mn}k=b+\frac{m}{\operatorname{gcd}(k,m)}\frac{n\operatorname{gcd}(k,m)}k,$$ and the Lemma can be used to conclude since $\frac{mn}k\in\mathbb Z\implies \frac{n\operatorname{gcd}(k,m)}k \in\mathbb Z$.

The other direction is easier: If $$a=b+\frac{m n}{\operatorname{gcd}(k,m)}$$ for some $n\in\mathbb Z$, then $$ka=kb+m\frac{nk}{\operatorname{gcd}(k,m)}$$ and you can conclude with $\frac{nk}{\operatorname{gcd}(k,m)}\in\mathbb N$.

* In fact, my current formal proof would rely on the fundamental Theorem of arithmetic but I am convinced that there is a much easier way to show this.
