[proofplan]
We reduce the general congruence to one with coprime coefficient and modulus, where the extended Euclidean algorithm gives a unique solution. The key facts are: (i) solubility reduces to $d \mid b$ because $ax - my = b$ forces $d \mid b$; (ii) after dividing through by $d$ the reduced congruence $(a/d) x \equiv (b/d) \pmod{m/d}$ has $\gcd(a/d, m/d) = 1$, hence a unique solution modulo $m/d$; (iii) lifting modulo $m$ gives exactly $d$ solutions, namely the $d$ residue classes modulo $m$ that contain the unique class modulo $m/d$.
[/proofplan]
[step:Rule out solutions when $d \nmid b$]
Suppose $x \in \mathbb{Z}$ satisfies $ax \equiv b \pmod{m}$. By definition of congruence there exists $y \in \mathbb{Z}$ with
\begin{align*}
ax - my = b.
\end{align*}
Since $d = \gcd(a, m)$, we have $d \mid a$ and $d \mid m$, so $d \mid ax - my = b$. Hence $d \mid b$ is necessary for any solution to exist. Equivalently, if $d \nmid b$, the congruence has no solution.
[/step]
[step:Reduce to a coprime congruence modulo $m/d$ when $d \mid b$]
Assume $d \mid b$. Write
\begin{align*}
a = d \cdot a', \quad b = d \cdot b', \quad m = d \cdot m',
\end{align*}
where $a', b', m' \in \mathbb{Z}$ and $m' \ge 1$. By the definition of $\gcd$, we have $\gcd(a', m') = 1$: if some prime $\pi$ divided both $a'$ and $m'$, then $d\pi \mid \gcd(a, m) = d$, contradicting $\pi \ge 2$.
We claim the congruence $ax \equiv b \pmod m$ is equivalent to
\begin{align*}
a' x \equiv b' \pmod{m'}. \tag{$*$}
\end{align*}
Indeed, for any $x, y \in \mathbb{Z}$:
\begin{align*}
ax - b = my \iff d(a'x - b') = d m' y \iff a' x - b' = m' y,
\end{align*}
where the cancellation of $d$ uses $d \ne 0$. The first equation says $ax \equiv b \pmod m$; the last says $a'x \equiv b' \pmod{m'}$. Hence the two congruences have the same integer solutions $x$.
[guided]
The divisibility $d \mid b$ is the exact condition needed to carry out the division. Without it, $b/d$ is not an integer, and the equation $a' x \equiv b' \pmod{m'}$ would involve a non-integer right-hand side — not a well-formed congruence.
Why is $\gcd(a', m') = 1$ the crucial property? A classical result — which we shall invoke in the next step — states that when the coefficient and modulus are coprime, the linear congruence is uniquely soluble. This is what unlocks an explicit count of solutions. The division by $d$ is thus not mere cosmetic simplification but the move that converts a degenerate coefficient to an invertible one.
[/guided]
[/step]
[step:Solve the coprime congruence via the extended Euclidean algorithm]
We invoke the [Linear Congruence with Coprime Modulus](/theorems/???) result: if $\gcd(a', m') = 1$, the congruence $a' x \equiv b' \pmod{m'}$ has a unique solution in $\mathbb{Z}/m'\mathbb{Z}$. The hypothesis $\gcd(a', m') = 1$ was verified in the previous step.
Concretely, the extended Euclidean algorithm produces $u, v \in \mathbb{Z}$ with
\begin{align*}
u \cdot a' + v \cdot m' = 1,
\end{align*}
so $u \cdot a' \equiv 1 \pmod{m'}$, i.e., $u$ is the multiplicative inverse of $a'$ in $(\mathbb{Z}/m'\mathbb{Z})^\times$. Setting
\begin{align*}
x_0 := u \cdot b' \bmod m',
\end{align*}
we obtain $a' x_0 \equiv a' u b' \equiv b' \pmod{m'}$. Uniqueness modulo $m'$ follows from cancellation: if $a' x_1 \equiv a' x_2 \pmod{m'}$, multiplying by $u$ gives $x_1 \equiv x_2 \pmod{m'}$.
Hence the solutions of $(*)$ form the single residue class
\begin{align*}
\{x \in \mathbb{Z} : x \equiv x_0 \pmod{m'}\} = \{x_0 + k m' : k \in \mathbb{Z}\}.
\end{align*}
[/step]
[step:Lift the unique solution modulo $m/d$ to exactly $d$ solutions modulo $m$]
By the equivalence established in Step 2, the integer solutions of $ax \equiv b \pmod m$ coincide with the integer solutions of $(*)$, namely $\{x_0 + k m' : k \in \mathbb{Z}\}$ where $m' = m/d$. We project this set to $\mathbb{Z}/m\mathbb{Z}$.
Two integers $x_0 + k_1 m'$ and $x_0 + k_2 m'$ represent the same class modulo $m$ if and only if
\begin{align*}
(k_1 - k_2) m' \equiv 0 \pmod m \iff (k_1 - k_2) m' = m \ell \text{ for some } \ell \in \mathbb{Z} \iff (k_1 - k_2) = d \ell,
\end{align*}
where the last equivalence divides both sides by $m' = m/d > 0$. Thus the set $\{x_0 + k m' : k \in \mathbb{Z}\}$ partitions into exactly $d$ residue classes modulo $m$, represented by
\begin{align*}
\{x_0 + k m' \bmod m : k = 0, 1, \dots, d - 1\}.
\end{align*}
Hence the solution set in $\mathbb{Z}/m\mathbb{Z}$ has cardinality exactly $d$.
[guided]
The lifting step answers the question: given that the solutions form a full residue class modulo $m' = m/d$, how many residue classes modulo $m$ does that class split into? A single class modulo $m'$ contains every integer $\equiv x_0 \pmod{m'}$. When we refine the relation to congruence modulo $m = d m'$, each class mod $m'$ splits into $m/m' = d$ classes modulo $m$ — one for each "offset" $0, m', 2m', \dots, (d-1) m'$.
We can verify this by a direct count. The set $\{x_0 + k m' : k = 0, 1, \dots, d - 1\}$ has $d$ elements. They are pairwise distinct modulo $m$: if $x_0 + k_1 m' \equiv x_0 + k_2 m' \pmod m$ with $0 \le k_1, k_2 \le d - 1$, then $(k_1 - k_2) m' \equiv 0 \pmod m$, hence $d \mid k_1 - k_2$, and with $|k_1 - k_2| < d$ this forces $k_1 = k_2$. Every integer congruent to $x_0$ modulo $m'$ lies in one of these $d$ classes by taking $k$ as the remainder of its $m'$-offset modulo $d$.
In the special case $d = 1$: $m' = m$, $\gcd(a, m) = 1$, and the equation has the unique solution $x_0 \bmod m$. At the other extreme $d = m$: $a \equiv 0 \pmod m$, and either $b \equiv 0$ (all $m$ classes are solutions) or $b \not\equiv 0$ (no solutions). Both extremes match the formula.
[/guided]
[/step]
[step:Assemble the two cases into the final statement]
Collecting the cases:
- If $d \nmid b$, Step 1 shows there are $0$ solutions in $\mathbb{Z}/m\mathbb{Z}$.
- If $d \mid b$, Steps 2–4 show there are exactly $d$ solutions in $\mathbb{Z}/m\mathbb{Z}$, given explicitly by $\{x_0 + k(m/d) \bmod m : k = 0, 1, \dots, d - 1\}$ for any particular solution $x_0$.
Both claims (i) and (ii) of the theorem follow. This completes the proof.
[/step]
