# Quadratic Diophantine to Pell reduction

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?

• Do you know how to complete the square? – Calvin Lin Sep 11 '13 at 14:53
• I also do not think that the article says what you claim it does. They are separate lines of though. – Calvin Lin Sep 11 '13 at 14:55
• What do you think it says? – 1.. Sep 11 '13 at 14:57
• 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. – Calvin Lin Sep 11 '13 at 15:02
• 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. – 1.. Sep 11 '13 at 15:04

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)

• Great answer. Thankyou. Actually I am unfamiliar with solving Pell as well. Could you write that portion as well? – 1.. Sep 11 '13 at 19:08
• 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. – Macavity Sep 12 '13 at 15:07

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

• Oh wow. Thanks! – Calvin Lin Nov 28 '14 at 16:39
• @CalvinLin I modified the answer to make it clearer. – Tito Piezas III Nov 29 '14 at 20:40
• 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)? – Kieren MacMillan Jan 30 '18 at 19:03
• @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)$. – Tito Piezas III Jan 31 '18 at 15:10
• 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. ;) – Kieren MacMillan Feb 1 '18 at 2:53