How many integers solutions does $x^2 + xy - y^2 = 1$ have? Also, if we know if a binary form represents an integer $n$, is there an algorithm to find all the solutions?
 A: 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...
A: 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)   $$
