Integer and Rational Solutions of a Binary Quadratic Equation (2): Quadratic Residue

Posted on In , Disqus: Word count in article: 872 Reading time ≈ 3 mins.

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:

For a prime \(p\), an integer \(a \neq 0\) such that \(p\) does not divide \(a\), find one or all integer \(x\) such that

\[ \begin{equation} x^2 \equiv a \pmod{p^e}. \label{eq:quad-residue} \end{equation} \]

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.