Integer and Rational Solutions of a Binary Quadratic Equation (0): General binary quadratic equation

Posted on In , Disqus: Word count in article: 1.5k Reading time ≈ 5 mins.

In this post, we are interested in finding all integer and rational solutions for a general binary quadratic equation: \[ \begin{equation} ax^2 + bxy + cy^2 + dx + ey + f = 0, \label{eq:general} \end{equation} \] for any integer coefficients \(a, b, c, d, e, f\). The equation might degenerate; we only point it out when it does but do not solve it, as it's typically easier to solve a degenerate equation.

This post mainly serves as an entry point for a series of posts and also contains a little bit of the story behind the posts. That is why this post has index 0 in the title.

The story

As readers might know, I have been practicing Project Euler for years. Project Euler contains many problems related to number theory, some of which involve solving binary Diophantine equations. One of the most famous examples of quadratic Diophantine equations is the Pythagorean triples (\(x^2 + y^2 = z^2\)).

One day, I suddenly had an idea: What's the general method for solving quadratic equations? How can we enumerate the solutions? Given that there might be infinite solutions, probably we want to enumerate bounded solutions efficiently (mostly for solving Project Euler problems). So I spent time researching, reading numerous papers, notes, books and blog posts... Until I thought I was done and ready to summarize what I had learned into posts.

While finishing my writing, I found Quadratic diophantine equations BCMATH programs, and immediately realized that my literature review was so incomplete. The website covers most related topics and is maintained by Keith Matthews, who seems to be a domain expert, with regular updates. Reading his papers made me question the necessity of my posts...

Nevertheless, I decided to proceed with my writing. Perhaps it's for my own understanding, or perhaps I simply don't want to admit I haven't published anything on my blog for two months (so I even break the topic down into many small parts)...

What's next? I still have two incomplete things, but it depends on whether my interests fade.

  • Implement the algorithms, which is a perfect chance to learn a new programming language, just like what I did for my previous side project (Analytic prime counting, Part 1 and Part 2).
  • More efficient enumeration of primitive solutions of the Legendre equation. Although an upper bound of the GCD exists, I still want to make it more efficient by removing GCD. The requirement of enumerating the primitive input pair \((u, v)\) probably can't be removed, though.

Common techniques

Suppose we want to solve \(f(\mathbf{x}) = n\).

  • (Homogenization) If \(f\) is not homogeneous, it may be beneficial to homogenize it;
  • (Diagonalization) If \(f(\mathbf{x}) = x^\T Q \mathbf{x}\) is quadratic but \(Q\) is not diagonal, diagonalize it;
  • (Primitive solutions) Only consider the primitive solutions. For most cases, an algorithm for primitive solutions can be easily used to find non-primitive solutions (Turing reduction);
  • (Partition of solution space) Consider the equation \(f(\mathbf{x}) \equiv 0 \pmod{n}\). The solution gives us strong constraints on \(\mathbf{x}\), which is enough to partition the solution space.

Integer solutions

Let \(\Delta := b^2 - 4ac\) be the discriminant of the equation.

  • (Case 1) If \(a = c = 0\):

    • (Case 1.1) If \(b = 0\): it simplifies to a linear case \(dx + ey + f = 0\);
    • (Case 1.2) If \(b \neq 0\): This results in a degenerate case: \((bx + e)(by + d) = de - bf\). To solve, factor \(de - bf\) to express it in terms of \(bx + e\) and \(by + d\).

  • (Case 2) If \(\Delta = 0\) while \(a \neq 0\) or \(c \neq 0\): Without loss of generality (W.L.O.G.), we assume \(a \neq 0\). Note \[ 4a(a x^2 + bxy + cy^2 + dx + ey + f) = (2ax + by + d)^2 + (4ae - 2bd)y - (d^2 - 4af). \] Thus:

    • (Case 2.1) If \(2ae = bd\): Solve \((2ax+by+d)^2 = d^2 - 4af\);
    • (Case 2.2) If \(2ae \neq bd\): Solve \[ (2ax+by+d)^2 \equiv d^2 - 4af \pmod{|4ae - 2bd|} \] using quadratic residue.

  • (Case 3) If \(\Delta \neq 0\), while \(a \neq 0\) or \(c \neq 0\). W.L.O.G. we assume \(a \neq 0\). Note \[ 4 a \Delta (ax^2+bxy+cy^2 + dx + ey + f) = x'^2 - \Delta y'^2 - 4an, \] where \[ \begin{aligned} x' &= \Delta y - 2ae + bd,\\ y' & = 2 a x + by + d, \\ n & = ae^2 - bde + cd^2 + \Delta f. \\ \end{aligned} \] Thus:

  • (Alternative Case 3) If \(\Delta \neq 0\), note \[ \Delta^2 (ax^2 + bxy + cy^2 + dx + ey + f) = ax'^2 + bx'y' + cy'^2 + \Delta n, \] where \[ \begin{aligned} x' &= \Delta x - 2cd + be, \\ y' &= \Delta y - 2ae + bd, \\ n &= ae^2 - bed + cd^2 + \Delta f. \end{aligned} \] Then we can use the methods about solving binary quadratic forms to find all integer solutions to \(ax'^2 + bx'y' + cy'^2 = n\). The advantage of the method is that we don't need to diagonalize the equation, although many methods implicitly include this step.

