Combining GCD and congruences

Question

Let $a, b, m, k \in \Bbb Z$ such that $m\ge2$ and $k\not=0$. Let $d=\gcd(k,m)$. Prove that if $a\equiv b\pmod m$ and $k$ is a common divisor of $a$ and $b$, then ${\frac ak}\equiv {\frac bk}\pmod {\frac md}$.

Any ideas? I'm really stumped.

Answer 1

Clearly, $\displaystyle {\frac ad}\equiv {\frac bd}\pmod {\frac md}$.

Now, write $k=dk'$ and $m=dm'$, with $\gcd(k',m')=1$.

Then $\displaystyle \frac{ak'}{k}=\frac{ak'}{dk'}=\frac{a}{d} \equiv \frac{b}{d} = \frac{bk'}{dk'} = \frac{bk'}{k}\pmod {m'}$.

Finally, $\gcd(k',m')=1$ allows us to cancel $k'$ on both sides of $\displaystyle \frac{ak'}{k} \equiv \frac{bk'}{k}\pmod {m'}$.

Answer 2

Since $k$ is a common divisor of $a$ and $b$, therefore $\exists \, p,q \in \mathbb{Z}$ such that $$a=pk \qquad b=qk$$ Then $a \equiv b \pmod{m}$ implies that $m | (a-b)$, hence $m | k(p-q)$. Thus $m/d$ divides $k/d(p-q)$. But $\gcd(\frac{m}{d}, \frac{k}{d})=1$. Therefore $$m/d \quad \text{ divides } \quad (p-q).$$ This gives us $$p \equiv q \pmod{\frac{m}{d}}.$$ Now multiply both sides by $k$ and the congruence still holds, giving us $$a \equiv b \pmod{\frac{m}{d}}.$$