Prove that if $b = dk$ where $gcd(m, a) = d$, there are $d$ solutions to $ax \equiv b \mod m$ I know that there exists at least one solution, because
$ax \equiv b \mod m \implies ax - b = qm$
Rearranging terms gives
$ax - qm = b$, and since $d | a$ and $d | m$, so $d | b$ it can be said that $b \equiv 0 \mod d$.
I implemented Euclid's extended algorithm and have been able to experimentally verify that the claim holds, but I do not see a pattern or how I can begin to show there are exactly $d$ solutions.
def euclid_extended(x, y, i=0):
  if y == 0:
    print("iteration {0} returns ({1}, {2}, {3}) - base case hit with ({4}, {5})".format(i, x, 1, 0, x, y))
    return (x, 1, 0)
  else:
    (d, a, b) = euclid_extended(y, x % y, i + 1)
    print("iteration {0}. ({4}, {5}) => ({1}, {2}, {3})".format(i, d, b, a - b * (x//y), x, y))
    return (d, b, a - b * (x//y))
 A: Case 1: $\gcd (m,a) = 1; b = 1$ then
$ax \equiv 1 \mod m$ has exactly one solution modulo $m$.
If $ax \equiv ay \equiv 1 mod m$ then $m$ divides $a(x-y)$ and as $m$ and $a$ are relatively prime and have no factors in common, $m$ divides $x-y$ and $x \equiv y \mod m$. So $x \equiv y \mod m$ and $x$ is unique solution.  If it exists.
As $\gcd(m,a) =1$ there are $ax + ym = 1$ and ... $ax \equiv 1 \mod m$.
Case 2: $\gcd(m,a) = 1$ $b = k$.
Solve for $ay \equiv 1 \mod m$.  Let $x = ky$.  That is clearly a solution.
If $aw \equiv k \mod m$ is another solution then $aw \equiv ax \mod m$ and as $\gcd(m,a)=1$ and $a$ and $m$ have no factors in common then $w \equiv x \mod m$.
Case 3: $\gcd(m,a) = d$ $b = dk$.
Let $m' = m/d$ and $a' = a/d$.  Note: $\gcd(a',m') = 1$ (else that'd be a common divisor of $m$ and $d$ and $d*\gcd(a',m')$ would be a common divisor larger than the greatest common divisor.)
Then $ax \equiv b \mod m \implies ax - b = a'dx - dk$ is divisible by $m=m'd$. So $a'x - k$ is divisible by $m'$ or $a'x \equiv k \mod m'$ which has exactly one solution.
Call that solution $g$. Any solution $x$ must be so that $x \equiv g \mod m'$.
There are precisely $d$ such $x$, namely $x = g + jm'; 0 \le j < d$.
A: The linear congruence $ax \equiv b \mod m$ has a solution $x'$ since $(a,m) = d | b$ and there exists $p,q$ such that $ap -mq = d$.
Note that there exists $j$ such that $b = jd$ and $a(pj)-m(qj) = jd = b$, implying that the solution is $x' = pj$.  
It is easy to show all solutions must be of the form
$$x = x' + t \frac{m}{d}$$
with $t = 0, \pm1, \pm 2, \ldots.$
The $d$ solutions $x', x' + \frac{m}{d}, x' + 2\frac{m}{d}, \ldots, x' + (d-1)\frac{m}{d}, $ are mutually incongruent modulo  $m$ since the difference between any two is less than $m$. If $x'' = x' + p \frac{m}{d}$ is any other solution then Euclid's division lemma gives  $p = qd + r$ with $0 \leqslant r < d$ and $x'' = x' + (qd +r)\frac{m}{d} \equiv x' + r \frac{m}{d}.$  Therefore, there are $d$ mutually incongruent solutions modulo $m$.
