# How do you find solutions to $2 x^2 +3 x +1 = y^2$ using integers for $x,y$

I am trying to solve an equation in integers to give a square number.

$$2 x^2 + 3 x +1 = y^2$$

while also satisfying $x=k^2 * n$ where $n$ is a very large integer given to us and $k$ can be any integer chosen to form a solution. The $y$ can be any integer needed to form a solution.

I am looking for a method to find solutions in integers only.

I am new to this kind of equation and can't tell easy from hard from impossible. This is not school work.

-
Is it $= y$ (as stated in title) or $= y^2$ (as stated in question)? – m0nhawk Jan 7 '13 at 8:30
alpertron is a webpage with a tool to solve such equations. you will also find a description of the methods used – miracle173 Jan 7 '13 at 10:30

Since $y^2=2x^2+3x+1=(2x+1)(x+1)$ and $(2x+1,x+1)=1$, we must have integers $p$ and $q$ so that $2x+1=p^2$ and $x+1=q^2$ (from whch we get $y=pq$).

Thus, we need to solve $$2q^2-p^2=1\tag{1}$$ In the standard way to solve the Pell's Equation, $\frac pq$ needs to be a continued fraction underestimate of $\sqrt2$. Computing the continued fraction yields $\sqrt2=(1;2)$. Thus, the approximants we want would be the underestimates, which happen every other approximant: \begin{align} (1)&=\frac11\Rightarrow x=0\quad\text{and}\quad y=1\\ (1,2,2)&=\frac75\Rightarrow x=24\quad\text{and}\quad y=35\\ (1,2,2,2,2)&=\frac{41}{29}\Rightarrow x=840\quad\text{and}\quad y=1189\\ (1,2,2,2,2,2,2)&=\frac{239}{169}\Rightarrow x=28560\quad\text{and}\quad y=40391 \end{align}\tag{2} We start with $$(p_0,q_0)=(1,1)\quad\text{and}\quad(p_1,q_1)=(7,5)\tag{3}$$ The continued fraction implies the recurrence $$(p_n,q_n)=6(p_{n-1},q_{n-1})-(p_{n-2},q_{n-2})\tag{4}$$ $(3)$ and $(4)$ yield the solution \begin{align} p_n&=\left({\tfrac12+\tfrac1{\sqrt2}}\right)\left(3+\sqrt8\right)^n +\left(\tfrac12-\tfrac1{\sqrt2}\right)\left(3-\sqrt8\right)^n\\ q_n&=\left(\tfrac12+\tfrac1{\sqrt8}\right)\left(3+\sqrt8\right)^n +\left(\tfrac12-\tfrac1{\sqrt8}\right)\left(3-\sqrt8\right)^n\\ \end{align}\tag{5} Since $x_n=q_n^2-1$ and $y_n=p_nq_n$, $(5)$ gives \begin{align} x_n&=\left(\tfrac38+\tfrac1{\sqrt8}\right)\left(17+6\sqrt8\right)^n +\left(\tfrac38-\tfrac1{\sqrt8}\right)\left(17-6\sqrt8\right)^n -\tfrac34\\ y_n&=\left(\tfrac12+\tfrac3{2\sqrt8}\right)\left(17+6\sqrt8\right)^n +\left(\tfrac12-\tfrac3{2\sqrt8}\right)\left(17-6\sqrt8\right)^n \end{align}\tag{6} which satisfy the recursions \begin{align} x_n&=35x_{n-1}-35x_{n-2}+x_{n-3}\\ y_n&=34y_{n-1}-y_{n-2} \end{align}\tag{7} Since $x^2-34x+1\,|\,x^3-35x^2+35x-1$, any sequence which satisfies the recurrence for $y_n$ satisfies the recurrence for $x_n$. Thus, we get all solutions to $y^2=2x^2+3x+1$ from $$(x_0,y_0)=(0,1)\quad(x_1,y_1)=(24,35)\quad(x_2,y_2)=(840,1189)\tag{8}$$ and the recurrence $$(x_n,y_n)=35(x_{n-1},y_{n-1})-35(x_{n-2},y_{n-2})+(x_{n-3},y_{n-3})\tag{9}$$

Second Condition

