1
$\begingroup$

Is there a general way to solve quadratic equations modulo n? I know how to use Legendre and Jacobi symbols to tell me if there's a solution, but I don't know how to get a solution without resorting to guesswork. Some examples of my problems:

$x^2 = 8$ mod 2009
$x^2 + 3x + 1 = 0$ mod 13

Thanks

$\endgroup$
  • $\begingroup$ The first problem, with no cross terms, is hard in general. The second one can be reduced to the first by completing the square. $\endgroup$ – vadim123 Apr 29 '15 at 15:08
3
$\begingroup$

The answer depends on the value of the modulus $n$.

  • in general, if $n$ is composite, then solving modulo $n = \prod p_i^{e_i}$ is equivalent to solve modulo each $p_i^{e_i}$. However, this requires knowing the factorization of $n$, which is hard in general (in a computational way): there are cryptosystems based on this.
  • modulo a prime $p \neq 2$, you may simply complete the square and proceed in exactly the same way as in the reals.
  • modulo the prime $p = 2$, it is impossible to complete the square. Instead, the relevant way to solve quadratic equations is through Artin-Schreier theory: basically, instead of $x^2 = a$, your “standard” quadratic equation is here $x^2-x = a$. (Well, this is useful for extensions of the field $\mathbb Z/2\mathbb Z$, but not so much for this field itself, since you can then simply enumerate the solutions...).
  • modulo a power $p^e$, you start by computing an “approximate” solution, that is, a solution modulo $p$. You may then refine this solution to a solution modulo $p^e$ by using Hensel's lemma. Note that this works for both the equations $x^2 = a \pmod{p \neq 2}$ and $x^2 - x = a \pmod{2}$ as stated above.

This means that the only remaining problem is how to compute a square root modulo a prime $p$. For this, the relevant reference would be the Tonnelli-Shanks algorithm; see for instance Henri Cohen's A Course in computational algebraic number theory, 1.5.1.

$\endgroup$
  • $\begingroup$ For modulo a prime p not equals 2, what is the "same way as in the reals"? $\endgroup$ – user221330 Apr 29 '15 at 15:29
  • $\begingroup$ In the same way as far as deciding the existence goes (except the sign is replaced by the Jacobi symbol). For computing the solution, it is different: you use the structure of the multiplicative group $(\mathbb Z/p\mathbb Z)^\times$. I edited my answer to add a reference. $\endgroup$ – Circonflexe Apr 29 '15 at 15:31
  • $\begingroup$ Thanks for the help, but I'm expected to do these by hand! $\endgroup$ – user221330 Apr 29 '15 at 15:47
  • $\begingroup$ @user221330 See this answer for how to solve any quadratic congruence mod $p\neq 2$. $\endgroup$ – user26486 May 3 '15 at 19:48

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.