Proof on linear congruence solutions There's a proof in a section in my book on modular arithmetic I don't really understand.
On linear congruences:

$ax \equiv b \text{ (mod $m$)}$
Suppose that $\gcd({a,m}) = d > 1$ and $b$ is divisible by $d$. We can
  divide both sides of the linear congruence by $d$:
$\frac{a}{d}x \equiv \frac{b}{d}$ (mod $\frac{m}{d}$),
  gcd($\frac{a}{d}$, $\frac{m}{d}$) $= 1$.
This last linear congruence has exactly one solution $r \in$ 
  $\mathbb{N}[0, \frac{m}{d}-1]$. Therefore the solutions to $ax \equiv$
  $b$ (mod $m$) are $r + t\frac{m}{d}$ with $t \in \mathbb{N}[0,d-1]$.

I understand everything except the last sentence. I have an intuition on why this might be true, but how can it be proven?
 A: Let $S:\{r\}$ is a complete residue $\pmod M,$ where $0 \le r<M$.
Now let us consider $T:\{A\cdot s\}$ where $0 \le r<M$ and $(A,M)=1$ 
If $A\cdot s_i\equiv A\cdot s_j\pmod M$ where $0\le s_i<s_j<M$
$\implies M\mid A(s_i-s_j)\implies M\mid(s_i-s_j)$ 
But $M\not\mid (s_i-s_j)$ as $0<s_j-s_i<M$
So, $T$ is also a complete residue and each element of $T$ is congruent to exactly one  element of $S$.
Hence, we have exactly one solution of $A\cdot x\equiv B\pmod M$ for $(A,M)=1$ 
So, the solution is $\frac BA\pmod M=\frac BA+tM$ where $t$ is any integer.
We consider two roots to be different, if they are in-congruent $\pmod m$ 
If $\frac aA=\frac mM=d=(a,m),$
and $\frac BA+t_1M\equiv \frac BA+t_2M\pmod m\iff m\mid M(t_2-t_1)\implies t_1\equiv t_2\pmod{\frac mM}$
So, there are exactly $\frac mM=d=(a,m)$ in-congruent solutions $\pmod m$ of the form $\frac BA+t\cdot M=\frac BA+t\cdot \frac md$ where $0\le t<d$
A: Here is a different approach.
Suppose that $r'\in\Bbb N\cap[0,m-1]$ is a solution to the first congruence. Notice that $r'$ must also be a solution to the second congruence. If $r'\in\Bbb N\cap[0,{m\over d}-1],$ then we are done (and $r=r'$). Otherwise, there must exist some integer $s<0$ such that $r'+s{m\over d}\in\Bbb N\cap[0,{m\over d}-1].$ Set $r=r'+s{m\over d}.$ Then $r$ is obviously the unique solution to the second congruence in the mentioned interval, and we have $r'=r+t{m\over d}$ with $t=-s.$
Notice also that $|t{m\over d}|=|r-r'|< m,$ which implies that $|t|=t< d.$
Thus any solution $r'$ of the first congruence has the given form. Conversely, it is easy to show that every $r'=r+t{m\over d},$ with $r$ a solution to the second congruence, is a solution to the first.
