Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

3 Answers 3

$\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|improve this answer
    
Lol, this looks like we have the very same idea :) –  yo' Jan 13 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|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

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

share|improve this answer

Your Answer

 
discard

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.