Solve $12x\equiv9\pmod{15}$

Question

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?

Answer 1

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.

Answer 2

$\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.

Answer 3

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$).