DIOPHANTINE EQUATIONS, FIBONACCI HYPERBOLAS, AND QUADRATIC FORMS

Keith Brandt and John Koelzer

1. Introduction. In Mathematical Diversions [4], Hunter and Madachy ask for the ages of a boy and his mother, given the following:

His mother’s age and his, when multiplied together, come to one more than the square of their difference.

We used this problem in a contest for our students. While reviewing the solutions submitted, we discovered some oddities about this question and its corresponding Diophantine equation. All integer solutions to the equation, and those of an incorrect formulation of the equation, consist of Fibonacci numbers. Furthermore, there is an interesting duality between the solutions to the correct and incorrect formulations.

2. The Equations. Let x and y represent the ages of the boy and his mother, respectively. The question leads to the equation

xy = 1 + (x − y)^{2},

which simplifies to

x^{2} − 3xy + y^{2} = −1.  (1)

One of the solutions submitted had the 1 on the wrong side of the equation,

xy + 1 = (x − y)^{2},

which simplifies to

x^{2} − 3xy + y^{2} = 1.  (2)

Figure 1. The curves defined by xy = 1 + (x − y)^{2} (solid) and xy + 1 = (x − y)^{2} (dashed).

The substitutions u = 2x − 3y and v = y reduce equations (1) and (2), respectively, to

u^{2} − 5v^{2} = −4  (3)

and

u^{2} − 5v^{2} = 4,  (4)

which are versions of Pell’s equation [10]. With these substitutions it is easy to convert between solutions of equations (1) and (2) and solutions of equations (3) and (4).

3. The Solutions. Write the equation x^{2}+axy+y^{2} = b as x^{T} Ax = b, where

x [ \begin{matrix}x \\ y \end{matrix} ] and A = [ \begin{matrix}1 & \frac{a}{2} \\ \frac{a}{2} & 1 \end{matrix} ] ,

and apply the following theorem.

\underline{Theorem 1}. Consider the equation x^{T} Ax = b, where A is a square matrix, x is a column vector, and b ∈ ℝ. Suppose P is a matrix with integer entries such that P^{T} AP = A. If x is a solution to the equation, then P x is also a solution. If P has an inverse, then P^{−1}x is also a solution.

\underline{Proof}. (P x)^{T} A(P x) = x^{T} P^{T} AP x = x^{T} Ax = b. If P has an inverse, then (P^{−1})^{T} A (P^{−1}) = A, and it follows that (P^{−1}x)^{T} A(P^{−1}x) = x^{T} (P^{−1})^{T} AP^{−1}x = x^{T} Ax = b.

The matrix

P = [ \begin{matrix}−a & −1 \\ 1 & 0 \end{matrix} ]

satisfies the hypothesis of Theorem 1. Setting a = −3 and b = −1 gives the equation for the mother-son age problem. Since

[ \begin{matrix}x \\ y \end{matrix} ] = [ \begin{matrix}1 \\ 1 \end{matrix} ]

is a solution to equation (1), all elements of the set

K^{+} = \{x_{k} = [ \begin{matrix}x_{k} \\ y_{k} \end{matrix} ] = P^{k} · [ \begin{matrix}1 \\ 1 \end{matrix} ] |k ∈ ℤ\}

are solutions to equation (1).

Similarly, there is a set K^{−} of solutions corresponding to the solution

[ \begin{matrix}x \\ y \end{matrix} ] = [ \begin{matrix}−1 \\ −1 \end{matrix} ] .

The sets K^{+} and K^{−} give solutions on the two branches in quadrants one and three, respectively, of the hyperbola defined by equation (1). For any k ∈ ℤ and x_{k}, x_{k−1} ∈ K^{+} (or K^{−}), Theorem 1 yields

x_{k} = P x_{k−1}.  (5)

Note that P is diagonalizable via the similarity transformation P = QDQ^{−1}, where

D = [ \begin{matrix}\frac{3−\sqrt{5}}{2} & 0 \\ 0 & \frac{3+\sqrt{5}}{2} \end{matrix} ]

