# Solving quadratic equations in modular arithmetic

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

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

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.

• For modulo a prime p not equals 2, what is the "same way as in the reals"? – user221330 Apr 29 '15 at 15:29
• 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. – Circonflexe Apr 29 '15 at 15:31
• Thanks for the help, but I'm expected to do these by hand! – user221330 Apr 29 '15 at 15:47
• @user221330 See this answer for how to solve any quadratic congruence mod $p\neq 2$. – user26486 May 3 '15 at 19:48