1
$\begingroup$

http://mathworld.wolfram.com/DiophantineEquation2ndPowers.html says the equation $$ax^2+bxy+cy^2=k$$ can be reduced to Pell equation.

Can someone explain how?

$\endgroup$
  • 1
    $\begingroup$ Do you know how to complete the square? $\endgroup$ – Calvin Lin Sep 11 '13 at 14:53
  • $\begingroup$ I also do not think that the article says what you claim it does. They are separate lines of though. $\endgroup$ – Calvin Lin Sep 11 '13 at 14:55
  • $\begingroup$ What do you think it says? $\endgroup$ – Turbo Sep 11 '13 at 14:57
  • $\begingroup$ They are not sequential statements. There is an entire paragraph (line) between them that talks about implementation in Mathematica, and another paragraph (line) which mentions deeper results for more than 2 variables. $\endgroup$ – Calvin Lin Sep 11 '13 at 15:02
  • $\begingroup$ Well if you know the correct form of the question I am implying, please feel free to modify this question. I am a bit clueless here. $\endgroup$ – Turbo Sep 11 '13 at 15:04
2
$\begingroup$

To sketch the how, starting with $ax^2+bxy+cy^2=k$, look at it as a quadratic in $x$. We then need
$$x = \frac{-b\pm\sqrt{b^2-4a(cy^2-k)}}{2a}$$ to be an integer. Clearly this needs $\sqrt{b^2-4a(cy^2-k)} = z$ to be an integer.

So we solve $z^2 + (4ac)y^2 = b^2 + 4ak$, which is a generalised Pell equation and I suppose you are familiar with solving.

Of course we need to (in the end) pick solutions only where $2a \mid (-b \pm z)$.


Another approach is to use a general translation $X = px + qy, Y = ry$ and then pick the values such that the cross term disappears, then complete the square etc... If I recall the specific translation, will post it. An old reference I have is http://www.math.niu.edu/~rusin/known-math/95/quadratics (check part 2)

$\endgroup$
  • $\begingroup$ Great answer. Thankyou. Actually I am unfamiliar with solving Pell as well. Could you write that portion as well? $\endgroup$ – Turbo Sep 11 '13 at 19:08
  • 1
    $\begingroup$ Describing how to solve the general Pell equation is quite an elaborate job, there are methods using continued fractions, using factoring in a specific ring, algorithms for finding at least one solution etc., including cases where there are no solutions. The good thing is I am sure you should find many references on the web. For e.g. check ams.org/notices/200202/fea-lenstra.pdf . Most of them boil down to "somehow" finding one solution, if this exists, then using a characteristic recurrence pattern to find infinitely many more solutions. $\endgroup$ – Macavity Sep 12 '13 at 15:07
1
$\begingroup$

Edit: This is a shorter and clearer answer to the older version.

Actually, Mathworld is correct when it says solving,

$$a x^2 + b x y + c y^2 = k\tag{1}$$

involves the usual Pell equation,

$$x^2-Dy^2 = \pm 1$$

Given an initial solution {$m,n$} to,

$$a m^2 + b mn + c n^2 = k\tag{2}$$

then we have the identity,

$$a x^2 + b x y + c y^2 - k = k(u^2-Dv^2-1)(u^2-Dv^2+1)\tag{3}$$

where,

$$x = m u^2 - 2 (b m + 2 c n) u v + D m v^2$$

$$y = n u^2 + 2 (2 a m + b n) u v + D n v^2$$

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

for arbitrary variables $u,v$. However, if one wishes to set $(3)$ equal to zero, then $u,v$ should be chosen to satisfy the Pell equation,

$$u^2-Dv^2=\pm 1$$

which, for non-square discriminant $D>0$, should provide an infinite number of integer solutions for the $x,y$ of $(3)$.

$\endgroup$
  • $\begingroup$ Oh wow. Thanks! $\endgroup$ – Calvin Lin Nov 28 '14 at 16:39
  • $\begingroup$ @CalvinLin I modified the answer to make it clearer. $\endgroup$ – Tito Piezas III Nov 29 '14 at 20:40
  • $\begingroup$ Do you know if this provides all solutions? i.e., letting $u,v$ range over all integers, do you eventually generate all integer solutions of (1)? $\endgroup$ – Kieren MacMillan Jan 30 '18 at 19:03
  • 1
    $\begingroup$ @KierenMacMillan: I'm not sure. Also, while $(3)$ is valid for any $u,v$, one has to choose such that $u^2-Dv^2 =\pm1$ to make $(1)$ true, hence $u,v$ does not range over all integers if the objective is $(1)$. $\endgroup$ – Tito Piezas III Jan 31 '18 at 15:10
  • $\begingroup$ Of course; I meant ranging over all integer solutions to the Pell equation. As for the completeness… I smell a theorem I need to prove. ;) $\endgroup$ – Kieren MacMillan Feb 1 '18 at 2:53

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.