and

Q = [ 1 1^{\frac{3−\sqrt{5}}{2} \frac{3+\sqrt{5}}{2}} ] .

Letting x_{k} ∈ K^{+} and substituting into the recursive equation (5) above gives

x_{k} = P x_{k−1} = P^{k}x_{0} = QD^{k}Q^{−1}x_{0}.

Note that if ϕ is defined to be \frac{1+\sqrt{5}}{2} (the Golden Ratio), then

ϕ^{2} = \frac{3 + \sqrt{5}}{2} and ϕ^{−2} = \frac{3 − \sqrt{5}}{2}.

Substitution of these values into D and Q leads to formulas for x_{k} and y_{k}:

\begin{aligned}x_{k} & = \frac{ϕ^{−2k} + ϕ^{2k+2}}{1 + ϕ^{2}} \\ y_{k} & = \frac{ϕ^{−2k+2} + ϕ^{2k}}{1 + ϕ^{2}} . \end{aligned}

These formulas are related to the sequence of Fibonacci numbers, F_{n}. This sequence is defined by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1}+F_{n−2} for n ≥ 2. The definition can be extended to negative integers n by F_{−n} = (−1)^{n+1}F_{n}. Binet’s familiar formula [2] for the k^{th} Fibonacci number is

F_{k} = \frac{1}{\sqrt{5}}(ϕ^{k} − (−1)^{k}ϕ^{−k}), k ∈ ℤ.

Replacing k by 2k + 1 and noting that \frac{ϕ}{1 + ϕ^{2}} = \frac{1}{\sqrt{5}} yields

F_{2k+1} = \frac{ϕ}{1 + ϕ^{2}} (ϕ^{2k+1} − (−1)^{2k+1}ϕ^{−2k−1})

= \frac{ϕ^{−2k} + ϕ^{2k+2}}{1 + ϕ^{2}}

= x_{k}.

The proof that y_{k} = F_{2k−1} is similar. Thus, the solutions to equation (1) include pairs of Fibonacci numbers whose indices run over the odd integers. In fact, these are all the solutions to the equation.

The matrices

C = [ \begin{matrix}2 & −3 \\ 0 & 1 \end{matrix} ] and C^{−1} = [ 0 1^{\frac{1}{2} \frac{3}{2}} ]

are used to convert between solutions to equations (1) and (3). For example,

[ \begin{matrix}5 \\ 2 \end{matrix} ]

is a solution to (1), and

[ \begin{matrix}2 & −3 \\ 0 & 1 \end{matrix} ] · [ \begin{matrix}5 \\ 2 \end{matrix} ] = [ \begin{matrix}4 \\ 2 \end{matrix} ] ,

which is a solution to (3).

Note that solutions to (3) must consist of either two even integers or two odd integers. Thus, multiplying any solution of (3) by C^{−1} gives an integral solution to (1). It follows that there is a one-to-one correspondence between the solutions to equations (1) and (3).

Standard results on Diophantine equations will now reveal that the set K = K^{+} ∪ K^{−} contains all solutions to equation (1). First, determine all solutions to equation (3). To describe these solutions, some new notation is introduced. If the vector

[ \begin{matrix}s \\ t \end{matrix} ]

is a solution to an equation of the form u^{2} − 5v^{2} = c, this solution can be conveniently denoted by s + t\sqrt{5}. Now identify the sets

S = \{[ \begin{matrix}s \\ t \end{matrix} ] | s, t ∈ ℤ\} and R = \{s + t\sqrt{5} | s, t ∈ ℤ\} .

Note also that the set R is closed under multiplication and is isomorphic (as a monoid) to the set

M = \{[ \begin{matrix}s & 5t \\ t & s \end{matrix} ] | s, t ∈ ℤ\}

under matrix multiplication. The map M ↦ S, given by

[ \begin{matrix}s & 5t \\ t & s \end{matrix} ] → [ \begin{matrix}s & 5t \\ t & s \end{matrix} ] · [ \begin{matrix}1 \\ 0 \end{matrix} ] = [ \begin{matrix}s \\ t \end{matrix} ] ,

