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?
 A: $\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.
A: Hint: $12x\equiv 9 \pmod{15}$ if and only if $4x\equiv 3\pmod{5}$, this is easy to verify by definition. Now, everything is co-prime to the modulus, so the problem is trivial.
A: Lemma: Let $gcd(a,n)=d$ and suppose that $d|b$. Then the linear congruence 
$ax \equiv b $ (mod $n$)
has exactly $d$ solutions modulo $n$. These are given by
$t,t+\dfrac{n}{d},t+\dfrac{2n}{d},\cdots,t+\dfrac{(d-1)n}{d}$
where $t$ is the solution, unique modulo $n/d$, of the linear congruence
$\dfrac{a}{d}x\equiv \dfrac{b}{d}$ (mod $\dfrac{n}{d}$).
By Lemma, we just need to consider the linear congruence $4x\equiv 3$ (mod $5$), easy to see the unique solution is $2$. Hence the all solutions of $12x\equiv 9$ (mod $15$) is $x\equiv 2,7,12$(mod $15$).
