# Find all integer solutions for the equation $|5x^2 - y^2| = 4$

In a paper that I wrote as an undergraduate student, I conjectured that the only integer solutions to the equation $$|5x^2 - y^2| = 4$$ occur when $x$ is a Fibonacci number and $y$ is a Lucas number. I was able to prove that when $x$ was a Fibonacci number there existed a Lucas number $y$ such that $|5x^2 - y^2| = 4$. This is easily shown with Cassini's Identity $$F_{n-1}F_{n+1} - F_{n}^2 = (-1)^n$$

The challenge is this ... prove (or disprove) that these are the ONLY solutions.

By the way, this is how I generated the Diophantine equation. $$F_{n-1}F_{n+1} - F_{n}^2 = (-1)^n$$ $$F_{n-1}(F_{n}+F_{n-1}) - F_{n}^2 = (-1)^n$$ $$F_n^2 - F_{n-1}F_n-F_{n-1}^2+(-1)^n=0$$ because $F_n \gt \frac{F_{n-1}}{2}$ $$F_n=\frac{F_{n-1} + \sqrt{F_{n-1}^2-4((-1)^n-F_{n-1}^2)}}{2}=\frac{F_{n-1} + \sqrt{5F_{n-1}^2+4((-1)^{n+1})}}{2}$$ Letting $y= \pm \sqrt{5F_{n-1}^2+4((-1)^{n+1})}$ and $x=F_{n-1}$ we have $$y= \pm \sqrt{5x^2+4((-1)^{n+1})}$$ $$y^2= 5x^2 \pm 4$$ $$|5x^2 - y^2| = 4$$

-
I found this solution from Dalhousie University in Halifax, Nova Scotia (which is similar to Ricardo Buring's solution). See page 91 of this pdf. link. This appeared in the June 1968 edition of the Fibonacci Quarterly (Volume 6, Number 3). Full editions of the Fibonacci Quarterly can be downloaded here link – John Joy Apr 10 '14 at 21:19
Except for $x=0, y= \pm 2,$ those are all solutions. – Will Jagy Apr 16 '14 at 22:48
There is a lot of inconsistency in the literature concerning whether or not $L_0$ and $F_0$ are included in their respective sequences. Whether $(0, \pm 2)$ is a counter example or not depends on how you define the sequences. – John Joy Apr 19 '14 at 2:18
John, that's fine, it appears we can have $2$ as the Lucas number before $1,$ as in $2,1,3,4,7.$ In any case, we do know all solutions. – Will Jagy Apr 19 '14 at 2:30

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]$.

-
I have no idea what you just wrote. I have some reading to do, and I'm sure that I'll understand your answer in 2-3 weeks. In the mean time, you get the green check mark :) Thanks for pointing me in the right direction. – John Joy Apr 10 '14 at 13:47

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.

-