Solve $ax \equiv b \mod m$ without Linear Congruence Theorem or Euclid's Algorithm? 


Origin page 5. The overhead doesn't look like Linear Congruence Theorem or anything from Euclid's Algorithm. page 4 tries to delineate 
Casting Out the Modulus? Is this it?
So if $d|m,$ then I rewrite $\begin{align} ax & \equiv b \mod m
\\dx + x & \equiv 
\\ \implies x & \equiv \end{align}$
Is this errorless? Did I blight anything? 
 A: The $3x \equiv 9 \mod 6 $ has a common factor of $3$.  Dividing both sides by 3 - including the modulus - we get:
$$
\begin{array}{ccc}
3x & \equiv & 9 \mod 6 \\
x & \equiv & 3 \mod \mathbf{2} 
\end{array}
 $$
For the remaining two congruence, we multiply both sides by an appropriate number:
$$
\begin{array}{rcc}
2x & \equiv & 1 \mod 5 \\
3(2x) & \equiv & 3 \mod 5 \\
x & \equiv & 3 \mod 5 
\end{array}
 $$
In modular arithmetic we have inverses $3\times 2 = 6 \equiv 1 \mod 5$ so we can say that $2^{-1} = 3$.

If you are still not sure about $x \equiv 3 \mod 2$.  Let's write the congruence as an actual equation:
$$ 
\begin{array}{ccc}
3x -9 & \equiv & 6k \\
x-3  & \equiv & 2k
\end{array}
 $$
The modulus $6$ got reduced to a $2$ in the process.
A: I use the following strategy for solving the linear congruence
$$ax \equiv b \mod{m}\quad (\star)$$
Case 1: $\gcd(a, m) = 1$
Implies that the modular multiplicative inverse $(\color{green}{a^{-1}})$ exists, and we solve for $x$ as follows.
$\begin{eqnarray}&&ax &\equiv b&\mod{m}\\\iff&(\color{green}{a^{-1}})&ax &\equiv (\color{green}{a^{-1}})b&\mod{m}\\\iff&&x &\equiv \color{green}{a^{-1}}b&\mod{m}\tag{1}\end{eqnarray}$
Example: $$2x \equiv 1 \mod{5} \iff x \equiv 3 \mod{5}$$ where $\color{green}{2^{-1} = 3}$ was found using the Extended Euclidean algorithm.
Case 2: $\gcd(a, m) > 1$ and $\gcd(a, m) \nmid b$ 
$\text{No solution exists}\tag{2}$
$\begin{eqnarray}\text{since}&ax &\equiv b \mod{m}\\\iff &ax &= b + mt &(t \in\mathbb{Z})\\\iff &b&= ax - mt \end{eqnarray}$
so $b$ being a linear combination of $a$ and $m$, must be divisible by $\gcd(a, m)$.
Example: $$2x \equiv 3 \mod{4}$$ has no solution, since $\gcd(2, 4) = 2 \nmid 3$.
Case 3: $\gcd(a, m) > 1$ and $\gcd(a, m) \mid b$
Substitute $a = a_0d, b = b_0d, m = m_0d$ in $(\star)$ where $d = \gcd(a, m)$
$\begin{eqnarray}&ax &\equiv b &\mod{m}\\\iff&a_0dx &\equiv b_0d &\mod{m_0d}\\\iff &a_0dx &= b_0d + m_0dt &(t \in\mathbb{Z})\\\iff &a_0x &= b_0 + m_0t &(\text{divide by }d \neq 0) \\\iff&a_0x &\equiv b_0&\mod{m_0}\tag{3}\end{eqnarray}$
which finds itself amenable to solution by invoking case 1, since $\gcd(a_0, m_0) = 1$.
Examples: 


*

*$4x \equiv 2 \mod{10} \underset{(\text{case }3)}{\overset{\gcd(4, 10) = 2}{\iff}} 2x \equiv 1 \mod{5}\underset{(\text{case }1)}{\overset{\gcd(2, 5) = 1}{\iff}} x \equiv 3 \mod{5}$

*$3x \equiv 9 \mod{6} \quad\underset{(\text{case }3)}{\overset{\gcd(3, 6) = 3}{\iff}} x \equiv 3 \mod{2}\quad\underset{(\text{case }1)}{\overset{\text{trivially}}{\iff}} x \equiv 3 \mod{2}$

