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

If \(g | b\) then \(b = gc\). Also:

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

If \(b = a(cp) + m(cq)\), then \( b ≡ a(cp) \mod m\). Therefore, \(x = cp\). However, there may be more solutions. Let \(m = zg\) and \(a = wg\). 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 \(m = zg\) and \(a = wg\):

$$\begin{align} wg(cp - x_i) = zgf \\ w(cp - x_i) = zf \end{align}$$

This tells us that \(z | w(cp - x_i)\), which means \(z | (cp - x_i)\), because \((z, w) = 1\) (since \( (m/g,a/g) = 1 \) as you shouldn't be able to divide both \(m\) and \(a\) any further after dividing them by the gcd). Since \(z | (cp - x_i)\):

$$ x_i ≡ cp \mod z $$

This means all the solutions are \(x_i = cp + zh\) where \(h \in \mathbb{Z}\). As an 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, a=gw\) and \(m=gz\), then \(c=3, w=4\) and \(z=7\). Since \(g = a*2 + m*-1\), then \(x = cp = 3*2 = 6\). There are other solutions where:

$$ x_i ≡ 6 \mod 7 $$

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

If \(g | b\) then \(b = gc\). Also: