Number Theory proofs relating to gcd and mod How do you prove that the congruence $ax \equiv b \pmod m$ has exactly $d = (a,m)$ solutions?
I know that this proof is false but I can't come up with any counterexamples. Any ideas?
 A: Let $(a,m)>1$ and $(a,m) \mid b$.
We define:
$$d=(a,m) , a_1=\frac{a}{d}, b_1=\frac{b}{d}, m_1=\frac{m}{d}$$
Then, $ax \equiv b \pmod m$ is equivalent to $a_1 x \equiv b_1 \pmod {m_1} (1)$
As $(a_1,m_1)=1$ , (1) has exactly one solution.So,there is a solution $\xi_0$  of (1).
And as $ax \equiv b \pmod m$ is equivalent to (1),the solutions of $ax \equiv b \pmod m$ are the elements of the set:
$$[\xi]_{m_1}=\{  \xi | \xi_0 \equiv 0 \pmod {m_1}\}=\{qm_1+\xi_0 | q \in \mathbb{Z} \}$$
Now we have to check how many of them are inequivalent $\pmod m$.
We have:
$$q'm_1+\xi_0 \equiv q''m_1+\xi_0 \pmod m \Leftrightarrow q'm_1 \equiv q''m_1 \pmod {dm_1} \Leftrightarrow q' \equiv q'' \pmod d$$
So the solutions $qm_1+\xi_0$,that are inequivalent $\pmod m$ come from the values of $q$,that are inequivalent $\pmod d$.Such values of $q$ are elements of a complete system of residues modulo d,for example of this one: $ \{ 0,1, \dots , d-1 \}$.
We conclude that the $d=(a,m)$ numbers:
$$\xi_0, m_1+ \xi_0, \dots, (d-1)m_1+\xi_0$$
are inequivalent $\pmod m$ solutions of $ax \equiv b \pmod m$ and that each other solution is equivalent $\pmod m$ to one of them.
A: If $(a,m)\mid b$ then we can divide the congruence by $(a,m)$ to get $\frac{a}{(a,m)}x\equiv\frac{b}{(a,m)}$ mod $\frac{m}{(a,m)}$.
Since $(\frac{a}{(a,m)},\frac{m}{(a,m)})=\frac{(a,m)}{(a,m)}=1$ we know $\frac{a}{(a,m)}$ is a unit mod $\frac{m}{(a,m)}$, so we can divide to get 
$$x\equiv \left(\frac{a}{(a,m)}\right)^{-1}\frac{b}{(a,m)}\mod{\frac{m}{(a,m)}}.$$
Any residue mod $m'$ lifts up to $\frac{m}{m'}$ residues mod $m$, so there are $m/\hskip -0.06in \frac{m}{(a,m)}=(a,m)$ solutions.
Conversely given a solution, multiplying both sides by $\frac{m}{(a,m)}$ yields $m\mid b\frac{m}{(a,m)}\Rightarrow (a,m)\mid b$, so this condition is necessary for there to be any solution at all.