To have $x=nk^2$, while maintaining $x=q^2-1$, we need to have $$q^2-nk^2=1\tag{10}$$ This is Pell's Equation again. However, we are limited to using $q$ which also satisfy $(1)$. Thus, $q$ is a simultaneous solution to $(1)$ and $(10)$. I have not come up with a way to handle this in general.

A Guess using Borel-Cantelli

Looking at $(5)$, the density of solutions to $(1)$ is about $$\rho(n)=\frac1{n\log(3+\sqrt8)}\tag{11}$$ Although $\sqrt n$ may have a complicated continued fraction, the solutions to $(10)$ have a form similar to $(5)$. That is, the density of solutions is $O\left(\frac1n\right)$. Therefore, if the probability for a given $q$ to be a solution to $(1)$ is independent of to the probability of that same $q$ being a solution to $(10)$, then the probability of $q$ being a solution to both is $O\left(\frac1{n^2}\right)$. Since $\sum\limits_{n=1}^\infty\frac1{n^2}\lt\infty$, the Borel-Cantelli Lemma says that the probability that there is an infinite number of solutions, for a given $n$, is $0$.

Thus, it seems a good guess that there may be some isolated solutions, but for a given $n$, there are at most finitely many solutions.

-
Are you able to deal with the condition $x=k^2n$? – Calvin Lin Jan 8 '13 at 16:44
@CalvinLin: we have that $x=q^2-1$ and requiring that $x=nk^2$, we have $q^2-nk^2=1$. However, instead of all possible $q$ and $k$, the $q$ are limited to those from $(5)$. I have not looked beyond that. – robjohn Jan 8 '13 at 18:04
Agreed. However OP has a further criterion that $x= k^2 * n$ in the problem statement, which I have not been able to approach at all, apart from saying generate the list and pray for the best. – Calvin Lin Jan 8 '13 at 18:10
@CalvinLin: the best I can do at this time is to make a guess using the Borel-Cantelli Lemma. – robjohn Jan 9 '13 at 14:26

I'm assuming you want it to be a perfect square, otherwise the problem is trivial.

Notice that your equation is $(2x+1)(x+1) = y^2$. Since $\gcd (2x+1, x+1) = \gcd (x, x+1) = 1$, hence we need both $x+1$ and $2x+1$ to be perfect squares.

We thus want $(2x+1) - 2(x+1) = -1$. This is Pell's equation of the form $X^2 - 2Y^2 = -1$, and has solutions $X_k + \sqrt{2}Y_k = ( 7+ 5 \sqrt{2}) ( 3 + 2 \sqrt{2})^k$. I would suggest that you look determine this list first, and hence obtain all possible values of $x$ such that $2x^2 + 3x +1$ is a perfect square. For example, we have $(X_k, Y_k) = (7, 5), (41, 29), (239, 169), \ldots$ which gives $x = 24, 840, 28560, \ldots$. [I forgot the 'trivial solution $(1, 1)$ which yields $x=0$.]

Now, we also want $x+1 - x = 1$, which is of the form $X^2 - nY^2 = 1$ (Pell's equation). While this equation always has solutions in integers, it can be extremely hard to determine the initial (non-trivial) solution. Having done that, generate the list of possible $x$, and compare it to the previous list.

-

As a coda to the (excellent) answer of robjohn and using the notation given there, one is led to solve the system of equations $$2q^2-p^2= q^2-n k^2 =1.$$ For fixed $n$, such systems always have at most finitely many solutions, via an old theorem of Siegel (they define a genus $1$ curve, indeed an elliptic curve). In fact, one can find an absolute bound upon the number of solution triples $(p,q,k)$, independent of $n$ (probably, if we restrict to positive integers, a bound of $2$ suffices), in contrast to elliptic curves in Weierstrass form.

There are a number of methods for finding all such solutions, given $n$, ranging from elementary to less so (the standard algorithm uses lower bounds for linear forms in logarithms). Googling "simultaneous Pell equations'' is a good place to start.

-

For a small n =6 you have the solution x =24 y =35.

-
As $n=6$ hardly qualifies as "very large integer", this might rather be considered a comment – Hagen von Eitzen Jan 27 '13 at 12:21
Yes it was a comment. I do not usually look too much where exactly i post it. What is the difference and the exact limit between a comment and an answer? An answer is also a comment made by words and by equations. – user55514 Jan 27 '13 at 17:00