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$

Question

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.

Answer 1

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$.

Answer 2

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.