3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $2x^2+x+1=k^2$ becomes $4x^2+2x+2=2k^2$, i.e. $(2x+1/2)^2+1.75=2k^2$, i.e. $(4x+1)^2+7=8k^2$. Generally, multiply both sides of $ax^2+bx+c=k^2$ by something to make $a$ a square, then complete the square, multiply both sides by something to make everything integers. $\endgroup$ – user236182 Oct 25 '15 at 0:10
  • $\begingroup$ If $a$ is a square, you might be able to prove $(\sqrt{a}x+k)^2<ax^2+bx+c<(\sqrt{a}x+k+1)^2$ for some $k\in\Bbb Z$, which proves no solutions exist. $\endgroup$ – user236182 Oct 25 '15 at 0:12
  • $\begingroup$ @user236182 This is useful, but what to do with the $7$ left over? I know there are special cases for $\pm 2, \pm 4$. $\endgroup$ – qwr Oct 25 '15 at 0:36
  • $\begingroup$ You can solve $x^2-dy^2=k$ with $d$ square-free for any integer $k\neq 0$. If a solution exists, then exist infinitely many solutions. Let $(x_k,y_k)$ be the minimal solution of $x^2-dy^2=k$ and let $(x_1,y_1)$ be the minimal solution of $x^2-dy^2=1$. Note $\left(a^2-db^2\right)\left(e^2-df^2\right)=(ae+dbf)^2-d(be+af)^2$. Define $(a,b)\otimes (e,f)=(ae+dbf,be+af)$. Then all positive integer solutions are given by $(x_k,y_k)\otimes (x_1,y_1)^n$ with $n\ge 0$. $\endgroup$ – user236182 Oct 25 '15 at 0:54
  • $\begingroup$ @user236182 Your comments have essentially answered the question. I've asked this last question, but do you mind posting the comments together as an answer so I can accept it? $\endgroup$ – qwr Oct 25 '15 at 2:04
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do you mind updating your answer so that it includes all the steps to solve the general equation? $\endgroup$ – qwr Dec 7 '15 at 19:14
  • $\begingroup$ @qwr , putting all the steps is not possible. I show a good portion of the issues in learning Conway's picture method in the several answers linked in. Both Conway and Stillwell prove that the river is periodic, but neither goes so far as to emphasize how all solutions may be found by applying "automorphisms" to the finite set of solutions in a single period, so I push that aspect pretty hard. $\endgroup$ – Will Jagy Dec 7 '15 at 20:29
  • $\begingroup$ I'm just trying to make sense of Alpern's sea of variables, which appears (I'm not sure) to be the same thing but with far more algebra invovled $\endgroup$ – qwr Dec 8 '15 at 4:47
  • $\begingroup$ @qwr , if you begin with $Ax^2 + Bx + C = k^2$ as you initially wrote, you will always arrive at a Pell type equation, $(2Ax + B)^2 - (4A)k^2 = B^2 - 4 AC$ is what you expect when $B$ is odd. Find all solutions to $y^2 - (4A)k^2 = B^2 - 4 AC,$ allowing $y$ both positive and negative, select those that can be written as $2Ax+B.$ What is your own background, and why do you want to know more detail about this topic? $\endgroup$ – Will Jagy Dec 8 '15 at 5:01
  • $\begingroup$ I have no background in number theory and I only know some basic calculus. I am interested in learning more about number theory. $\endgroup$ – qwr Dec 11 '15 at 5:08

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.