2
$\begingroup$

Take two integers $a,b$ with $\mathrm{GCD}(a,b)=1$ and $a$ odd. Consider the Diophantine equation $$ a(x^2-y^2)+2bxy=1,\qquad x,y\in\mathbb Z $$

Is there any efficient way to determine whether such an equation is solvable for a given $(a,b)$? For example, for $a=9$ and $b=10$, FindInstance is unacceptably slow:

FindInstance[9 (x^2 - y^2) + 2 10 x y == 1, {x, y}, Integers] != {} // AbsoluteTiming
(* around 9 seconds on my laptop *)

I am interested in pairs $(a,b)$ much larger than $\sim 10$. Surely there must be a better, much more specific way to solve this.

$\endgroup$
5
  • $\begingroup$ On develop.wolframcloud.com still takes around: {9.85082,True} seconds. $\endgroup$ Nov 14, 2018 at 19:33
  • $\begingroup$ Could you please explain, are you interested in a general analytic formula for any a and b or a general analytic formula for fixed a and b, or a random sample of solutions produced quickly? $\endgroup$ Nov 14, 2018 at 20:11
  • $\begingroup$ @VitaliyKaurov Given a fixed pair of integers, say $a=99$ and $b=100$, I want to know whether the equation is solvable or not; the actual solution being irrelevant. And I want to know this as fast as possible: ideally, it should take it less than a second for pairs of order $a,b\sim 10^4$ or higher, to decide whether the equation is solvable or not. I believe there is some algorithm (Gauss? Legendre?) for this kind of polynomial equations, although I'm not sure. $\endgroup$ Nov 14, 2018 at 20:14
  • $\begingroup$ @AccidentalFourierTransform understood, thank you ! $\endgroup$ Nov 14, 2018 at 20:16
  • $\begingroup$ Strange it's so slow. There's a general approach for quadratic Diophantine equations. See this solver: alpertron.com.ar/QUAD.HTM $\endgroup$
    – Greg Hurst
    Nov 14, 2018 at 22:24

2 Answers 2

3
$\begingroup$

To determine if a solution exists, it suffices to look at convergents of a quadratic irrational.

SolutionQ[-1|1, _] = True;
SolutionQ[0, _] = False;
SolutionQ[_, 0] = False;

SolutionQ[a_, b_] /; !CoprimeQ[a, 2b] = False;

SolutionQ[a_, b_] := 
  Or[
    AnyTrue[Most[Convergents[(-b + Sqrt[b^2+a^2])/a]], solQ[a, b]],
    AnyTrue[Most[Convergents[(-b - Sqrt[b^2+a^2])/a]], solQ[a, b]]
  ]

solQ[a_, b_][r_] := 
  With[{x = Numerator[r], y = Denominator[r]}, 
    a(x^2 - y^2) + 2 b x y == 1
  ]

Some comparisons:

SolutionQ[9, 10] // AbsoluteTiming
SolutionQ[13, 9] // AbsoluteTiming
SolutionQ[99, 100] // AbsoluteTiming
SolutionQ[997, 1100] // AbsoluteTiming
SolutionQ[99711, 11011] // AbsoluteTiming
{0.00199, True}
{0.002114, False}
{0.009289, True}
{0.03192, True}
{0.743921, True}
FindInstance[9 (x^2 - y^2) + 2*10 x y == 1, {x, y}, Integers] // AbsoluteTiming
FindInstance[13 (x^2 - y^2) + 2*9 x y == 1, {x, y}, Integers] // AbsoluteTiming
TimeConstrained[FindInstance[99 (x^2 - y^2) + 2*100 x y == 1, {x, y}, Integers], 300]
TimeConstrained[FindInstance[997 (x^2 - y^2) + 2*1100 x y == 1, {x, y}, Integers], 300]
{7.4759, {{x -> -8485, y -> 3256}}}
{0.324242, {}}
$Aborted
$Aborted
$\endgroup$
3
$\begingroup$

The following code relies on Reduce, which is the rate-determining step and can be slow. Nevertheless, it solves $a=99$ and $b=100$ in about half a second. It solves $a=997$ and $b=1100$ in about 0.8 s. Remove "=!= {}" to see a few of the smallest solutions, if any.

AccidentalSolutionQ[a_, b_] :=
   Block[{r, s, w, y},
      r = Flatten[Table[
        Simplify[{ToRules[
          Reduce[{w^2 - 4 (a^2 + b^2) y^2 == 4 a}, {w, y}, Integers] /. C[1] -> k]}],
        {k, -1, 1}], 1];
      If[r == {},
         False,
         s = {w, y} /. r;
         Map[{(#[[1]] - 2 b #[[2]])/(2 a), #[[2]]} &, 
             Pick[s, Map[IntegerQ[(#[[1]] - (2 b)*#[[2]])/(2 a)] &, s]]] =!= {}
      ]]
$\endgroup$
1
  • $\begingroup$ Why not use the substitution x -> (w-b y)/a instead of x -> (w - 2 b y)/(2 a)? It seems that the resulting equation can be solved more quickly by Mathematica. $\endgroup$
    – Carl Woll
    Nov 15, 2018 at 0:29

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.