Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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?

share|cite|improve this question
No, e.g. $x=2$ is a solution also – user127.0.0.1 Jan 13 '14 at 15:42

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

share|cite|improve this answer
Lol, this looks like we have the very same idea :) – yo' Jan 13 '14 at 15:44

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.

share|cite|improve this answer

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


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.