gives a bijection between the elements of M and S.

By [10], all solutions to equation (3) are given by the union W of the three sets

\begin{aligned}W_{1} & = \{±(9 + 4\sqrt{5})^{k} · (−1 + \sqrt{5}) | k ∈ ℤ\} , \\ W_{2} & = \{±(9 + 4\sqrt{5})^{k} · (1 + \sqrt{5}) | k ∈ ℤ\} , \\ W_{3} & = \{±(9 + 4\sqrt{5})^{k} · (4 + 2\sqrt{5}) | k ∈ ℤ\} . \end{aligned}

The sets W_{1}, W_{2}, and W_{3} are called classes of solutions. The solutions −1 + \sqrt{5}, 1 + \sqrt{5}, and 4 + 2\sqrt{5} are known as fundamental solutions of their respective classes, and they are found using certain numerical conditions [10]. The expression 9 + 4\sqrt{5} is a fundamental solution to the equation

u^{2} − 5v^{2} = 1.

Let W^{+} be the subset of W whose elements begin with “+” in the three sets above, and let W^{−} be the subset of W whose elements begin with “−” in the three sets above. Similarly, one may speak of W_{i}^{+} and W_{i}^{−} for i = 1, 2, 3.

Recall that multiplication by the matrix C gives a bijection between the solutions to equations (1) and (3). From this, it follows that the set K maps onto W. First, it is clear that K^{+} maps onto W^{+}.

If

[ \begin{matrix}x_{k} \\ y_{k} \end{matrix} ] ∈ K^{+},

then

C · [ \begin{matrix}x_{k} \\ y_{k} \end{matrix} ] = C · P^{k} · [ \begin{matrix}1 \\ 1 \end{matrix} ] .

For example,

C · [ \begin{matrix}x_{3} \\ y_{3} \end{matrix} ] = [ \begin{matrix}2 & −3 \\ 0 & 1 \end{matrix} ] · [ \begin{matrix}3 & −1 \\ 1 & 0 \end{matrix} ]^{3} · [ \begin{matrix}1 \\ 1 \end{matrix} ] = [ \begin{matrix}2 & −3 \\ 0 & 1 \end{matrix} ] · [ \begin{matrix}13 \\ 5 \end{matrix} ] = [ \begin{matrix}11 \\ 5 \end{matrix} ] .

Let k ∈ ℤ and consider (9 + 4\sqrt{5})^{k} · (−1 + \sqrt{5}) ∈ W_{1}^{+}. One can now show that

C · [ \begin{matrix}x_{3k} \\ y_{3k} \end{matrix} ] = (9 + 4\sqrt{5})^{k} · (−1 + \sqrt{5}).

In view of the identifications between the sets S, R, and M described earlier, the previous equation reduces to the matrix equation

[ \begin{matrix}2 & −3 \\ 0 & 1 \end{matrix} ] · [ \begin{matrix}3 & −1 \\ 1 & 0 \end{matrix} ]^{3k} · [ \begin{matrix}1 \\ 1 \end{matrix} ] = [ \begin{matrix}9 & 20 \\ 4 & 9 \end{matrix} ]^{k} · [ \begin{matrix}−1 & 5 \\ 1 & −1 \end{matrix} ] · [ \begin{matrix}1 \\ 0 \end{matrix} ] ,

which can be proved using mathematical induction. Similarly, there is a one-to-one correspondence between the solutions

[ \begin{matrix}x_{3k+1} \\ y_{3k+1} \end{matrix} ]

and W_{2}^{+} and between the solutions

[ \begin{matrix}x_{3k+2} \\ y_{3k+2} \end{matrix} ]

and W_{3}^{+}. Thus, there is a one-to-one correspondence between K^{+} and W^{+}. There is also a one-to-one correspondence between K^{−} and W^{−}. The main result of this paper is now established.

\underline{Theorem 2}. The set K consists of all solutions to equation (1).

