Find all integer solutions for the equation $|5x^2 - y^2| = 4$
Let me interchange $x$ and $y$ for my own convenience. We want to solve $$x^2 - 5y^2 = \pm 4$$ over the integers.
Solving these equations corresponds to finding the elements of norm $\pm 4$ in the quadratic integer ring $\mathbf{Z}[\sqrt{5}]$, where the norm is the function given by $$N(x+\sqrt{5}y) = (x+\sqrt{5}y)(x-\sqrt{5}y) = x^2 - 5y^2.$$
Finding these elements is an exercise in algebraic number theory. The real quadratic number field $\mathbf{Q}(\sqrt{5})$ has $\mathbf{Z}[\omega]$ with $\omega = (1+\sqrt{5})/2$ as its ring of integers, and $\mathbf{Z}[\sqrt{5}]$ is a subring of this. The field norm on $\mathbf{Q}(\sqrt{5})$ agrees with the norm given above for elements of $\mathbf{Z}[\sqrt{5}]$.
Lemma I.7.2 in Neukirch's Algebraic Number Theory yields that up to multiplication by units in $\mathbf{Z}[\omega]$, there are only finitely many elements of a given norm in $\mathbf{Z}[\omega]$. Since $\mathbf{Z}[\sqrt{5}] \subset \mathbf{Z}[\omega]$ and the norms agree, up to multiplication by units in $\mathbf{Z}[\omega]$ there are only finitely many elements of norm $4$ in $\mathbf{Z}[\sqrt{5}]$.
By Dirichlet's unit theorem the group of units of $\mathbf{Z}[\omega]$ has rank $1$. A generator of this group, or a fundamental unit of $\mathbf{Q}(\sqrt{5})$, is given by $$\varepsilon = \frac{1+\sqrt{5}}{2},$$ which has norm $-1$.
Since the norm of an element $\alpha$ is the same as the norm of the principal ideal $(\alpha)$, it is useful to determine the number of ideals of norm $4$ in $\mathbf{Z}[\omega]$. By this answer to an other question this number is $$\sum_{m|4} \chi(m) = \chi(1) + \chi(2) + \chi(4) = \left(\frac{1}{5}\right) + \left(\frac{2}{5}\right) + \left(\frac{4}{5}\right) = 1 - 1 + 1 = 1.$$
Hence if $\alpha, \beta$ are two elements of norm $4$, then $(\alpha) = (\beta)$, so $\beta = u\alpha$ for a unit $u$. That is, up to multiplication by units in $\mathbf{Z}[\omega]$ there is only one element $\alpha$ of norm $4$.
Take $\alpha = 2$; then all the elements of norm $4$ in $\mathbf{Z}[\omega]$ are given by $2\varepsilon^n$, for integer $n$. But since $2\mathbf{Z}[\omega] \subset \mathbf{Z}[\sqrt{5}]$, all of these elements in fact belong to $\mathbf{Z}[\sqrt{5}]$. Hence all the solutions to the original equation are the $(x_n, y_n)$ given by $2\varepsilon^n = x_n + \sqrt{5}y_n$.
From the identity $\varphi^n = \frac{L_n + \sqrt{5}F_n}{2}$ of real numbers for nonnegative $n$ mentioned at the end of this section of the Wikipedia article on Lucas numbers it follows that $$2\varepsilon^n = L_n + \sqrt{5}F_n$$ for nonnegative $n$.
For negative $n$ you get extra solutions like $(1,-1)$ and $(-3,1)$, but you could have predicted those from the beginning: if $(x,y)$ is a solution, then so are $(-x,y)$, $(x,-y)$ and $(-x,-y)$.
I should mention that with SAGE you can do calculations in $\mathbf{Q}(\sqrt{5})$,
K.<s> = QuadraticField(5)
eps = (1+s)/2 # = K.units()[0]
for n in range(0,15):
print 2*eps^n
and also with Fibonacci and Lucas numbers:
for n in range(0,15):
print (fibonacci(n), lucas_number2(n,1,-1))
These two pieces of code give the same output (up to formatting).
Edit (01/11/14): A more elementary way to see that there is only one ideal of norm 4 in $\mathbf{Z}[\omega]$ is as follows:
The quadratic field $\mathbf{Q}(\sqrt{5})$ has discriminant $5$ and has no complex embeddings; hence by this inequality we have $N(I) \geq N(x)/\sqrt{5}$ for any ideal $I$ and element $x \in I$. Since $\mathbf{Z}[\omega]$ is a Dedekind domain we have unique factorization of ideals into primes. For a prime $\mathfrak{p} \subset \mathbf{Z}[\omega]$ lying over $p$ we get $N(\mathfrak{p}) \geq p^2/\sqrt{5}$. Since $p^2/\sqrt{5} > 4$ for $p > 2$, the primes of norm at most $4$ must lie over $2$. The minimal polynomial $X^2 - X - 1$ of $\omega$ is irreducible mod $2$, so $2$ is inert in $\mathbf{Z}[\omega]$ by the Kummer-Dedekind theorem. That is, $(2)$ is the only prime with norm at most $4$, and its norm is exactly $4$. By unique factorization into primes and multiplicativity of the norm, $(2)$ is the only ideal of norm $4$ in $\mathbf{Z}[\omega]$.
EDIT, January 2015: Conway's little book is available at http://www.maths.ed.ac.uk/~aar/papers/conwaysens.pdf
I also put four related excerpts, all with the prefix indefinite_binary, at OTHER. Dmitry says the computer zakuski is being decommissioned, hope it continues to work through late January. I especially like Stillwell's presentation. Put it all together, for a Pell form, indeed any form $a x^2 + b xy + c y^2$ with $a > 0, \; b \geq 0, \; c < 0,$ but $b^2 - 4ac$ not a perfect square, we get a diagram that shows all of Conway's information, along with the $(x,y)$ pairs as column vectors, with an explicit illustration of the (proper) automorphism group generator, that being the mapping $(x,y) \mapsto (9x+20y,4x+9 y). $
Did not notice this one ten days ago. There is an explicit structure for representing a number by an indefinite quadratic form. This is chapter one in Conway's The Sensual Quadratic Form. I wrote a little program recently, and no longer make simple arithmetic mistakes in these.
It turns out that all occurrences of $\pm 4$ happen along the "river" for $x^2 - 5 y^2. $
Given any solution to $x^2 - 5 y^2 = \pm 4,$ we gat the same value by switching $(x,y)$ to $$ (9x+20y,4x+9 y). $$ The two by two matrix causing this transformation (on column vectors) is $$ A \; = \; \left( \begin{array}{rr} 9 & 20 \\ 4 & 9 \end{array} \right) , $$ which you can see towards the right of the diagram as the coordinates of the final $1$ and then the final $-5,$ placed side by side. The big theorem is that the entire diagram is periodic. I find the finite set of representatives within one cycle, apply the transformation I wrote arbitrarily many times, and i get all. As there is no $xy$ term in $x^2 - 5 y^2,$ there is a simple $\pm$ symmetry as well.
So, all solutions to $x^2 - 5 y^2 = \pm 4 $ are:
Imprimitive:
+4: $$(2,0), (18,8), (322,144), (5778,2584), (103682,46368), (1860498,832040),\ldots, $$
-4: $$(-4,2), (4,2), (76,34), (1364,610), (24476,10946), (439204,196418),\ldots, $$
Primitive:
+4: $$(3,-1), (7,3), (123,55), (2207,987), (39603,17711), (710647,317811), \ldots, $$
+4: $$(3,1), (47,21), (843,377), (15127,6765), (271443,121393), \ldots, $$
-4: $$(-1,1), (11,5), (199,89), (3571,1597), (64079,28657), (1149851,514229), \ldots, $$
-4: $$(1,1), (29,13), (521,233), (9349,4181), (167761,75025), \ldots, $$
For any position in these sequences, there is a degree two recursion given by
$$ a_{n+2} = 18 a_{n+1} - a_n. $$ For example, $18 \cdot 29 - 1 = 521,$ then $18 \cdot 521 - 29 = 9349. $
Let's see, 3:21 pm. Both Fibonacci and Lucas do the same thing (by six positions), as $$ F_{n+12} = 18 F_{n+6} - F_n, $$ $$ L_{n+12} = 18 L_{n+6} - L_n. $$ So, if the six orbits above satisfy the desired Fibonacci/Lucas conditions, that is a complete proof. If so, one could, carefully, interleave the six orbits in numerical order, perhaps using only the ones with strictly positive entries. See whether that works:
$$ (1,1),(3,1),(4,2),(7,3),(11,5), (18,8),$$ $$ (29,13),(47,21),(76,34),(123,55),(199,89), (322,144),$$ $$(521,233),(843,377),(1364,610),(2207,987),(3571,1597),(5778,2584), $$ $$(9349,4181),(15127,6765),(24476,10946),(39603,17711),(64079,28657),(103682,46368), $$ $$ (167761,75025),(271443,121393),(439204,196418),(710647,317811),(1149851,514229),(1860498,832040), $$ Yep. The only miss is $(2,0),$ as $2$ is not a Lucas number. CORRECTION, FEB. 2015: as is commented elsewhere, it appears fairly common for people to define Lucas number $L_0 = 2,$ http://en.wikipedia.org/wiki/Lucas_number
Ummm; as you can see, $(x,y)$ and $(x,-y)$ may be distinct as far as the orbits, the six lists i wrote.
There is plenty more that could be said; anyway, these give all solutions. Oh, the other business, the "climbing lemma," says that values only increase (in absolute value) when leaving the river. The next layers of values are $\pm 11$ at the continuation of each edge with a light blue $6,$ and $\pm 19$ at the continuation of each edge with a light blue $10.$ So we have done enough to catch all $\pm 4$ already.
If no enough basic knowledge, we can also directly caculate.
If $(x_0,y_0),(x_1,y_1)$ solved $x^2-5y^2 = \pm 4$
$ 1 = \frac{x_0^2-5y_0^2}{x_1^2-5y_1^2}$
$ = \frac{x_0+\sqrt{5}y_0}{x_1+\sqrt{5}y_1} \cdot \frac{x_0-\sqrt{5}y_0}{x_1-\sqrt{5}y_1} $
$ = \frac{(x_0+\sqrt{5}y_0)(x_1-\sqrt{5}y_1)}{x_1^2-5y_1^2} \cdot \frac{(x_0-\sqrt{5}y_0)(x_1+\sqrt{5}y_1)}{x_1^2-5y_1^2} $
$ = \frac{(x_0x_1-5y_0y_1)+\sqrt{5}(y_0x_1-x_0y_1)}{4} \cdot \frac{(x_0x_1-5y_0y_1)-\sqrt{5}(y_0x_1-x_0y_1)}{4} $
$ = (\frac{x_0x_1-5y_0y_1}{4})^2+\sqrt{5}(\frac{y_0x_1-x_0y_1}{4})^2$
if $ y_0x_1-x_0y_1 = 0 \pmod 4 $ then $ (\frac{x_0x_1-5y_0y_1}{4},\frac{y_0x_1-x_0y_1}{4})$ satisfy $x^2 - 5y^2 = 1$ which is pell's equation
so we can group $(x,y)$ into different group, (if exist)
$(4k_0,4k_1+2),(4k_0+2,4k_1)$
$(4k_0+1,4k_1+1),(4k_0+3,4k_1+3)$
$(4k_0+1,4k_1+3),(4k_0+3,4k_1+1)$
$(4k_0+2,4k_1+2),(4k_0+4,4k_1+4)$
Note that $(4k_0+2,4k_1+2),(4k_0+4,4k_1+4)$ if exist, it can be same group with above group. When $(4k_0+3,4k_1+3)$ be the same group with $(4k_0+2,4k_1+2)$ and $(4k_0+1,4k_1+3)$ be the same group with $(4k_0+2,4k_1+2)$, but $(4k_0+1,4k_1+3)$ and $(4k_0+3,4k_1+3)$ can never be in same group, so some group may have no answer. So I split it out.
The base answer for $x^2-5y^2=1$ is $(9,4)$
so if $(x,y)$ is the answer for $x^2-5y^2=-4$ , ($x^2-5y^2=4$ can be solved same way)
the next answer in its group will be get from $(x+\sqrt{5}y)(9+4\sqrt{5}) = (9x+20y) + \sqrt{5}(9y+4x)$,which is $(9x+20y,9y+4x)$
the previous answer in its group will be get from $(x+\sqrt{5}y)(9+4\sqrt{5})^{-1} = (9x-20y) + \sqrt{5}(9y-4x)$,which is $(9x-20y,9y-4x)$
we only care about $x>0,y>0$, In each group we have the the smallest positive solutions.
so the smallest answer satisfy $9x-20y \le 0$ or $9y-4x \le 0$
$\frac{x}{y} \le \frac{20}{9}$ or $\frac{x}{y} \ge \frac{9}{4}$
$\sqrt{5- \frac{4}{y^2}} \le \frac{20}{9}$ or $\sqrt{5- \frac{4}{y^2}} \ge \frac{9}{4}$
$0.894427 \le y \le 8.04984 $
so we can just test $y$ from 1 to 8, and we will find 3 base answer for $x^2-5y^2=-4$ , $(x,y) = (1,1),(4,2),(11,5)$
if $x^2-5y^2=4$,the above ineqution become $\sqrt{5 + \frac{4}{y^2}} \le \frac{20}{9}$ or $\sqrt{5 + \frac{4}{y^2}} \ge \frac{9}{4}$
$0<y \le 8$
so we can just test $y$ from 1 to 8, and we will find 3 base answer for $x^2-5y^2=4$ , $(x,y) = (3,1),(7,3),(18,8)$
all other answers can be generate by $(x+\sqrt{5}y)(9+4\sqrt{5})^n$ , $n$ can be positive or negative integer