General method for determining if $Ax^2 + Bx + C$ is square

Is there a general method for solving Diophantine equations in the form $Ax^2 + Bx + C = k^2$, preferably turning them into Pell's equations, when possible? For example, $2x^2 + x + 1 = k^2$ or $5x^2 + 2x + 1 = k^2$. Certain cases have special solutions, but I cannot figure out how these are derived beyond a simple completing the square approach.

A general method for solving the hyperbolic equation $Ax^2 + Bxy + Cy^2 + F = 0$ is given by Dario Alejandro Alpern.


Solution 1:

The comments you have been given are almost correct. Once you get to $$ x^2 - d y^2 = k, $$ you do need to find the minimal solution to $U^2 - d V^2 = 1,$ that is with both $U,V > 0.$ The generator of the (oriented) automorphism group of $x^2 - d y^2$ is then $$ A = \left( \begin{array}{cc} U & dV \\ V & U \end{array} \right). $$ Notice that this has determinant $1,$ with trace $2U.$ The Cayley-Hamilton theorem says, quite correctly, $A^2 - 2 U A + I = 0,$ so $A^2 = 2 U A - I.$

We need to know only one orientation reversing automorphism, which is just $$ (x,y) \mapsto (x,-y) $$

Now, all the solutions for some $k$ are produced by using $A.$ The detail that gets glossed over is that we may require more than one or two "seed" solutions.

Let us display all solutions to $x^2 - 2 y^2 = 119 = 7 \cdot 17.$ For any solution $(x,y),$ we really do get a sequence of new solutions by taking $$ (x,y) \mapsto (3x+4y,2x+3y), $$ which comes from $U = 3, V = 2,$ so this time $$ A = \left( \begin{array}{cc} 3 & 4 \\ 2 & 3 \end{array} \right). $$

This is indicated in the comments.

The trick is that we need four seed solutions.

In all four of the following sequences of solutions, we get, from Cayley-Hamilton applied to $A,$ giving $A^2 = 6 A - I,$ we get $$ x_{n+2} = 6 x_{n+1} - x_n, $$ $$ y_{n+2} = 6 y_{n+1} - y_n. $$ If we intertwine the four sequences things do not look that simple.

$$ ................................ $$ $$ (11,1) $$ $$ (37,25) $$ $$ (211,149) $$ $$ (1229,869) $$ $$ ................................ $$ $$ (11,-1) $$ $$ (29,19) $$ $$ (163,115) $$ $$ (949,671) $$ $$ (5531,3911) $$ $$ ................................ $$ $$ (13,5) $$ $$ (59,41) $$ $$ (341,241) $$ $$ (1987,1405) $$ $$ ................................ $$ $$ (13,-5) $$ $$ (19,11) $$ $$ (101,71) $$ $$ (587,415) $$ $$ (3421,2419) $$ $$ ................................ $$

Afterthought: when $k=1$ the only seed required is $(1,0).$ When $k=-1$ or $k=p$ or $k = -p$ only two seeds are required, some $(B,C)$ and $(B,-C).$ It is when $k$ (well, squarefree) is the product of primes that are represented by $x^2 - d y^2$ that we require more than two seed solutions. Note that both $x^2 - 2 y^2 = 7$ and $x^2 - 2 y^2 = 17$ have solutions.

Here are all the solutions to $x^2 - 2 y^2 = 119$ with $x,y > 0$ and $y < 12000,$ in numerical order:

 x: 11     y: 1
 x: 13     y: 5
 x: 19     y: 11
 x: 29     y: 19
 x: 37     y: 25
 x: 59     y: 41
 x: 101     y: 71
 x: 163     y: 115
 x: 211     y: 149
 x: 341     y: 241
 x: 587     y: 415
 x: 949     y: 671
 x: 1229     y: 869
 x: 1987     y: 1405
 x: 3421     y: 2419
 x: 5531     y: 3911
 x: 7163     y: 5065
 x: 11581     y: 8189

Note, December. Over a few years of posting related answers, I have settled on my favorite way to present Conway's Topograph method so as to show the generator ($A$) of the automorphism group of the form, an infinite cyclic subgroup of $SL_2 \mathbb Z.$ Neither Conway's book nor Stillwell's chapter emphasize that aspect of it. I have also settled on a version of the picture of the river that I like, a straight line with trees growing up, in the direction of positive values of $x^2 - d y^2$ or other quadratic binary form, then trees growing down in the direction of negative values.

Here are some previous MSE questions and answers.

http://www.maa.org/press/maa-reviews/the-sensual-quadratic-form

Here is a preview for Conway's book, set to the page with the Climbing Lemma

At the moment, Conway's entire book is available as a pdf here

http://www.springer.com/gp/book/9780387955872

A few of the relevant pages in Stillwell are viewable, really everything in pages 87-100 relates. I found this very helpful in clarifying things.

Another quadratic Diophantine equation: How do I proceed?

How to find solutions of $x^2-3y^2=-2$?

Generate solutions of Quadratic Diophantine Equation

Finding all solutions of the Pell-type equation $x^2-5y^2 = -4$

Find all integer solutions for the equation $|5x^2 - y^2| = 4$

Maps of primitive vectors and Conway's river, has anyone built this in SAGE?

Infinitely many systems of $23$ consecutive integers

Finding integers of the form $3x^2 + xy - 5y^2$ where $x$ and $y$ are integers, using diagram via arithmetic progression

Small integral representation as $x^2-2y^2$ in Pell's equation

Solving the equation $ x^2-7y^2=-3 $ over integers