2
$\begingroup$

Preface: I know there are a lot of posts already here and elsewhere about algorithms for solving quadratic Diophantine equations in general. I am posting this in the hope that my very particular case might allow an approach much simpler (both in time complexity and the need for me to relearn combinatorics) than those for the general case.


I have a program in which I must solve equations of the following form.

$$ x(A-x)=y(B+y) \\~\\ \mbox{or, equivalently,} \\~\\ x^2 - Ax + By + y^2 = 0 $$

Subject to the following nontrivial (I think) constraints.

  • $A, B \in \mathbb{N} \quad \mbox{and} \quad A, B \quad \mbox{are even}$
  • $A \gt B$
  • $x(A-x)=y(B+y)<\frac{A^2-B^2}{8}$
  • $1 \le x \lt \frac{A-B}{2}$
  • $1 \le y \lt \frac{A-B}{2} - 1$

The even, natural numbers $A$ and $B$ are the only parameters.

These constraints are sufficient to reduce the number of possible values of $x,y$ to a few hundred or thousand (342 in the example below). Therefore, rote trial and error can usually find a solution in well under a second. But I'm convinced there must be a smarter way to do this, rather than just checking all possible answers. Therefore, I appeal to you who are smarter than me.


Example

$$ \mbox{Let } A = 50 \\ \mbox{Let } B = 10 \\~\\ x(50-x)=y(10+y) < \frac{50^2-10^2}{8} = 300 \\ 1 \le x \lt \frac{50-10}{2} = 20 \\ 1 \le y \lt \frac{50-10}{2} - 1 = 19 $$

This equation has two solutions.

$$ \begin{align} x&=2,\quad y=6 \\ x&=6,\quad y=12 \end{align} $$

The potential solutions $x=8,y=14$ and $x=14,y=18$ are disqualified because $x(A-x)=y(B+y) \ge 300$ in both cases.

$\endgroup$

1 Answer 1

3
$\begingroup$

If you apply this transformation:

$$\begin{eqnarray*}-4x & = & X - 2A \\ -4y & = & Y + 2B\end{eqnarray*}$$

You get a quadratic Diophantine equation without the linear terms:

$$X^2 + Y^2 = 4A^2 + 4B^2$$

Can you take it from there?

ADDENDUM

Just for completeness, suppose you have a general six-term quadratic Diophantine equation:

$$ax^2 + bxy + cy^2 + dx + ey + f = 0$$

Compute the discriminant of the homogeneous quadratic part:

$$D = b^2 - 4ac$$

Then this substitution eliminates the linear terms, keeping the homogeneous part untouched:

$$\begin{eqnarray*}Dx & = & X + 2cd - be \\ Dy & = & Y + 2ae-bd\end{eqnarray*}$$

This is due to Legendre, but I don't know precisely where.

$\endgroup$
3
  • $\begingroup$ Damn, I wish I was clever like this. $\endgroup$ Nov 22, 2021 at 17:29
  • $\begingroup$ Adrien-Marie Legendre came up with this transformation, not me. $\endgroup$
    – Pseudonym
    Nov 22, 2021 at 22:36
  • $\begingroup$ I don't believe you. I believe you came up with this. You are a genius. $\endgroup$ Nov 23, 2021 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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