In this post, we’re interested in finding any or all integer solutions of a binary quadratic equation:

$$x^2 - ny - a = 0.$$

We assume that the equation is non-degenerate in the sense that $n \neq 0$.

Normalization

We first normalize the problem to simplify its properties.

• Assume $n > 0$. Otherwise, reduce it to $x^2 - (-n)(-y) - a = 0$.
• Assume $n = p^e$ is a prime power. Otherwise, write $n = \prod\limits_{i=1}^k p_i^{e_i}$ and solve $x^2 \equiv a \pmod {p_i^{e_i}}$ for each $p_i^{e_i}$ and use CRT to combine all results.
• Assume $a \neq 0$. If $a = 0$, all solutions are $\{p^i \bmod p^e: e \leq 2i \leq 2 e\}$.
• Assume $p$ does not divide $a$. Otherwise, write $a = a' p^{e'}$ where $p$ does not divide $a'$.
  • If $e'$ is odd, there exists no solution.
  • If $e'$ is even, $x$ must be a multiple of $p^{e'/2}$, so reduce it to $(x/p^{e'/2})^2 \equiv a' \pmod{p^{e-e'}}$.

After normalization, the problem that we’re interested in is:

We say that $x$ is a quadratic residue modulo $n$ if $x^2 \equiv a \pmod{n}$ has a solution, and a quadratic non-residue modulo $n$ otherwise.

The case of $p = 2$

(Solubility) For $p = 2$, $a$ is a quadratic residue modulo $p^e$ if and only if $a \equiv 1 \pmod 8$.

To find one or all solutions, we first consider the two easy cases:

• If $e = 1$, certainly the case is $a \equiv 1 \pmod 2$ and all solutions are $x \equiv 1 \pmod 2$.
• If $e = 2$:
  • If $a \equiv 1 \pmod{4}$, all solutions are $x \equiv 1 \pmod 2$.
  • Otherwise, there is no solution.

Now we assume $e > 2$.

(Any solution) Observe that:

$$\left(x + \frac{x^2 - a}{2} \right)^2 - a = (x+1)(x^2 - a) + \left( \frac{x^2 - a}{2} \right)^2.$$

So if $x_{e-1}$ satisfies $x^2 \equiv a \pmod{2^{e-1}}$, then $x_e = x_{e-1} + \frac{x_{e-1}^2 - a}{2}$ satisfies $x^2 \equiv a \pmod{2^e}$. Thus, we can begin with $x_2 = 1$.

(All solutions) Let $x^*$ be any solution to $x^2 \equiv a \pmod{2^e}$. It is clear that $x^*$ must be odd. Consider $\frac{x^* - x}{2}$ and $\frac{x^* + x}{2}$. The sum is $x^*$, so only one of them is even. The product is $\frac{x^{*2} - x^2}{4} \equiv 0 \pmod{2^{e-2}}$, thus one of them is 0 modulo $2^{e-2}$. Thus, the set of all solutions is:

$$x \in \{\pm x^*\} \pmod{2^{e-1}}.$$

The case of an odd prime $p$

(Solubility) The solubility is often determined by the Jacobi symbol, which is the generalization of the Legendre symbol: For an odd prime $p$, $a$ is a quadratic residue modulo $p^e$ if and only if

$$\left( \frac{a}{p^e} \right) = 1, \quad \left( \frac{a}{p^e} \right) := \left( \frac{a}{p} \right)^e,$$

where $\left( \frac{a}{p} \right)$ is the Legendre symbol.

Note that this does not apply to $p = 2$ (e.g., $x^2 \equiv 3 \pmod 4$) or general composite numbers (e.g., $x^2 \equiv 8 \pmod {15}$).

(Modulo a prime ($e=1$)) There exist well-known algorithms for finding a solution to $x^2 \equiv a \pmod p$, e.g., the Tonelli-Shanks algorithm and Cipolla’s algorithm.

(Modulo a prime power ($e > 1$)) Let $x'$ be any solution to $x^2 \equiv a \pmod{p}$. Tonelli shows that

$$x^* \equiv x'^{p^{e - 1}} \cdot a^{(p^e - 2 p^{e-1} + 1) / 2} \pmod{p^e},$$

is a solution to Equation \eqref{eq:quad-residue}.

Alternatively, Cipolla’s algorithm can be extended to find a solution to Equation \eqref{eq:quad-residue} directly: Let $u$ be any integer such that $u^2 - a$ is a quadratic non-residue modulo $p$, then

$$x^* \equiv \frac{1}{2} a^{(p^e - 2 p^{e-1} + 1) / 2} \left(\left(u + \sqrt{u^2 - a}\right)^s + \left(u - \sqrt{u^2 - a}\right)^s \right). \pmod{p^e}$$

where $s := p^{e-1} (p+1)/2$.

Moreover, it’s also possible to use the identity

$$\left( \frac{x^2 + a}{2x} \right)^2 - a = \frac{(x^2 - a)^2}{4x^2}$$

to generate a solution from $x'$ by iterating it for $\log e$ times, but a division modulo $p^e$ takes $O(\log p^e)$ time so it won’t be faster.

(All solutions) Similarly, let $x^*$ be any solution to $x^2 \equiv a \pmod{p^e}$. Since $(x^* - x)(x^* +x) \equiv 0 \pmod {p^e}$, and at most one of $x^* - x$ and $x^* + x$ is a multiple of $p$, we conclude that all solutions are

$$x \in \{\pm x^*\} \pmod{p^e}.$$

References

• Tonelli-Shanks algorithm
• Cipolla’s algorithm
• [Dickson]: Dickson, L.E., 1919. History of the Theory of Numbers (No. 256). Carnegie Institution of Washington.