Quickly Finding Positive Solutions to Diophantine Equations

Question

I'm wondering if someone can help point me to the fastest available methods for solving problems like the following:

Given positive integers $C, D,$ find the smallest positive integers $x$ and $y$ that satisfy $$2y^2 + 2xy - Cx - D = 0.$$

In my use case, $C, D$ are known constants, but they can be large. I'm only interested in the first pair of positive $x, y$ that solve the equation. I found this neat page that has a solver which works fine. However, when $C$ and $D$ get very large, it takes a long time trying to find multiple solutions.

I'm also interested in knowing what kind of computational complexity I'm looking at to solve this type of quadratic, and if solving this sort of equation is intractable when $C, D$ get arbitrarily large.

(Note: I realize writing "the smallest positive integers" is vague, since they are a pair. I'm interested in the smallest positive $x$ that also has a positive $y$ solution.)

Answer 1

Consider your equation as a quadratic equation in $y$ to get

$$2y^2 + (2x)y + (-Cx - D) = 0 \tag{1}\label{eq1A}$$

By the quadratic formula, you then get

$$\begin{equation}\begin{aligned} y & = \frac{-2x \pm \sqrt{4x^2 - 4(2)(-Cx - D)}}{4} \\ & = \frac{-x \pm \sqrt{x^2 + 2Cx + 2D}}{2} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Since you're only interested in positive integers $x$ and $y$, you'll only want to use the one adding the square root. For $y$ to be an integer with $x$ being an integer requires the discriminant, i.e., the part in the square root, to be a perfect square. Let that be with

$$z = x + k, \; k \in \mathbb{Z} \tag{3}\label{eq3A}$$

You thus get

$$y = \frac{-x + (x + k)}{2} = \frac{k}{2} \tag{4}\label{eq4A}$$

and

$$\begin{equation}\begin{aligned} x^2 + 2Cx + 2D & = (x + k)^2 \\ x^2 + 2Cx + 2D & = x^2 + 2kx + k^2 \\ (2C - 2k)x & = k^2 - 2D \end{aligned}\end{equation}\tag{5}\label{eq5A}$$

Now, if $2C = 2k \implies k = C$, then $k^2 = 2D \implies D = \frac{C^2}{2}$. In that case, you get from \eqref{eq4A} that

$$y = \frac{C}{2} \tag{6}\label{eq6A}$$

and then you can get $x$ from \eqref{eq1A}, which I'll leave to you to do.

Otherwise, if $D \neq \frac{C^2}{2}$, and thus $C \neq k$, you then get from \eqref{eq5A} that

$$x = \frac{k^2 - 2D}{2C - 2k} \tag{7}\label{eq7A}$$

From \eqref{eq4A}, you need for $k$ to be an even integer, say

$$k = 2j \tag{8}\label{eq8A}$$

Then \eqref{eq7A} becomes

$$\begin{equation}\begin{aligned} x & = \frac{4j^2 - 2D}{2C - 4j} \\ & = \frac{2j^2 - D}{C - 2j} \\ & = \frac{2j^2 - Cj + Cj - D}{C - 2j} \\ & = \frac{j(2j - C) + Cj - D}{C - 2j} \\ & = -j + \frac{Cj - D}{C - 2j} \end{aligned}\end{equation}\tag{9}\label{eq9A}$$

Thus, you now need to find integers $j$ such that $C - 2j \mid Cj - D$. One extra thing you can do to help with the calculations is to handle whether $C$ is even or odd. For example, if $C$ is even, e.g.,

$$C = 2i, \; i \in \mathbb{Z} \tag{10}\label{eq10A}$$

then the fraction in \eqref{eq9A} becomes

$$\begin{equation}\begin{aligned} \frac{Cj - D}{C - 2j} & = \frac{2ij - D}{2i - 2j} \\ & = \frac{2ij - 2i^2 + 2i^2 - D}{2i - 2j} \\ & = \frac{i(2j - 2i) + 2i^2 - D}{2i - 2j} \\ & = -i + \frac{2i^2 - D}{2i - 2j} \end{aligned}\end{equation}\tag{11}\label{eq11A}$$

Now, you just need to find a $j$ where $2i - 2j \mid 2i^2 - D$. You can do something similar for the case where $C$ is odd.

Using these equations might help make the calculations required somewhat easier & more efficient, even for very large $C$ and $D$.