solution of ax ≡ b mod m (if gcd(a, m)|b)

Let \(g = (a, m)\). If \(g | b\) then \(b = gc\). Also:

$$ g = ap + mq $$$$ b = c(ap + mq) $$

If \(b = a(cp) + m(cq)\), then \( b ≡ a(cp) \bmod m\). Therefore, \(x = cp\). However, there may be more solutions. We know that \(cp\) is one solution, let \(x_i\) be another:

$$\begin{align} a(cp) &≡ b \mod m \\ a(x_i) &≡ b \mod m \end{align}$$

Which means:

$$ a(cp - x_i) ≡ 0 \mod m $$$$ a(cp - x_i) = mf $$

Since \(\frac{m}{g}\) is an integer and \(\frac{a}{g}\) is an integer:

$$\begin{gather} \left( \frac{a}{g} \right) (cp - x_i) = \left( \frac{m}{g} \right) f \\ \frac{m}{g} | \frac{a}{g}(cp - x_i) \end{gather}$$

Since \(\gcd(\frac{a}{g},\frac{m}{g})=1\):

$$\begin{gather} \frac{m}{g} | (cp - x_i) \end{gather}$$

We can rewrite \( \frac{m}{g} | (x_i - cp)\) as \( \frac{m}{g} | (x_i - cp)\). This means \(x_i = cp + \frac{m}{g} (h)\) where \(h \in \mathbb{Z}\). These means the solutions are:

$$ cp, \quad cp + \frac{m}{g}, \quad cp + 2\frac{m}{g}, \quad cp + 3\frac{m}{g}, \ldots$$

In the least residue system of modulo \(m\): \(\{ 0, 1, 2, \ldots, m-1 \}\), all the integers are unique modulo \(m\). Any integer \(\ge m\) will be congruent to an integer in the least residue system. This means \((\frac{m}{g} h)\) will be unique modulo \(m\) as long as \(0 \le h \lt g\). If \(h \ge g\), or \((\frac{m}{g} h) \ge m \), then \((\frac{m}{g} h)\) will be congruent to an integer in the least residue system.

Since \((\frac{m}{g} h)\) will be unique modulo \(m\) if \(0 \le h \lt g\), then \((cp + \frac{m}{g} h)\) will also be unique modulo \(m\) if \(0 \le h \lt g\). This means there are \(g\) unique solutions.

$$\begin{align} &\text{These solutions are incongruent: } \quad cp, &&cp + \frac{m}{g}, && cp + 2\frac{m}{g}, &&\ldots, &&cp + (g-1)\frac{m}{g} \\ &\text{These solutions are incongruent: } \quad cp + g\frac{m}{g}, &&cp + (g+1)\frac{m}{g}, && cp + (g+2)\frac{m}{g}, &&\ldots, &&cp + (2g-g)\frac{m}{g} \end{align}$$

The solutions above that are in the same row are incongruent modulo \(m\), while the solutions in the same column are congruent modulo \(m\).

Conclusion: If \([ax ≡ b \bmod m]\), \([g = (a, m)]\) and \([g|b]\), then there are \(g\) solutions of the form:

$$ x_0 + \left( \frac{m}{g} \right) h, \quad h = 0, 1, 2, \ldots, (g-1) $$

where \(x_0\) is any particular solution.

For example, let's try to solve \(8x ≡ 6 \mod 14\), where \(a=8, b=6\) and \(m=14\), so \(g\) is:

$$ (8, 14) = 2 $$

Since \( g | b\), solutions exist. If \(b=gc\), then \(c=3\). Since \(g = a*2 + m*-1\), then \(x = cp = 3*2 = 6\), which is one solution. There are other solutions where:

$$\begin{gather} x_i ≡ 6 \mod \frac{14}{2} \\ x_i ≡ 6 \mod 7 \end{gather}$$

This means \(x_i = 6 + 7h\), so \(x_i\) could be 6 and 13.