How many integers solutions does $x^2 + xy - y^2 = 1$ have?

Question

Also, if we know if a binary form represents an integer $n$, is there an algorithm to find all the solutions?

Answer 1

Multiply equation with 4: $$4x^2+4xy-4y^2=4$$ so $$(2x+y)^2-5y^2=4$$

$$(2x+y-2)(2x+y+2)=5y^2$$ Clearly $\gcd(x,y)=1$. Let prime $p\mid \gcd(2x+y-2,2x+y+2)$

then $p\mid 4$ (so $p\mid y$). Let $y=2z$, so $$(x+z-1)(x+z+1)=5z^2$$

Let prime $q\mid \gcd(x+z-1,x+z+1)$, then $q\mid 2$ and thus $2\mid z$ and $2\mid x-1$. Now we have $z=2t$ and $x=2s+1$ so

$$(s+t)(s+t+1)=5t^2$$

Since $s+t$ and $s+t+1$ are consecutive we have $$s+t = a^2\;\;\wedge \;\;s+t+1=5b^2$$ or $$s+t = 5a^2\;\;\wedge \;\; s+t+1=b^2$$ where $a,b$ are relatively prime such that $t=ab$.

I believe you can finish from here...

Answer 2

There is a combination of algorithms that allow us to describe all such solutions. When the constant desired is $1,$ things are about as simple as this gets. If you have already found a solution $x^2 + xy - y^2 = 1,$ you get an infinite string of solutions by $$ (x,y) \mapsto (x+y, x+2y) $$

Beginning with $$ (1,0) \; , \; \; \; (1,1) \; , \; \; \; (2,3) \; , \; \; \; (5,8) \; , \; \; \; (13,21) \; , \; \; \; (34,55) \; , \; \; \; (89,144) \; , \; \; \; (233,377) \; , \; \; \; (610,987) \; , \; \; \; $$

As soon as the target number is not $\pm 1,$ we begin to need more than one such sequence of points...

For $x^2 + xy - y^2 = 31,$ one "orbit" is $$ (5,2) \; , \; \; \; (7,9) \; , \; \; \; (16,25) \; , \; \; \; (41,66) \; , \; \; \; (107,173) \; , \; \; \; (280,453) \; , \; \; \; (733,1186) \; , \; \; \; (1919,3105) \; , \; \; \; (5024,8129) \; , \; \; \; $$

For $x^2 + xy - y^2 = 31,$ the other orbit is $$ (5,3) \; , \; \; \; (8,11) \; , \; \; \; (19,30) \; , \; \; \; (49,79) \; , \; \; \; (128,207) \; , \; \; \; (335,542) \; , \; \; \; (877,1419) \; , \; \; \; (2296,3715) \; , \; \; \; (6011,9726) \; , \; \; \; $$

Together, these give all solutions with both $x,y,>0.$ To find the solutions with negative values, take the inverse mapping, namely $$ (x,y) \mapsto (2x-y, -x+y) $$