Similarly, all solutions to equation (2), the incorrect formulation of the mother-son problem, satisfy

[ \begin{matrix}x_{k} \\ y_{k} \end{matrix} ] = [ \begin{matrix}F_{2k} \\ F_{2k−2} \end{matrix} ] .

To summarize, the solutions to equation (1) consist of Fibonacci numbers with consecutive odd indices, whereas the solutions to equation (2) consist of Fibonacci numbers with consecutive even indices. Hence, the coordinates of the integral points on the curves in Figure 1 are all Fibonacci numbers. Also, for all k ∈ ℤ, the identity

F_{k}^{2} − 3F_{k}F_{k−2} + F_{k−2}^{2} = (−1)^{k}

follows immediately from the above results.

4. Further Comments and Observations. Connections between Diophantine equations (and their corresponding curves) and sequences defined by linear recurrences (such as the Fibonacci numbers) have been studied for many years. In the late 1800’s, Lucas showed that if x and y are consecutive Fibonnaci numbers, then the point (x, y) lies on one of the hyperbolas y^{2} − xy − x^{2} = ±1, and Wasteels proved the converse in 1902 (for proofs of both results see Wasteels [11]). Lucas [7] also noted some connections between the Fibonacci numbers, Lucas numbers, and Pell’s equation. (Lucas numbers, denoted by L_{n}, are defined by L_{0} = 2, L_{1} = 1, and L_{n+2} = L_{n+1}+L_{n}.) In the above paper, Lucas showed that L_{n}^{2}−5F_{n}^{2} = ±4. More recently, Long and Jordan [6] proved the following: If (x, y) is a solution to x^{2} − 5y^{2} = 4, then x = L_{2n} and y = F_{2n}. Correspondingly, if (x, y) is a solution to x^{2} − 5y^{2} = −4, then x = L_{2n−1} and y = F_{2n−1}.

Bergum [1] and Horadam [3] identified some conic curves that pass through infinitely many points whose coordinates are Fibonacci numbers. Kimberling [5] then classified all hyperbolas with this property. He defined two classes of hyperbolas (here n is a positive integer):

\begin{aligned}p_{n}(x, y) & = x^{2} + (−1)^{n+1}L_{n}xy + (−1)^{n}y^{2} + F_{n}^{2} and \\ q_{n}(x, y) & = x^{2} + (−1)^{n+1}L_{n}xy + (−1)^{n}y^{2} − F_{n}^{2}. \end{aligned}

He named these curves “Fibonacci hyperbolas” because they have the property that they pass through an infinite number of points of the form (F_{m}, F_{n}), and he proved that these are the only hyperbolas with this property. Kimberling did not prove, however, that all the integer points through which these hyperbolas pass are pairs of Fibonacci numbers. We have been able to do this in the special cases of the two Fibonacci hyperbolas involved in the correct and incorrect solutions to the mother-son age problem. It is our conjecture that all the lattice points of Kimberling’s hyperbolas p_{n}(x, y) and q_{n}(x, y) are pairs of Fibonacci numbers.

More can be said about integer solutions in the general setting. It can be shown that, if n is even, then (1, F_{n−1}) is a solution to the equation

p_{n}(x, y) = x^{2} − L_{n}xy + y^{2} + F_{n}^{2} = 0.

In addition, this Diophantine equation can be written in quadratic form as x^{T} Ax = −F_{n}^{2}, where

x = [ \begin{matrix}x \\ y \end{matrix} ] and A = [ \begin{matrix}1 & \frac{−L_{n}}{2} \\ \frac{−L_{n}}{2} & 1 \end{matrix} ] .

The matrix

P = [ \begin{matrix}−L_{n} & −1 \\ 1 & 0 \end{matrix} ]

satisfies the hypothesis of Theorem 1, and if

x_{0} = [ \begin{matrix}1 \\ F_{n−1} \end{matrix} ] ,

then the set {P^{k}x_{0} | k ∈ ℤ} consists of solutions to the equation.

