$\gcd(a,n)=d$ and $s,t$ solutions to $ax\equiv b \pmod{n}$ then $s\equiv t\pmod{n/d}.$

Question

If $\gcd(a,n)=d$ and $s,t$ are each solutions to $ax\equiv b\pmod{n}$ then $s\equiv t \pmod{n/d}$.

As $d\mid a$ say $a=dm$ and as $s,t$ are each solutions, $as\equiv at\pmod{n}$ so $$a(s-t)=nk \text{ for some } k \in \mathbb{Z}\\ \Rightarrow s-t=(nk)/a\\ \Rightarrow s-t=\frac{n}{d}\cdot\frac{k}{m}.$$

How can I show that $m\mid k$ so then $k/m\in\mathbb{Z}$?

Answer 1

I would simply do: $$as \equiv at \pmod n \implies \frac{a}{d}s \equiv \frac{a}{d}t \pmod {\frac{n}{d}} \implies \frac{n}{d}\mid\frac{a}{d}(s-t) \implies \frac{n}{d} \mid s-t,$$ the last implication because $\gcd\left(\frac{a}{d},\frac{n}{d}\right)=1$.

Answer 2

As you have said, there exists some integer $k$ such that $$a(s-t)=nk$$ Therefore $$\frac ad(s-t)=k\frac nd$$

Since $a/d$ is integer, $s-t$ divides $n/d$.