How to solve congruence $x^2-2 \equiv 0\pmod a$, $x$ and $a$ are integers, and $a$ mustn't be prime? I have found solution when a is prime, but I haven't found solution for general case.

  • $\begingroup$ Find solutions modulo all the distinct (highest) prime powers $p^n$ dividing $a$, and use the Chinese remainder theorem to assemble them to a solution modulo $a$. $\endgroup$ – Daniel Fischer Aug 31 '13 at 12:37
  • $\begingroup$ "I have found solution when $a$ is prime" Oh? What's the solution when $a=3$? $\endgroup$ – Gerry Myerson Aug 31 '13 at 12:40

Building on the comments, a strategy might be the following.

  1. Check that the congruence has a solution modulo all prime divisors $p$ of $a$. If there is no solution even for a single such prime $p$, the congruence itself has no solution. For this, you may use quadratic reciprocity.
  2. Assuming there are solutions for each such $p$, find them, and use Hensel lifting to get a solution modulo each prime power $p^{e}$ such that $p^{e}$ divides $a$, but $p^{e+1}$ does not.
  3. Use the Chinese Remainder Theorem to glue all these solutions together.
  • $\begingroup$ Sorry, I forgot to say, I can't factorise $a$,because it is very large. $\endgroup$ – Marcin Augustynowicz Aug 31 '13 at 12:59

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.