Number of solutions to a linear congruence equation Consider
$$ ax \equiv c \mod m $$
If there is a solution, prove that there are exactly $\gcd(a, m)$ distinct solutions modulo $m$.

I can prove that there are at least that many, because if $x_0 < m$ is a solution, $x=x_0 + \frac{k \cdot m}{\gcd(a,m)}$ for any $k\in \mathbb{Z}$ is also a solution. Thus there are $\gcd(a, m)$ solutions modulo $m$ for $0 \le k \le \gcd(a,m)-1$.
But how can I prove these are the only solutions, i.e. there is no solution of other forms?
 A: $$ax\equiv c\pmod{m}\tag{1}$$
First consider $\gcd(a,m)=1$. Then when $x$ runs through a complete residue system modulo $m$, so does $ax$. Hence $ax$ is congruent to $c$ for one and only one value of $x$ from the  complete residue system. So there is just one solution to the congruence $(1)$ when $\gcd(a,m)=1$.
Now  let $\gcd(a,m)=d>1$. For any solution to $(1)$ we need $d\mid c$, otherwise there are no solutions. (To see this write $ax=c+mr$, then since this is equivalent to $a_0dx=c+m_0dr$ we must have $c=c_0d$.)
If $d\mid c$ then we can rewrite $(1)$ as
$$a_0dx\equiv c_0d\pmod{m_0d}$$
which on dividing through by $d$ gives the equivalent congruence to $(1)$:
$$a_0x\equiv c_0\pmod{m_0}\tag{2}$$
where $\gcd(a_0,m_0)=1$, meaning $(2)$ will have one solution modulo $m_0$.
Now if $x_0$ is the least nonnegative residue of $(2)$, then each $x$ that is a solution to $(2)$ satisfies
$$x\equiv x_0\pmod{m_0}\tag{3}$$
But modulo $m$ we must look at where the least nonnegative residues from $0$, $1$, $2,\dotsc,m-1$ appear as solutions to $(3)$, this then gives us $d$ solutions of $(2)$:
$$x_0,\, x_0+m_0,\, x_0+2m_0,\, \dotsc, x_0+(d-1)m_1$$
and these are all the possible $d$ amount of solutions of $(1)$.
To get it into the form you have, just note $m=m_0d$ so $m_0=\frac{m}{d}=\frac{m}{\gcd(a,m)}$
$$x_0,\, x_0+\frac{m}{\gcd(a,m)},\, x_0+\frac{2m}{\gcd(a,m)},\, \dotsc, x_0+\frac{(d-1)m}{\gcd(a,m)}$$
