Let a,b,m,k be integers such that m$\ge$2 and k $\neq$ 0. Let d = gcd(k,m) If a is congruent to b (mod m) and k is a common divisor of a and b...

Question

Let $a,b,m,k$ be integers such that $m\geq 2$ and $k \neq 0$. Let $d = gcd(k,m)$

if $a \equiv b (\mod m$) and $k$ is a common divisor of $a$ and $b$, then $(a/k)\equiv b/k \mod (m/d)$

I really don't know where to go with this. I've tried a lot

Answer 1

It is given that $d =\gcd(m , k)$ So, by definition, $d|k$ and $d|m$.

By the definition of congruency and as given: $m|(a-b)$, and as $\frac{k}{d}$ is an known integer, the statement $m|[(a-b)\frac{k}{kd}]$ would also be true.

As $\frac{m}{d}$ is an integer, it is easy to see that $\frac{m}{d}|[(a-b)\frac{k}{kd}]$.

Noting that $\gcd(\frac{m}{d} ,\frac{k}{d}) = 1$, the division statement can be reduced to $\frac{m}{d}|(\frac{a}{k}-\frac{b}{k})$, which can be restated as $ \frac{a}{k}\equiv\frac{b}{k}\pmod{\frac{m}{d}} $.

Answer 2

Hint: Look at $$\frac{a/k-b/k}{m/d}\\ = \frac{d(a-b)}{mk}$$ If you can prove this is an integer, then you can prove your original expression. Try to show that $d|k$.