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.

• 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$. – Daniel Fischer Aug 31 '13 at 12:37
• "I have found solution when $a$ is prime" Oh? What's the solution when $a=3$? – Gerry Myerson Aug 31 '13 at 12:40

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.
• Sorry, I forgot to say, I can't factorise $a$,because it is very large. – Marcin Augustynowicz Aug 31 '13 at 12:59