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