The number of solutions in a linear congruence.

Question

Why is the number of solutions in a linear congruence $ax\equiv b(mod m)$ equal to the $gcd(a,m)$ such that $gcd(a,m)$ divides $b$?

Answer 1

Let $\ d = \gcd(A,M)\,$ and $\, a,b,m = [A,B,M]/d = A/d,\,B/d,\,M/d.\ $ Then

$$\begin{align} A x \equiv&\ B\pmod{\!M}\\ \iff\ Ax\ -&\ B\ =\ j M,\quad\, {\rm for\ some}\ \ j\in\Bbb Z\\ \iff\ ax\,\ -&\ b\,\ =\,\ j\, m,\quad {\rm for\ some}\ \ j\in\Bbb Z,\, \text{ by scaling by $d$ or $d^{-1}$} \\ \iff\,\ ax\equiv&\ b\,\ \pmod{\!m}\\ \iff\,\ \ \ x\equiv&\: b/a\!\!\!\!\pmod{\!m}\quad\text{[note $a^{-1}$ exists by $\,\gcd(a,m)=1$]} \end{align}$$

The root $\,x\equiv b/a\pmod{\!m}\,$ lifts to $\,\color{#c00}d\,$ roots $\bmod \color{#c00}{d}m = M\,$ since

$$\begin{align} \bmod{dm}\!:\ \ b/a + jm\equiv&\ b/a + km\\ \iff\qquad\ \ (j-k)m\equiv&\ 0\\ \iff\ md\mid (j-k)m\quad &\\ \iff\ d\ \,\mid\,\ j-k\qquad\ \ \ &\\ \iff\ \ j\equiv k\pmod{\!d} \end{align}\qquad\qquad\qquad\qquad$$

Thus choosing normal reps $\,j=0,1,2,\ldots\,d\!-\!1\,$ yields precisely $\color{#c00}d$ roots $\bmod M,\,$ namely

$$ \{ b/a + j\, m\ : \ j = 0,1,2,\ldots,d\!-\!1\}\qquad\qquad\qquad\quad $$