Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks for your help.

share|improve this question
2  
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

4 Answers 4

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.

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.