I use an example to explain my question:

How many solutions are there to $x^2+3x+18\equiv 0$ (mod $28$).

Usually I will encounter these kind of problems. My first step must transform this equation to become 2 equations: $$x^2+3x+18\equiv 0 \quad (\text{mod }7) $$ $$x^2+3x+18\equiv 0\quad (\text{mod }4) $$ Then, I just plug in the numbers $0$ to $6$ to eq 1 to find out there is one solution $x\equiv 2$ mod $7$.

For equation 2, I do the same thing, plug in $0$ to $3$ and there are two solutions:$x\equiv 2$ and $x\equiv 3$ mod $4$.

Then how should I continue?? Using Chinese Remainder Theorem? Because I have made the original equation into a two simultaneous equations, maybe something like:

  1. $x\equiv 2$ mod $7$ and $x\equiv 2$ mod $4$
  2. $x\equiv 2$ mod $7$ and $x\equiv 3$ mod $4$ Is it the general way to do it? But is there a faster way to determine the number of solutions without performing CRT?

Hint. Note that $$x^2+3x+18\equiv x^2+3x-10= (x+5)(x-2)\pmod{28}.$$

  • $\begingroup$ Thank you. This is a much better method. $\endgroup$ – Jason Ng Nov 30 '18 at 6:32
  • $\begingroup$ Thanks, this is by far the best method $\endgroup$ – Alessar Dec 3 '18 at 12:34

$x\equiv2\pmod4,x\equiv2\pmod7\implies$lcm$(4,7)|(x-2)\implies x\equiv2\pmod{28}$

For the second, $$7a+2=4b+3\iff7a=4b+8-7\iff\dfrac{7(a+1)}4=b+2$$ which is an integer

$\implies4|7(a+1)\iff4|(a+1)$ as $(4,7)=1$

$\implies a+1=4c$

$\implies x=7a+2=7(4c-1)+2=28c-5\equiv-5\pmod{28}\equiv-5+28$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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