Note that many changes of variable are not unimodular, so we need to verify whether the result is an integer solution.

Rational solutions

We write the equation in the matrix form: \[ \mathbf{x}^\T Q \mathbf{x} = 0, \quad Q := \begin{pmatrix} 2a & b & d \\ b & 2c & e \\ d & e & 2f \\ \end{pmatrix}, \quad \mathbf{x} := \begin{pmatrix} x \\ y \\ 1 \end{pmatrix}. \]

(Diagonalization) The matrix \(Q\) may not be diagonal. If so, we can diagonalize it by finding an invertible matrix \(P \in \QQ^{3 \times 3}\) and a diagonal matrix \(D \in \ZZ^{3 \times 3}\) such that \[ Q = P^\T D P. \] It follows that \[ \mathbf{x}^\T Q \mathbf{x} = 0 \quad \Longleftrightarrow \quad (P \mathbf{x})^\T D (P \mathbf{x}) = 0. \] One possible approach is to use the LDL decomposition. However, the matrix \(Q\) may not have a LDL decomposition if, at some step (e.g., \((x+y)^2 + yz\)), the diagonal element becomes zero. If this occurs, we can conclude that the equation at that step is actually linear in the variable (e.g., \(y\) in the example). Thus we can always treat other variables (\(x' = x+y, z\)) as free variables and compute \(y\) in the end.

(Legendre equation) Let \(Q = \diag(a', b', c')\), we consider the primitive solutions to the Legendre equation \(a'x'^2 + b' y'^2 + c'z'^2 = 0\). For any primitive solution \(\mathbf{x}' = (x', y', z')\) to the Legendre equation, write \((x, y, z) = P \mathbf{x'}\). If \(z \neq 0\), then \((x/z, y/z)\) is a rational solution to the original equation.

(Solving Legendre equation) For the Legendre equation \(a'x'^2 + b' y'^2 + c'z'^2 = 0\), we assume \(|a'| \geq |b'| \geq |c'|\) W.L.O.G. We analyze the number of zero coefficients among \(a', b', c'\).

  1. There are 3 zeros. Any \((x', y', z')\) for any \(x', y', z'\) is a solution;
  2. There are 2 zeros. Any \((0, y', z')\) for any \(y', z'\) is a solution;
  3. There is 1 zero. Any \((ty', y', z')\) for any \(y', z'\), and any rational solution \(t\) to \(a' t^2 + b' = 0\), is a solution.
  4. There is no zero. We find any non-trivial integer solution \(\mathbf{x'}\) to the Legendre equation \(a'x^2 + b'y^2 + c'z^2 = 0\), and every rational solution can be parameterized by \(\mathbf{x}'\).

Homework: \(\frac{x}{y+z} + \frac{y}{z+x} + \frac{z}{x+y}=4\)

How hard it can be?

Answer: See Alon Amit's excellent post.

References

General resources from the Internet:

  • Quadratic diophantine equations BCMATH programs by Keith Matthews.
    • Also check out the history of his algorithm for his line of work.
  • Methods to solve quadratic Diophantine equations by Dario Alejandro Alpern;
    • The validity of the following statement is uncertain:

    If \(4F^2<B^2-4AC\), the solutions of the equation will be amongst the convergents of the continued fraction of the roots of the equation \(At^2+ Bt + C = 0\).

  • Sander Verdonschot's repo, which implements many Keith Matthews' papers in Java;
  • Thilina Rathnayake's blog when developing the Diophantine module of SciPy;
  • Diophantine Equation--2nd Powers from Wolfram MathWorld;
  • SciPy's doc on Diophantine equations;
  • Writings in Keith Conrad's websites. It may be elementary, but it is sufficient for amateurs like me.

Textbooks and notes:

  • [Dickson19] : Dickson, L.E., 1919. History of the Theory of Numbers (No. 256). Carnegie Institution of Washington.
  • [Mordell69] : Mordell, L.J., 1969. Diophantine Equations: Diophantine Equations (Vol. 30)
  • Matthews15: Matthews, K., 2015. Solving the Diophantine Equation \(ax^2 + bxy + cy^2 + dx + ey + f = 0\).