I'm studying for a test and have 2 problems that I just can't figure out.

a) $3x^2+5x-2 \equiv 0 \pmod{12}$

I know that I have to seperate this to mod 3 and mod 4, but can't do much after.

b) $x^3+x+3 \equiv 0 \pmod{125}$

No idea. Probably something with $\pmod{5}$.

Please help :3


One approach to both problems is to start by looking at them modulo various divisors of the original modulus, with each subsequent divisor being multiple of the preceding one. Each step then provides further refinement of the information we have about the solutions; reducing the amount of work we need to perform.

For example, in the first case, we can proceed as follows:

  • Let's start by looking at the equation "modulo $3$". Trying out all three possible remainders of $x$ modulo $3$ tells us that only $x\equiv 1\pmod 3$ works.
  • This implies that once we move to "modulo $6$", the only possible values of $x\pmod 6$ will be $1$ and $4$. As it turns out, both of them work modulo $6$.
  • Finally, let's get up to "modulo $12$". Since we had two possible remainders modulo $6$, there are four candidates modulo $12$: $1, 4, 7, 10$. Of these, only $7$ and $10$ turn out to work; both being solutions of the original equation.

Of course, one doesn't need to restrict to primes; we could just as well start by looking at the equation modulo $4$ and check the four possibilities in order to find that $1$ and $2$ work; and then step up directly to "modulo $12$".

Alternatively, if one is more interested in the theory behind the problems, the first one is good example for the Chinese Remainder Theorem and the second one goes well with Hensel's Lifting Lemma.


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.