2
$\begingroup$

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.)

$\endgroup$
7
  • 1
    $\begingroup$ Diophantine equations are, by definition, polynomial equations for which one seeks only integer solutions. Your title is redundant and non-specific, as it equates to "Solving Diophantine equations". Try to make the title your question. $\endgroup$ Apr 11, 2020 at 0:11
  • $\begingroup$ Good point, fixed. $\endgroup$ Apr 11, 2020 at 0:43
  • 1
    $\begingroup$ The page you found spends most of its time finding the first solution. Finding the rest is easier because of the Brahmgupta-Fibonacci identity. It is a good one. $\endgroup$ Apr 11, 2020 at 2:16
  • 1
    $\begingroup$ $2y^2+2xy-Cx-D=0 \implies(x + 2 y)^2 - (x + C)^2 = 2D -C^2$ $\endgroup$ Apr 11, 2020 at 8:05
  • $\begingroup$ @RossMillikan Interesting! Thanks. $\endgroup$ Apr 11, 2020 at 18:47

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Hi John, thanks for that answer. It sounds like your idea is to work with smaller numbers $i, j$. However, the final equation still involves two variables ($i, j$) and the equation $2i^2 - D$, which seems to be about as difficult as the original equation. Is that correct? I'm also interested in any research on the complexity of solving this equations. Is it inherently something along the lines of $O(C^2)$, or are lower upper bounds known? $\endgroup$ Apr 11, 2020 at 0:51
  • $\begingroup$ @EntangledLoops You are welcome for the answer. You're right, they don't reduce the complexity too much for particularly large values of $C$ and $D$. Instead, they might help to provide a particular method to use to solve the equation. Regarding research on the complexity of solving an equation like yours, I don't know of any myself, including how it compares to $O(C^2)$. $\endgroup$ Apr 11, 2020 at 0:55
  • $\begingroup$ Starting from the second line of $(2)$ in this answer you need $x^2+2Cx+2D=(x+C)^2+(2D-C^2)$ to be a perfect square and for its parity to be the same as the parity of $x$. This means that $C$ and $D$ must have the same parity or you are sunk. $\endgroup$ Apr 11, 2020 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.