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.
Asked
Active
Viewed 131 times
1
-
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 Answers
3
Building on the comments, a strategy might be the following.
- 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.
- 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.
- Use the Chinese Remainder Theorem to glue all these solutions together.
Andreas Caranti
- 68,873
-
Sorry, I forgot to say, I can't factorise $a$,because it is very large. – Marcin Augustynowicz Aug 31 '13 at 12:59