ELEMENTARY RESULTS ON THE FIBONACCI NUMBERS
DR AFT
ROGÉRIO THEODORO DE BRITO
Contents
1. Introduction 2. Definition and Elementary Properties 3. Other Properties of the Golden Ratio 4. Algorithms for the Fibonacci Numbers 5. “Appearances” of the Fibonacci Numbers 6. The Fibonacci numbers and their siblings 7. Fibonacci Numbers and Linear Algebra 8. Fibonacci Numbers and Their use in Analysis of Algorithms References
1 1 6 7 7 9 9 9 12
1. Introduction
The Fibonacci Numbers arise in plenty of situations of our days (even if in disguise) and they fascinate a lot of people for the abundance of their properties. It is remarkable that such a sequence presents so many connections with a number of branches of Mathematics, ranging from Complex Variables to Abstract Algebra, from Discrete Mathematics [4] to Linear Algebra, from Elementary Number Theory [1] to Analysis of Algorithms [2], just to cite a few. It is the purpose of these short notes to present (in a very easy way—perhaps, accessible even to high-school students) some of the most widely known and elementary facts regarding such intriguing numbers. The reader can find many other sources of material for further study (including a journal entirely devoted to Fibonacci Numbers, the Fibonacci Quarterly Journal!) in the references. They contain a number of much deeper results that are outside the scope of these modest notes. 2. Definition and Elementary Properties
The Fibonacci Numbers can be defined in many different (and equivalent) ways, but the most common definition seems to be the fact that they are a sequence of integers that can be defined by a very simple recurrence relation: 0, if i = 0 1, if i = 1 Fi = F i −1 + F i −2 , if i ≥ 2 Notice that starting with the third number of the sequence, a given Fibonacci number can be calculated as the sum of its two predecessors in the sequence. This means that the first numbers can be listed as illustrated by the following table: i Fi
0 1 2 3 0 1 1 2
4 5 6 3 5 8
7 8 13 21
Date: January 27, 2013. 1
9 34
10 55
11 89
12 13 . 144 233
2
ROGÉRIO THEODORO DE BRITO
This is a good moment to remark that some authors define the Fibonacci numbers starting with index 1, instead of what we did here. As the reader will shortly see, the way we defined these numbers has advantages that will be obvious soon, while, at the same time, describing the sequence in a slightly more general way (we will also see further generalizations soon).
DR AFT
2.1. Some Basic Properties of the Fibonacci Numbers. A little observation of the first few numbers listed in the table above suggests that the sequence might satisfy some relations. For instance, summing the first four terms of the sequence gives 0 + 1 + 1 + 2 = 4 = 5 − 1; summing the first five terms gives us 0 + 1 + 1 + 2 + 3 = 7 = 8 − 1. This seems to suggest us that summing the first n terms of the sequence results in the (n + 2)-th term minus one, and this is indeed the case, as we will prove in the following proposition. Proposition 1. For each natural n ≥ 1, we have (1)
F 0 + F 1 + · · · + F n −1 = F n+1 − 1.
Proof. Since the sequence is defined by a recurrence relation, the most straightforward way of proving it is by induction on n. If n = 1, then the left side of the equation would consist of F 0 = 0 = 1 − 1 = F 1 − 1, and the fact holds for n = 1. If n = 2, then we would have F 0 + F 1 = 0 + 1 = 1 = 2 − 1 = F 3 − 1 and it is also OK for this case. The reader is encouraged to verify the assertion for other values of n, to gain a little more confidence on what we are trying to prove. Let us assume then that our hypothesis is valid for all integers n such that 1 ≤ n < n 0 P 0 −1 and let’s prove that it is also true for n 0. By our induction hypothesis, nk=0 F k = F n 0 +1 − 1. Summing F n 0 to both sides of this equation gives n0 X
F k = F n 0 + F n 0 +1 − 1 = F n 0 +2 − 1,
k=0
where the last equation is simply a use of the definition of the Fibonacci numbers and this concludes our proof. Other facts can be easily inferred from the table of our first numbers: Proposition 2. For any natural n ≥ 0, we have: (2) (3)
F 1 + F 3 + F 5 + · · · + F 2n+1 = F 2n+2
F 0 + F 2 + F 4 + F 6 + · · · + F 2n = F 2n+1 − 1
Proof. Like the previous proposition, both facts here can be proved by induction on n. We now proceed to . . . In fact, “merging” the formulas stated in Proposition 2, we can derive Proposition 1 as a corollary, obtaining, thus, a second proof for the sum of the first Fibonacci numbers. Alternate proof of Proposition 1. Since we already know that F 1+· · ·+F 2n+1 = F 2n+2 and that P 2n+1 F 0 +F 2 +· · ·+F 2n = F 2n+1 −1, summing both equation, we get k=0 F k = (F 2n+1 −1)+F 2n+2 = F 2n+3 −1. Changing the variables conveniently, we get the result stated in the corollary. 2.2. The Golden Ratio and Some Elementary Facts. Before talking more about the Fibonacci numbers, we take some moments for a little digression regarding some other numbers that are quite important and, as we shall see, they present strong (and, sometimes, remarkably surprising) connections with the Fibonacci numbers. √
Definition 1 (The Golden Ratio and Its Conjugate). The real number ϕ = 1+2 5 is called √ the golden ratio and the number ϕˆ = 1− 5 is called the golden ratio conjugate. 2
ELEMENTARY RESULTS ON THE FIBONACCI NUMBERS
3
DR AFT
Both numbers that we have just defined occur frequently enough (including in others areas like Geometry and Architecture, for instance) that they have received attention of many authors and, as a consequence, different terminology is in use regarding such numbers. For instance, ϕ is also called the “divine proportion” (among other names) and the number ϕˆ is, sometimes, called the “silver ratio”. One first elementary result involving ϕ and ϕˆ is that they are the roots of the polynomial p(x ) = 1 + x − x 2 (and this can be easily seen by the quadratic formula). This means, in particular, that they satisfy x 2 = x + 1 and, in other words, we have the following fact: Proposition 3. Both the golden ratio ϕ and its conjugate ϕˆ satisfy the equality x 2 = x + 1. √ √ √ 2 Proof. We have ϕ 2 = (1 + 5) /4 = (1 + 2 5 √ + 5)/4 = (6 + 2 5)/4. Simplifying this latter √ equation, we have ϕ 2 = (3 + 5)/2 = 1 + (1 + 5)/2 = 1 + ϕ 2. The same can be verified for the conjugate of the golden ratio, which we leave as an exercise. In other words, if we wish to calculate ϕ squared, we can do that simply by adding 1 to ˆ In fact, ϕ has some other interesting properties: ϕ. The same is true for ϕ. ˆ Proposition 4. If ϕ is the golden ratio, then ϕ − 1 = −ϕ. √ √ √ Proof. This is a quite direct fact, since ϕ −1 = (1+ 5)/2−1 = (−1+ 5)/2 = −(1− 5)/2 = ˆ −ϕ. ˆ Proposition 5. If ϕ is the golden ratio, then 1/ϕ = −ϕ. √ √ √ ˆ √ 5 , we have 1/ϕ = 2(1 − 5)/ − 4 = −(1 − 5)/2 = −ϕ. Proof. Since 1/ϕ = 1+2√ 5 · 1− 1− 5
From the Proposition 5, we can formally state the same fact in equivalent, but convenient ways for our future uses: Corollary 6. For the golden ratio ϕ, we have ϕϕˆ = −1. Equivalently, we have 1/ϕˆ = −ϕ. Proof. Both facts are simply re-statements of the result of the earlier proposition.
And we can, actually, say a little more about the golden ratio, as the following proposition asserts: √ ˆ we have ϕ − ϕˆ = 5 and ϕ + ϕˆ = 1. Proposition 7. For the golden ratio ϕ and its conjugate ϕ, Proof. Again, both facts admit quite straight verifications.
2.3. Generating Functions and the Fibonacci Numbers. It is a fortunate case that many sequences may be “compactly” represented by a single, “simple” univariate function, whose Taylor-Maclaurin expansion (around 0) [5] has the i-th sequence number as the coefficient of the i-th power of the variable x. Functions that have such properties are called generating functions [8]. It should be made explicit here that these functions are formal series and we are not particularly concerned about convergence. If the function actually happens to be convergent for some values of x, then we can possibly use this fact for deriving other properties, but our main purpose is to just find a function that has the chosen numbers as the coefficients of the powers of the variable.1 For instance, we can easily find a generating function the sequence h1, 1, . . . , 1, . . .i, that is, the sequence composed of ones only: its generating function is f (x ) = 1 + x + x 2 + · · · + x i + · · · = 1/(1 − x ). The reader not used to generating functions may be wondering what is, the, so special about generating functions that makes it deserve our attention. In fact a slight modification of the generating function f (x ) can give us some 1In other words, we are mainly interested in the ring C[[X ]] of formal series with complex numbers as the coefficients.
4
ROGÉRIO THEODORO DE BRITO
DR AFT
not so trivial results, as we shall see. Indeed, the sequence h1, 3, 9, 27, 81, . . .i of powers of 3 is simply д(x ) = f (3x ) = 1/(1 − 3x ) and, in general, the generating function for the geometric sequence h1, q, q 2 , q 3 , . . .i of powers of a real number q is easily seen to be f q (x ) = 1/(1 − qx ). Quite a good deal more sequences may be described by a suitably “simple” generating function. Just as one simple example, we can see that h0, 1, 2, 3, 4, 5, . . .i, comprised of the natural numbers is the formal derivative of f (x ), that is 0 + 1 + 2x + 3x 2 + · · · + ix i −1 + · · · = [1/(1 − x )]0 = 1/(1 − x ) 2, which is a simple way of describing the natural numbers in a very compact fashion. 2.3.1. Is There a Generating Function for the Fibonacci Numbers? But would there be a such a compact representation for the sequence of the Fibonacci numbers? The answer is, fortunately enough, positive. Suppose that the Fibonacci numbers are denoted by hF 0 , F 1 , F 2 , . . . , F i , . . .i. Then, if there exists a function F (x ) with such numbers as the P i coefficients of powers of x, we would have F (x ) = F 0 +F 1x +F 2x 2 +· · · = F 0 +F 1x + ∞ i=2 F i x . Using the fact that for i ≥ 2 we have F i = F i −1 + F i −2, we have F (x ) = F 0 + F 1x +
∞ X
i
(F i −1 + F i −2 )x = F 0 + F 1x +
i=2
∞ X
i
F i −1x +
i=2
∞ X
F i −2x i .
i=2
Therefore, we have
∞ ∞ X X i 2 i F (x ) = F 0 + F 1x + x F i x + x F i x . i=1
xi
i=0
xi.
Since F 0 = 0, we have i=0 F i = i=1 F i Thus, if such a function F (x ) exists, it must satisfy F (x ) = 0 + x + x F (x ) + x 2 F (x ), that is, F (x ) − x F (x ) − x 2 F (x ) = x, which means that F (x )(1 − x − x 2 ) = x, or, in other words, x (4) F (x ) = . 1 − x − x2 We now one have to show that this is indeed a function whose coefficient of x i is F i , and we are done showing that F (x ) is the generating function of the Fibonacci numbers. One thing worth trying is to write the generating function F (x ) of the Fibonacci numbers as a sum of partial fractions, since it is the quotient of two polynomials. As a first step, we can try to factor the denominator, which is apquadratic polynomial. Finding the √ roots of 1−x −x 2 = 0 can be accomplished as x = (1± 1 − 4(−1)(1))/−2 = (1± 5)/(−2). This means, in particular, that the polynomial 1−x −x 2 has (x +ϕ) as a factor. By performing long division, we see that P∞
P∞
1 − x − x 2 = (x + ϕ)(−ϕˆ − x ).
(5)
Trying to rewrite (5) in a more “digestible way”, we have that " !# x x 2 ˆ ˆ 1 − x − x = (x + ϕ)(−ϕ − x ) = ϕ + 1 (−ϕ) 1 + , ϕ ϕˆ that is, ˆ − ϕx ˆ )(1 − ϕx ) = (1 − ϕx )(1 − ϕx ˆ ), 1 − x − x 2 = (−ϕϕ)(1 where the equalities are due to the facts stated in the previous section. In particular, we have found a very nice way of writing the denominator of (4) as a product of two simple linear factors on x. Thus, writing F (x ) as a sum of partial fractions, we have, with α and α 0 being unknowns, (−α ϕˆ − α 0ϕ)x + (α + α 0 ) x α α0 F (x ) = = + = , 2 ˆ ) ˆ ) 1−x −x (1 − ϕx ) (1 − ϕx (1 − ϕx )(1 − ϕx
ELEMENTARY RESULTS ON THE FIBONACCI NUMBERS
5
DR AFT
which gives rise to the following linear system on two variables α and α 0: −α ϕˆ − α 0ϕ = 1 , α + α 0 =0 √ √ which, upon being solved, gives us α = 1/ 5 and α 0 = −1/ 5. Therefore, x α α0 1 1 1 . F (x ) = = + = √ − ˆ ˆ 1 − x − x 2 1 − ϕx 1 − ϕx 5 1 − ϕx 1 − ϕx √ We have already seen in Proposition 7 that ϕ − ϕˆ = 5, which means that we can write the generating function F (x ) purely in terms of the golden ration and its conjugate: 1 1 1 . F (x ) = − ˆ ϕ − ϕˆ 1 − ϕx 1 − ϕx But since we already know the expansion of 1/(1 − qx ) for any real q, we can use our knowledge here, to get: X 1 X 1 X i ˆi i X ϕ i − ϕˆi i i i ˆ F (x ) = (ϕ − ϕ )x = x . (ϕx ) = (ϕx ) − ˆ ϕ − ϕˆ i ≥0 ϕ − ϕˆ i ≥0 i ≥0 ϕ − ϕ i ≥0 This seems to indicate us that
Fi =
ϕ i − ϕˆi , ϕ − ϕˆ
and, as the reader can show by induction, this is, indeed, a “closed formula” for the i-th Fibonacci number, called Binet’s Formula. We state this here for further reference: Theorem 8 (Binet’s Formula for Fibonacci Numbers). For every i ≥ 0, we have that Fi =
ϕ i − ϕˆi . ϕ − ϕˆ
2.3.2. Infinite Series involving the Fibonacci Numbers. It is interesting to see that a generating function provides a compact way of representing a sequence of numbers and, by manipulations to that function, we can obtain manipulations to the sequence of numbers. There are many things more to be said about generating functions, but one remarkable fact is that, although generally only regarded formally, there are some cases when it is possible to use those functions “plugging in some numbers” in place of the placeholder variable, namely, when the series analytically converges to the generating function of the sequence. That is the case of the function F , when its variable is x = 1/2.2 Indeed, recalling that we can write F as a power series as: ∞ X F (x ) = F 0 + F 1x + F 2x 2 + F 3x 3 + · · · = Fix i , i ≥0
we see that if x = 1/2, the we would have X Fi 1 1 1 F (1/2) = F 0 + F 1 + F 2 + F 3 + · · · = . 2 4 8 2i i ≥0 But since we also know that a closed form for F , we have that 1 X Fi 1/2 =F = = 2. i 2 2 1 − 1/2 − 1/4 i ≥0 2In general, the convergence of a power series is determined as an interval centered in a point, that is a ball in one-dimensional space.
6
ROGÉRIO THEODORO DE BRITO
DR AFT
2.4. Binet’s Formula, Characteristic Equations, and Fibonacci Numbers. If we look √ ˆ = 5, at Binet’s expression for the i-th Fibonacci number, the we can easily see that ϕ − ϕ √ ˆ < 1/2, which is a constant factor and, since 5 > 4, we have that 5 > 2, that is, 1/(ϕ − ϕ) i i ˆ that multiplies the difference ϕ − ϕ . Numerically speaking, we get an approximation for ϕ ' 1.618033988 and for ϕˆ ' −0.618033988, which is another way to see something that we have already proved: that the golden ratio and its conjugate sum 1 and, as a consequence, they have exactly the same “fractional part” (see Proposition 7). ˆ < 1, we have that ϕˆi is a quite rapidly decreasing function. FurtherAlso, given that |ϕ| ϕi
ϕˆ i
more, we soon see that Binet’s formula F i = has this second term considerably − ϕ − ϕˆ ϕ − ϕˆ smaller than the first as i increases and we compare it with the first term. For this purpose, if we define a function nint : R → Z that for each x ∈ R gives us the nearest integer to x, we have that ! ϕi F i = nint √ , 5 for all i ≥ 0, which is another way to express the i-th Fibonacci number as a function of the golden ratio. If we had not seen the derivation of the formula in the previous section, but only saw the table for the first Fibonacci numbers, we could still have guessed that, perhaps, they could have an exponential growth. In fact, if we had a real number α such that α i = F i , the, for the general case, we would have that α i = α i −1 + α i −2, for all i ≥ 2. Se we would obviously have α , 0, then this would mean that α 2 = α + 1, for all i ≥ 2, upon division of both sides of the equation by α i −2. But solving the equation x 2 = x + 1 for x, we get, quite ˆ unsurprisingly, x = ϕ or x = ϕ. This is a standard technique for solving linear and homogeneous differential equations: we find, first, its characteristic equation (in our case, x 2 = x + 1) and, given the initial conditions (for us, F 0 = 0 and F 1 = 1), try to find a solution as a linear combination of the exponentials given by the solutions to the characteristic equation. So, let’s try it here with our recent findings: if F 0 = xϕ 0 + yϕˆ0 for reals x , y, and F 1 = xϕ 1 + yϕˆ1, then, solving the linear system 0 = 1x + 1y ˆ 1 = ϕx + ϕy, ˆ ˆ = 1, which yields x = 1/(ϕ − ϕ), ˆ ) = 1, that is, x (ϕ − ϕ) we get x = −y, and thus, ϕx + ϕ(−x ˆ and, as y = −x, y = −1/(ϕ − ϕ). This shows that ϕ i − ϕˆi F i = xϕ i + yϕˆi = x (ϕ i − ϕˆi ) = , ϕ − ϕˆ
which is, again, Binet’s formula, for which we now know of a second derivation. 2.5. Lucas numbers (initial conditions: L 1 = 1, L 2 = 3).
2.5.1. Derivation of a formula for the Lucas Numbers from the characteristic equation and the initial conditions (L n = ϕ n + ϕˆn ). 3. Other Properties of the Golden Ratio 3.1.
ϕn
=
ϕ n −1
+ ϕ n −2.
3.2. Alternative definition of the Golden Ratio as limn→∞ F n+1/F n . 3.3. Irrationality proof of the Golden Ratio. 3.4. Exponential Growth of the Fibonacci Sequence: Θ(ϕ).
ELEMENTARY RESULTS ON THE FIBONACCI NUMBERS
7
3.5. Description of the Golden Ratio as a Continued Fraction. 3.6. Golden Rectangle. 3.7. Golden Segment.
DR AFT
4. Algorithms for the Fibonacci Numbers
It is quite easy to develop a computer program for calculating those numbers. We give a pseudo-code for such program, which is nothing more than a mere “transcription” of the definition given above. Algorithm 1 Fibonacci-Rec(n)
Input: An integer n ≥ 0. Output: The n-th number of the Fibonacci sequence. 1: if n ≤ 1 then 2: return n 3: else 4: return Fibonacci-Rec(n − 1) + Fibonacci-Rec(n − 2) 5: end if
This short algorithm correctly implements a procedure for calculating F n given n, as it is obviously doing what the defining recurrence relation describes. Unfortunately, despite its simplicity, Fibonacci-Rec is not a “good way” of calculating F n . More precisely, as we shall see in a latter section, the number of operations performed by Algorithm Fibonacci-Rec cannot be bounded (from above) by a polynomial in the input n. Remark 1. Actually, from a Computational Complexity [2, 3, 7] point of view, the number of steps should be counted as a function of the length of the input, which, in this case, is the number of bits used as input for n—without padding it with “spurious” zeros at the left, obviously. 5. “Appearances” of the Fibonacci Numbers
5.1. In Geometry.
5.1.1. Trigonometric functions. Here we present an elementary derivation of the values of sin, and cos of multiples of π5 and, somewhat unexpectedly, these values of the trigonometric functions are related to the golden ratio. It is evident that since both sin and cos are periodic functions with period 2π , and that symmetries can be exploited so that we can restrict ourselves to the interval [0, π ). Concretely, is is sufficient to determine the values sin( kπ/5) and cos( kπ/5) for k = 0, √ . . . , 4. As the derivation of such√values happens to make use of the golden ratio ϕ = (1 + 5)/2 and its conjugate ϕˆ = (1 − 5)/2, we briefly summarize below some useful relations: • ϕ 2 = ϕ + 1 and ϕˆ2 = ϕˆ + 1. ˆ • ϕϕˆ = −1 and its equivalent form ϕ = −1/ϕ. ˆ ˆ • ϕ + ϕ = 1 or ϕ = 1 − ϕ. For most of our work, we will also need the so-called “double angle formulas” for sine and cosine, which we collect here for future reference: • sin(2θ ) = 2 cos θ sin θ . • cos(2θ ) = cos 2 θ − sin 2 θ = 2 cos 2 θ − 1 = 1 − sin 2 θ .
8
ROGÉRIO THEODORO DE BRITO
2π/5 4π/5
0
DR AFT
6π/5
8π 5
Figure 1. A regular pentagon and its internal angles.
Now, on to our main task. To determine the values of both sine and cosine of multiples of π /5, we first see that a regular pentagon has all its 5 internal angles measuring 2π /5. So, for θ = 2π /5, we can see, by the symmetry of walking both clockwise and counterclockwise on the pentagon of figure 1 we have that (6)
sin(4θ ) = − sin θ .
Also, using the double angle formulas repeatedly, we have: (7) (8)
sin(4θ ) = 2 cos(2θ ) sin(2θ ) = 2(2 cos 2 θ − 1)(2 cos θ sin θ )
= (2 cos 2 θ − 1)(4 cos θ sin θ ) = 8 cos 3 θ sin θ − 4 cos θ sin θ .
From (6) and (8), we have
8 cos 3 θ sin θ − 4 cos θ sin θ = − sin θ ,
or, rearranging the terms,
sin θ (8 cos 3 θ − 4 cos θ + 1) = 0.
So, sin θ = 0 or 8 cos 3 θ − 4 cos θ + 1 = 0. As θ = 2π /5 implies sin θ , 0, we must have that 8 cos 3 θ − 4 cos θ + 1 = 0. Solving for cos θ , we get (9)
8x 3 − 4x + 1 = 0.
It is not hard to solve (9): its only possible rational solutions are ±1, ±1/2, ±1/4, ±1/8. By inspection, we have that x = 1/2 works: 8 18 − 4 12 + 1 = 0. So, 8x 3 − 4x + 1 is a multiple of (x − 1/2) and, by the Euclidean algorithm, we have 8x 3 − 4x + 1 = (x − 1/2)(8x 2 + 4x − 2). If cos θ = 1/2, then we know that θ = π /3 or that θ = 5π /3, which is not the case, as we know that θ = 2π /5. We √can find the roots of 8x√2 + 4x − 2 by the quadratic formula, which gives us x = ˆ −(1 + 5)/4 = −ϕ/2 or x = ( 5 − 1)/4 = −ϕ/2. In other words, cos θ = −ϕ/2 < 0 or ˆ ˆ cos θ = −ϕ/2 > 0. As cos θ must be positive, we must have cos(2π /5) = −ϕ/2. 2 From the double angle formula for cosine, we have cos(4π /5) = 2 cos (2π /5) − 1 = ˆ 2 ) − 1 = ϕˆ2/2 − 1. As ϕˆ2 = ϕˆ + 1, we have cos(4π /5) = (ϕˆ + 1)/2 − 1 = (ϕˆ − 1)/2 = 2((ϕ/2) −ϕ/2. So far, we have determined cos(2π ) and cos(4π ). 5.1.2. Pentagons. 5.2. In Typography. 5.2.1. Page Layout. 5.3. In Music. 5.3.1. Béla Bartók? 5.3.2. Tool/Lateralus.
ELEMENTARY RESULTS ON THE FIBONACCI NUMBERS
9
6. The Fibonacci numbers and their siblings 6.1. Relation with binomial coefficients. 6.1.1. Relations between the Fibonacci Numbers and the Lucas Numbers. 6.2. Negative index Fibonacci Numbers.
DR AFT
6.3. Other relations found in the Book of Andrews [1].
7. Fibonacci Numbers and Linear Algebra
Use of the matrix
" # 1 1 , 1 0 its eigenvectors, its eigenvalues, its diagonal matrix, its powers, its determinants, more relations of Fibonacci Numbers, vectors that are neatly transformed by this matrix etc. 8. Fibonacci Numbers and Their use in Analysis of Algorithms 8.1. Iterative Algorithm for the Computation of Fibonacci Numbers. 8.2. Analysis of the Recursive Algorithm for the Fibonacci Numbers. 8.3. Euclid’s Greatest Common Divisor Algorithm. Now that we know some properties of the divisibility relation, we can define a very useful concept that is a consequence of division. Definition 2 (Greatest Common Divisor). Let a and b be integers not both null. An integer d that divides a and b simultaneously (i.e., d | a and d | b) is called a common divisor of a and b. If a common divisor d of a and b is such that every common divisor d 0 of a and b also divides d, then we say that d is a greatest common divisor of a and b. We denote that d is a greatest common divisor of a and b by d = (a, b). If d = 1, then we say that a and b are coprime or relatively prime. Notice that, by the definition above, if d and d 0 are both greatest common divisors of a and b, then, in particular, d | d 0 and d 0 | d and by the previous proposition, d = ±d 0, i.e., two greatest common divisors of a and b differ only by their signal. It is customary to define the greatest common divisor by taking the positive integer between d and d 0 and we shall, from now on, adopt this convention. From this it should be obvious that (a, b) = (−a, b) = (|a|, |b|) and that (a, b) = (b, a). The reader has certainly noticed that two numbers a and b do have a greatest common divisor: since 1 | a and 1 | b, in the worst case, their greatest common divisor is 1. But how can (a, b) be calculated? One method is to compute the sets D(a) and D(b) of positive divisors of a and b, respectively, take the intersection D (a) ∩ D (b), and find its maximum element (it is obvious that such set is bounded from above and that their intersection is non-empty). Example 1. To calculate (24, 15), can see that D(24) = {1, 2, 3, 4, 6, 8, 12, 24} and D(15) = {1, 3, 5, 15}. Therefore, D (24) ∩ D(15) = {1, 3} and from this we conclude that (24, 15) = 3. It is obvious that this process can become fantastically slow depending on a and b. But there is a much faster method known since the ancient Greeks (circa 350 B.C.) called Euclid’s Greatest Common Divisor Algorithm. We need a simple proposition before proceeding with the study of greatest common divisors: Proposition 9 (The Division Algorithm). Let a and b be integers, with b a positive integer. Then, there exist integers q and r , such that a = bq + r , with 0 ≤ r < b. Furthermore, the integers q and r above are unique.
10
ROGÉRIO THEODORO DE BRITO
DR AFT
Proof. Let us consider the set S = {a − bx : x ∈ Z}. Notice that S has positive elements (it suffices to take x small enough). Let r be the smallest non-negative element of S.3 We claim that r = a − bq is such that 0 ≤ r < b. In fact, if r ≥ b, then we would have r − b ≥ 0 and r − b would be non-negative and of the form a − bq − b = a − b (q + 1), that is, a member of the set S strictly smaller than r , which would contradict the minimality of r . To prove the uniqueness, let us suppose that a = bq + r = bq 0 + r 0, with 0 ≤ r , r 0 < b. Then we have that bq − bq 0 = r 0 − r , that is b (q − q 0 ) = r 0 − r . Without any loss of generality, we may assume that r 0 ≥ r , from which it follows that b ≥ b − r > r 0 − r ≥ 0, that is, b > r 0 − r ≥ 0. Then we have r 0 − r being both a non-negative multiple of b and strictly less than b, from which it follows that r 0 − r = 0, i.e., r 0 = r . Since b , 0, we have q − q 0 = 0, i.e., q = q 0 and the uniqueness is established. Definition 3 (Quotient, Remainder). With the notation of the lemma above, the integer q is called the quotient of a divided by b and r is called the remainder of a divided by b. The proposition above tells us, intuitively, how to find divisibility with “remainder”, that is, when b - a, we still can write a as a multiple of b plus a “small correction” (less than b). As another remark, notice that, in the statement of the proposition, if we had b < 0, then we could apply it for b 0 = −b and we would obtain a pair of numbers q 0 , r 0 such that a = q 0b 0 + r 0, with 0 ≤ r 0 < |b|. Example 2. We had seen earlier that 4 - 6 as we can’t write 6 = 4a for any integer a. But as a “consolation prize”, we can see that 6 = 4 · 1 + 2 and here 2 is the “adjustment” to 4 · 1 so that we can have “an approximation” to the assertion that 4 divides 6. On the other hand, if a | b, we have b = ac, with a remainder of 0. Back to the subject of greatest common divisors, Euclid’s Algorithm is based on the following observation: if a can be written in the form a = bq + r , then any common divisor of a and b is also a divisor of r , since r = a − bq. Conversely, if b and r share a common divisor, then it must also divide a. This means that the set of common divisors of a and b is precisely the set of common divisors of b and r , and their maximum must be the same or, in other words, (a, b) = (b, r ). Furthermore, if we can have 0 ≤ r < b (which we can by Proposition 9), then the problem of finding (a, b) is reduced to the problem of finding the greatest common divisor of a pair of numbers where one of them is strictly smaller than the other, which means that we are faced with a “simpler” problem. Now, explicitly, if we have:
(10)
a = bq 1 + r 1 ,
0 < r 1 < b,
b = r 1q 2 + r 2 ,
0 < r 2 < r1,
(b, r 1 ) = (r 1 , r 2 )
r 1 = r 2q 3 + r 3 ,
0 < r 3 < r 2,
(r 1 , r 2 ) = (r 2 , r 3 )
.. . r n −2 = r n −1q n + r n , r n −1 = r nq n+1 + 0,
.. . 0 < r n < r n −1 ,
(a, b) = (b, r 1 )
.. . (r n −2 , r n −1 ) = (r n −1 , r n ) (r n −1 , r n ) = (r n , 0),
then we see that performing multiple divisions, until we get a remainder equal to 0, we can determine the greatest common divisor of two integers to be equal to (r n , 0) = r n . This practical device allows us to calculate (a, b) quite quickly, as we shall see when we analyze its computational complexity.
3Here we use the fact that a set of non-negative integers is well-ordered, that is, a non-empty set of nonnegative integers has a smallest element.
ELEMENTARY RESULTS ON THE FIBONACCI NUMBERS
11
Example 3. As before, let us determine the (24, 15), now with the assistance of Euclid’s Algorithm. We have: 24 = 15 · 1 + 9 15 = 9 · 1 + 6 9=6·1+3
DR AFT
6 = 3 · 2,
and from just 4 divisions we conclude that 3 = (24, 15).
This algorithm can be easily implemented in a digital computer with use of a modern computer language with the pseudocode given by Algorithm gcd. Algorithm 2 gcd (a, b)
Input: Two positive integers a and b. Output: Their greatest common divisor. while b , 0 do r ← a mod b // mod represents the remainder of a divided by b a ←b b ←r end while return a
8.3.1. Lamé’s Theorem. According to Alexander Schrijver, the theorem below (given by the French mathematician Gabriel Lamé, in a paper published in 1884) was one of the first conscious analysis of time requirements of an algorithm. [7, p. 14]. Theorem 10 (Lamé’s Theorem). Let a and b be positive integers. Then, the number of divisions performed by Euclid’s Algorithm applied to a and b is at most 5 times the number of digits used in the decimal representation of b. Proof. Going back to the successive equations (10), we see that r n ≥ 1. From r n −1 = r nq n+1, we have that r n −1 ≥ 2, since r n −1 > r n . This means that r n ≥ F 2 and r n −1 ≥ F 3. But then, r n −2 = r n −1q n + r n ≥ F 3 + F 2 = F 4 , since q n ≥ 1. Similarly, r n −3 = r n −2q n −1 + r n −1 ≥ F 4 + F 3 = F 5, since q n −1 ≥ 1. By induction, we can see that (11)
r n −k ≥ F k+2 ,
for k = 0, . . . , n.
On the other√ hand, let us consider the positive root of the equation x 2 − x − 1 = 0, which is ϕ = 1+2 5 , the golden ratio. We see that: ϕ2 = ϕ + 1 < 2 + 1 ≤ F3 + F2 = F4
ϕ3 = ϕ2 + ϕ < F4 + 2 ≤ F4 + F3 = F5
ϕ 4 = ϕ 3 + ϕ 2 < F 5 + F 4 = F 6. In general, we have (12)
ϕ k < F k+2 ,
Then, by equations (11) and (12), we
have ϕ k
for k ≥ 2. < F k+2 ≤ r n −k , that is
ϕ k < r n −k . In particular, ϕ n < r n −n = r 0 = b, that is, ϕ n < b. As log10 is a monotonically increasing log b function, we have that n log10 ϕ < log10 b, i.e., n < log 10 ϕ . As log10 ϕ ' 0.20898764 > 10 0.2 = 15 , n < 5 · log10 b.
12
ROGÉRIO THEODORO DE BRITO
If b has s digits in its decimal representation, b < 10s , that is log10 b < s, and, therefore, n < 5s, from where it follows that the number n +1 of divisions performed by the Euclidean Algorithm is n + 1 ≤ 5s, which proves the theorem.
DR AFT
Despite being one of the first algorithms ever described (which Donald Knuth calls “the granddaddy” of all algorithms [6, p. 335]) and having the quality of requiring only a polynomial number of steps in its execution (in terms of its input length), it is not, in general, the fastest way of finding the greatest common divisor of two integers. Faster methods for modern computers include Derrick H. Lehmer’s algorithm and Josef Stein’s “binary method”. 8.4. Data Structures: Fibonacci Heaps.
References
[1] G. E. Andrews, Number Theory, Dover Publications, Inc., 1st ed., 1994. Cited in sections 1 and 9. [2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, the MIT Press, 2nd ed., 2001. Cited in sections 1 and 7. [3] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1st ed., 1979. Cited in section 7. [4] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, Inc., 2nd ed., 1994. Cited in section 1. [5] H. L. Guidorizzi, Um Curso de Cálculo, vol. 1, Livros Técnicos e Científicos Editora, 2nd ed., 1989. Cited in section 3. [6] D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, vol. 2, Addison-Wesley, Inc., 3rd ed., 1998. Cited in section 12. [7] C. H. Papadimitriou, Computational Complexity, Addison-Wesley, Inc., 1st ed., 1994. Cited in sections 7 and 11. [8] H. S. Wilf, generatingfunctionology, Academic Press, Inc., 2nd ed., 1994. Cited in section 3.