McDaniel [8] identified some conics whose equations are satisfied by consecutive terms of certain recursively defined sequences. His Theorem 2 is a generalization of our solution to equation (2). Later, Melham [9] generalized some of McDaniel’s theorems.

The proof of Theorem 1 yields no insight into how the matrix

P = [ \begin{matrix}3 & −1 \\ 1 & 0 \end{matrix} ]

is constructed from

A = [ \begin{matrix}1 & −\frac{3}{2} \\ −\frac{3}{2} & 1 \end{matrix} ]

in order to satisfy the condition P^{T} AP = A. There are other candidates for P, such as

[ \begin{matrix}0 & 1 \\ −1 & 3 \end{matrix} ] ,

that would work equally well for generating all solutions to the Diophantine equation for the mother-son age problem. Also, there are many matrices that do not generate an infinite number of solutions. It is also possible to find matrices that generate an infinite number of solutions, but not all solutions; P^{2} would be an example of such a matrix.

The matrix P that was used to obtain solutions to equation (1) was found by setting P equal to

[ \begin{matrix}s & t \\ 1 & 0 \end{matrix} ]

and solving the equation P^{T} AP = A for s and t. This yielded two solutions: the matrix used to generate all solutions, and

P = [ \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ] .

Since P^{2} = I, this matrix does not generate an infinite number of solutions. The next theorem, whose proof is straightforward, puts some structure on the set of matrices P that satisfy Theorem 1.

\underline{Theorem 3}. Let A be an invertible matrix in M_{n}(ℝ), the set of all n × n matrices over ℝ. Define 𝔾_{A} = {P ∈ M_{n}(ℝ) | P^{T} AP = A}. Then 𝔾_{A} forms a group under the operation of matrix multiplication.

Other authors have used the identification of expressions of the form s + t\sqrt{d} with matrices of the form

[ \begin{matrix}s & dt \\ t & s \end{matrix} ]

in problems similar to ours. See, for example, Wegener [12].

\underline{References}

1. G. E. Bergum, “Addenda to Geometry of a Generalized Simpson’s Formula,” The Fibonacci Quarterly, 22 (1984), 22–28.

2. J. Gullberg, Mathematics: From the Birth of Numbers, Norton, New York, 1997.

3. A. F. Horadam, “Geometry of a Generalized Simpson’s Formula,” The Fibonacci Quarterly, 20 (1982), 164–168.

4. J. A. H. Hunter and J. S. Madachy, Mathematical Diversions, Van Nostrand, Princeton, 1963.

5. C. Kimberling, “Fibonacci Hyperbolas,” The Fibonacci Quarterly, 28 (1990), 22–27.

6. C. T. Long, J. H. Jordan, “A Limited Arithmetic on Simple Continued Fractions,” The Fibonacci Quarterly, 5 (1967), 113–128.

7. E. Lucas, “Sur L’Emploi Calcul Symbolique, dans la Théorie des Séries Récurrentes,” Nouvelles Correspondances Mathématiques, 2 (1876), 201–206.

8. W. L. McDaniel, “Diophantine Representations of Lucas Sequences,” The Fibonacci Quarterly, 33 (1995), 59–63.

9. R. Melham, “Conics Which Characterize Certain Lucas Sequences,” The Fibonacci Quarterly, 35 (1997), 248–251.

10. T. Nagell, Introduction to Number Theory, Wiley, New York, 1951.

11. J. Wasteels, “Quelques Propriétés des Nombres de Fibonacci,” Mathesis, 3 (1902), 60–62.

12. D. P. Wegener, “An Application of Pell’s Equation,” The Fibonacci Quarterly, 19 (1981), 450–451.

Mathematics Subject Classification (2000): 11B39, 11C20, 11D09, 15A36, 15A63

Keith Brandt Department of Mathematics, Computer Science, and Physics Rockhurst University Kansas City, MO 64110 email: keith.brandt@rockhurst.edu

John Koelzer Department of Mathematics, Computer Science, and Physics Rockhurst University Kansas City, MO 64110 email: john.koelzer@rockhurst.edu