Prove if $\gcd(a,n) = g$ there are exactly $g$ solutions between $0$ and $n$ to $ax \equiv b \pmod{n}$ if $\gcd(a, n)\mid b$ I have already proved that there is a solution, and I have seen many proofs that simply state that there are obviously $\gcd(a, n)$ solutions of the form:
$$x_0, x_0 + \frac{n}{g}, x_0 + \frac{2n}{g}, \dots , x_0 + \frac{(g-1)n}{g}$$
This is not obvious to me though, and have no idea how they arrive at this conclusion.
 A: Since you proved a solution $x_0$ exists (probably by applying Bezout identity) it's easy to see that any other solution is of the following form 
$$y=x_0+t\frac{n}{g}, t\in\mathbb{Z}$$
Indeed, from $ay\equiv b \pmod{n}$ and $ax_0\equiv b \pmod{n}$ we have
$$a(y-x_0)\equiv 0 \pmod{n} \Rightarrow 
n \mid a(y-x_0) \Rightarrow\\
\exists q\in\mathbb{Z}: a(y-x_0)=nq \overset{\gcd(a,n)=g}{\Rightarrow}\\
a_1g(y-x_0)=n_1gq \Rightarrow 
a_1(y-x_0)=n_1q \overset{\gcd(a_1,n_1)=1}{\Rightarrow}\\
n_1 \mid y-x_0 \Rightarrow 
y=x_0+tn_1, t\in\mathbb{Z} \Rightarrow \\
y=x_0+t\frac{n}{g}$$

So, obviously each $x_0 + \frac{n}{g}, x_0 + \frac{2n}{g}, \dots , x_0 + \frac{(g-1)n}{g}$ is also a solution. The remaining part is to show that there are exactly $g$ solutions between $0$ and $n$. 
From $0< y \leq n$ ($y=0$ is not a solution, otherwise $n \mid b$) we have
$$-x_0< t\frac{n}{g} \leq n-x_0 \iff -gx_0< tn\leq gn-gx_0 \iff \\
-gx_0< t_{\min}\cdot n \leq t\cdot n  \leq gn-gx_0 \iff \\
0\leq (t - t_{\min})n < gn-gx_0+gx_0=gn \iff \\
0\leq t - t_{\min} < g$$
So, regardless of $t_{\min}$ (e.g. $t_{\min}=0$), this leads to $g$ solutions maximum.
A: The equation $ax\equiv b\pmod{n}$, knowing that $g=\gcd(a,n)\mid b$, becomes
$$
gAx-gB=kgN
$$
where $a=gA$, $n=gN$, $b=gB$. This in turn becomes
$$
Ax-B=kN
$$
or $Ax\equiv B\pmod{N}$. Note that $\gcd(A,N)=1$, so $A$ is invertible modulo $N$. Thus there exists $C$ with $AC\equiv 1\pmod{N}$ and therefore the equation becomes $x\equiv BC\pmod{N}$. There is a single $x_0$, with $0\le x_0<N$ satisfying this condition.
Clearly, $x_0$ is also a solution to $ax\equiv b\pmod{N}$.
Similarly, there is a single solution $x_1$ satisfying $N\le x_1<2N$, and, more generally, a single solution $x_k$ satisfying $kN\le x_k<(k+1)N$, namely
$$
x_k=x_0+kN
$$
Note that, for $0\le h<g$ and $0\le k<g$, $x_h\not\equiv x_k\pmod{n}$. Thus we have found exactly $g$ solutions $x_0,x_1,\dots,x_{g-1}$.
Each solution to $ax\equiv b\pmod{n}$ is congruent to one of these modulo $n$.
