9
$\begingroup$

If I have a quadratic form like $y^2 - x^2 - x = k$ none of the techniques I know work because of the nasty $x$. Note that homogenizing doesn't work because a solution of $Y^2 - X^2 - X Z = k Z^{(2)}$ does not lead to a solution of the original equation in integers, at least as far as I have been able to determine.

How does one understand the solution set of these equation? How can I solve them?

$\endgroup$
1

3 Answers 3

Reset to default
20
$\begingroup$

Over 200 years ago Lagrange solved the general binary quadratic Diophatine equation

$$\rm a\ x^2 + b\ xy + c\ y^2 + d\ x + e\ y + f = 0 $$

It reduces to a Pell equation: put $\rm\ D = b^2-4ac,\ E = bd-2ae,\ F = d^2-4af\:.\ $ Then

$$\rm D\ Y^2\ =\ (D\ y + E)^2 + D\ F - E^2,\quad\quad Y\ =\ 2ax + by + d $$

Therefore if we put $\rm\quad\ \ X = D\ y + E,\quad\ \ N = E^2 - D\ F\quad\ \ $ we have the Pell equation

$$\rm X^2 - D\ Y^2\ =\ N $$

Dario Alpern has a web page Quadratic two integer variable equation solver that will solve any such equation - with complete descriptions of the methods involved. For some recent optimizations of Lagrange's algorithm see this paper H. C. Williams et al. A new look at an old equation.

$\endgroup$
1
  • $\begingroup$ In particular, consider the equation \begin{equation} 4a(b^2-4ac)(ax^2+bxy+cy^2+dx+ey+f) = 0, \end{equation} where $a,b,c,d,e,f$ are arbitrary. As long as $a(b^2-4ac) \ne 0$, we can assume $ax^2+bxy+cy^2+dx+ey+f=0$, and we have the Pell equation \begin{align*} \bigl((b^2-4ac)y-2ae+bd\bigr)^2 - (b^2-4ac)(2ax+by+d)^2 &= 4a(ae^2+b^2f+cd^2-bde-4acf). \end{align*} $\endgroup$
    – Kieren MacMillan
    Sep 26, 2014 at 13:37
4
$\begingroup$

These all reduce to equations $$f(x,y)=k$$ where $x$ and $y$ are integers, possibly satisfying some congruence conditions, and $f$ is a homogeneous quadratic form. In two variables this basically comes down to solving norm equations in the rings of integers in quadratic fields. For your example you get $$4y^2-4x^2-4x-1=4k-1$$ that is $$y'^2-x'^2=4k-1$$ where $x'=2x-1$ is odd and $y'=2y$ is even. This is atypically easy, since it factorizes as $(y'-x')(y'+x')=4k-1$. More typically you'd get a Pell-type equation.

$\endgroup$
3
  • $\begingroup$ "atypically easy" - :D $\endgroup$
    – J. M. ain't a mathematician
    Nov 7, 2010 at 13:58
  • $\begingroup$ Thanks for this answer. Why/how would I get $4y^2-4x^4-4x-1=4k-1$! $\endgroup$
    – anon
    Nov 7, 2010 at 14:00
  • $\begingroup$ @muad: multiply by 4 and subtract 1 from both sides. That lets you factor 4x^2 + 4x + 1 to get rid of the linear term. $\endgroup$
    – Qiaochu Yuan
    Nov 7, 2010 at 15:00
0
$\begingroup$

The idea is to write the original equation and then try to match coefficients. The method is not perfect but it may work in a number of cases.

$\endgroup$
1

You must log in to answer this question.