<s>[INST] Solve $12x\equiv9\pmod{15}$ Question:
Solve $12x\equiv9\pmod{15}$
My try:
$\gcd(12,15)=3$ so it has at least $3$ solutions.
Now
$15=12\times1+3\\
3=15-12\times 1\\
3=15+2\times(-1)\\
\implies9=15\times3+12\times(-3)\\
\implies12\times(-3)\equiv9\pmod{15}$
So $x\equiv-3\pmod{15}$
Am I correct?
 [/INST] $\begin{eqnarray}{\bf Hint}\quad 12x\equiv 9\!\!\!\pmod{15} &\iff& 15\mid 12x-9\\ &\iff& \dfrac{12x-9^{\phantom I}}{15} = \dfrac{4x-3}5\in\Bbb Z\\ \\ &\iff& 5\mid 4x-3\\ \\ &\iff& 4x\equiv3\!\!\!\pmod 5 \end{eqnarray}$
Hence $\,{\rm mod}\ 5\!:\,\ 3 \equiv 4x\equiv -x\ \Rightarrow\ x \equiv -3\equiv 2\ $ hence
$$\ x = 2 + 5n = \ldots,-3,2,7,12,17\ldots  \equiv\, 2,7,12\!\!\pmod{15}$$
Remark $\ $ Notice in particular how one needs to cancel the gcd $(12,9) = 3$ from the modulus too, and how this is explained above by putting the associated fraction into lowest terms.
</s>