Prove Proposition (3.16).
Proposition (3.16):
The linear congruence $ax ≡ b \pmod n$ has exactly $g$ incongruent solutions modulo $n$, provided $g \mid b$ where $g= \gcd (a, n)$.
We first prove a lemma which we'll use in the proof.
Lemma (A): If integer $x$ runs through the complete residue system $\{0,1, \ldots, n-1\}$ for modulo $n$, then so does $ax \pmod n$, provided $\gcd(a,b)=1$.
That is, $ax \pmod n$ takes on one and only one value in the residue system $\{0,1, \ldots, n-1\}$.
Proof: Consider two elements $x$ and $y$ from the residue system. If $ax \equiv ay \pmod n$, then this means $ax -ay = a(x-y) = kn$, for some integer $k$. Since $\gcd(a,n)=1$, that is, $a$ and $n$ share no common factors, then it must be that $n$ divides $(x-y)$. That is $x=y \pmod n$, which means $x$ and $y$ are the same element. And so $ax \pmod n$ runs through the residue system without repetition as $x$ runs through the residue system.
Another way of saying this is that if $ax \equiv r \pmod n$, then no other element of the residue system $y \ne x$ results in $ay \equiv r \pmod n$.
Note: this online solution helped with this proof.
We consider two cases, $g=\gcd(a,n) =1$ and $g=\gcd(a,n)>1$.
Case $g=1$
Since $g=\gcd(a,n)=1$, Lemma A tells us that as $x$ runs through the complete residue system $\{0, 1, \ldots, n-1\}$ modulo $n$, then so does $ax \pmod n$. That is $ax \equiv b$ for only one value of $x$. Therefore the number of incongruent solutions for $ax \equiv b \pmod n$ is $g$.
Case $g>1$
We simplify the linear congruence from $ax \equiv b \pmod n$ to
$$ \begin{align} a_0 x & \equiv b_0 \pmod {\frac{n}{\gcd(n,g)}} \quad \quad \text{Proposition 3.10}\\ \\ & \equiv b_0 \pmod{ \frac{n}{\gcd(g n_0,g)} } \\ \\ & \equiv b_0 \pmod{ \frac{n}{g}} \\ \\ a_0 x & \equiv b_0 \pmod{n_0} \end{align}$$
where $ga_0 = a$, $g b_0 = b$ and $g n_0 = n$.
By definition $\gcd(n_0, a_0)=1$ and so the linear congruence $a_0 x \equiv b_0 \pmod{n_0} $ has one incongruent solution, by Lemma A above.
If $x_0$ is the smallest non-negative solution, then the congruent solutions in modulo $n_0$ are
$$ x_0 + (n_0)t $$
for integer $t$.
These are incongruent in modulo $n$ when
$$ x_0 + (n_0)t < n $$
That is
$$\begin{align} t & < \frac{n - x_0}{n_0} \\ \\ & = \frac{n}{n_0} - \frac{x_0}{n_0} \\ \\ & = g - \frac{x_0}{n_0}\end{align}$$
Here $\frac{x_0}{n_0} < 1$ because $x_0$ is a residue in modulo $n_0$, and so $x_0 < n_0$. This means the largest integer $t$ is $g-1$.
So $t$ ranges from 0 to $g-1$, that is, takes on $g$ values. This means there are $g$ incongruent solutions $ x_0 + (n_0)t $ for the linear congruence $ax \equiv b \pmod n$.
In both cases we have shown there are exactly $g=\gcd(a,n)$ incongruent solutions to the linear congruence $ax \equiv b \pmod n$, provided $g \mid b$.