# Generating integer solutions to $4mn - m^2 + n^2 = ±1$

How can I generate positive integer solutions to $m$ and $n$ that satisfy the equation:

$4mn - m^2 + n^2 = ±1$,

subject to the constraints that $m$ and $n$ are coprime, $m-n$ is odd and $m > n$.

-
Hint: Complete the square and you get an equation of the form $x^2-Dy^2=\pm 1$ –  Thomas Andrews Aug 27 '12 at 14:01

Hint: Completing the square yields an equation of the form: $$x^2-Dy^2=\pm 1$$ for a particular $D$.

There's actually a simple recursion that generates all solutions.

Let $a_0=0$, $a_1=1$, and $a_{k+2}=4a_{k+1}+a_{k}$. Then the general solution is $(m,n)=(a_{k+1},a_{k})$.

This gives the positive solutions. The solutions with $n$ negative are of the form $(m,n)=(a_k,-a_{k+1})$.

There are no solutions with $m$ negative and $m> n$

-
Can you explain the completing the square method in this case? I'm not sure what value I should add and subtract exactly –  Khaled Aug 27 '12 at 15:44
@Khaled Perhaps it is easier to see how to complete the square if you rewrite the left side as $n^2+4mn - m^2$ –  Thomas Andrews Aug 27 '12 at 15:48
Got it! Thank you for your answer –  Khaled Aug 27 '12 at 16:06