Greatest Common Divisors in Shifted Fibonacci Sequences

Kwang-Wu Chen Department of Mathematics and Computer Science Education Taipei Municipal University of Education No. 1, Ai-Kuo West Road Taipei, Taiwan 100, R.O.C.

                      kwchen@tmue.edu.tw

Abstract It is well known that successive members of the Fibonacci sequence are relatively

prime. Let

f_{n}(a) = gcd(F_{n} + a, F_{n+1} + a).

Therefore (f_{n}(0)) is the constant sequence 1, 1, 1, …, but Hoggatt in 1971 noted that (f_{n}(±1)) is unbounded. In this note we prove that (f_{n}(a)) is bounded if a ≠ ±1.

1 Introduction

Let the generalized Fibonacci sequence be defined by

G_{n} = G_{n−1} + G_{n−2}, for n ≥ 3,

and G_{1} = α, G_{2} = β. It is well known that [3, p. 109]

G_{n} = αF_{n−2} + βF_{n−1}.

If α = β = 1, then the generalized Fibonacci sequence G_{n} is the Fibonacci sequence F_{n}, \underline{A000045}, and if α = 1 and β = 3, G_{n} is the Lucas sequence L_{n}, \underline{A000032}. It is well known that successive members of the Fibonacci sequence are relatively prime. Consider a slightly different sequence,

(F_{n} + a),

which we call a shifted Fibonacci sequence by a, e.g., \underline{A000071}, \underline{A001611}, and \underline{A157725}. In 1971 Hoggatt [1] noted that

gcd(F_{4n+1} + 1, F_{4n+2} + 1) = L_{2n},
gcd(F_{4n+1} − 1, F_{4n+2} − 1) = F_{2n},
gcd(F_{4n+3} − 1, F_{4n+4} − 1) = L_{2n+1}.

That is to say, the successive members of the shifted Fibonacci sequence by ±1 are not always relatively prime. Let

f_{n}(a) = gcd(F_{n} + a, F_{n+1} + a).

Therefore (f_{n}(0)) is the constant sequence 1, 1, 1, …, but (f_{n}(±1)) is unbounded above. In 2003 Hernández and Luca [2] proved that there exists a constant c such that

gcd(F_{m} + a, F_{n} + a) > exp(cm),

holds for infinitely many pairs of positive integers m > n.

In this note we prove that (f_{n}(a)) is bounded above if a ≠ ±1. In fact we prove the following two theorems in this note.

Theorem 1. For any integers α, β, n and a with α^{2} + αβ − β^{2} − a^{2} ≠ 0, we have

gcd(G_{2n−1} + a, G_{2n} + a) ≤ |α^{2} + αβ − β^{2} − a^{2}|.  (1)

Theorem 2. For any integers α, β, n and a with α^{2} + αβ − β^{2} + a^{2} ≠ 0, we have

gcd(G_{2n} + a, G_{2n+1} + a) ≤ |α^{2} + αβ − β^{2} + a^{2}|.  (2)

Let α = β = 1 in Theorem 1 and Theorem 2. We can get the corollary.

Corollary 1. For integers n and a,

gcd(F_{2n−1} + a, F_{2n} + a) ≤ |a^{2} − 1|, if a ≠ ±1,
gcd(F_{2n} + a, F_{2n+1} + a) ≤ a^{2} + 1.

Hence we conclude that (f_{n}(a)) is bounded above if a ≠ ±1. Another easy corollary is that

ℓ_{n}(a) = gcd(L_{n} + a, L_{n+1} + a)

has only finitely many values.

Corollary 2. For integers n and a,

gcd(L_{2n−1} + a, L_{2n} + a) ≤ a^{2} + 5,
gcd(L_{2n} + a, L_{2n+1} + a) ≤ |a^{2} − 5|.

Similarly, let α = 1 and β = 3 in Theorem 1 and Theorem 2. We conclude that ℓ_{n}(a) is bounded above for any integers a.

In the next section we will derive two basic lemmas. From them, we determine f_{n}(1), f_{n}(2), f_{n}(−1), f_{n}(−2), and ℓ_{n}(1), in Section 3, 4, and 5. In the last section we prove Theorems 1 and 2.

2 Preliminaries

Lemma 1. For integers n, k, and a,

gcd(G_{n} + aF_{k}, G_{n−1} − aF_{k+1}) = gcd(G_{n−2} + aF_{k+2}, G_{n−3} − aF_{k+3}).  (3)

Proof. Since gcd(a, b) = gcd(a + bc, b) for any integers a, b, and c, we have

gcd(G_{n} + aF_{k}, G_{n−1} − aF_{k+1}) = gcd(G_{n} + aF_{k} − (G_{n−1} − aF_{k+1}), G_{n−1} − aF_{k+1})
= gcd(G_{n−2} + aF_{k+2}, G_{n−1} − aF_{k+1})
= gcd(G_{n−2} + aF_{k+2}, G_{n−1} − aF_{k+1} − (G_{n−2} + aF_{k+2}))
= gcd(G_{n−2} + aF_{k+2}, G_{n−3} − aF_{k+3}).

Lemma 2. For integers m, k, and a,

gcd(G_{m} + a, G_{m+1} + a) = gcd(G_{m−(2k)} + aF_{2k−1}, G_{m−(2k+1)} − aF_{2k}).  (4)

Proof. We simplify gcd(G_{m} + a, G_{m+1} + a),

gcd(G_{m} + a, G_{m+1} + a) = gcd(G_{m} + a, G_{m+1} + a − (G_{m} + a))
= gcd(G_{m} + a, G_{m−1}).

Because F_{−1} = 1 and F_{0} = 0 we can write

gcd(G_{m} + a, G_{m+1} + a) = gcd(G_{m} + aF_{−1}, G_{m−1} + aF_{0}),

and applying (3) k times gives the result.

3 The sequence (f_{n}(1))

Theorem 3. For any integer n, we have

gcd(F_{4n−1} + 1, F_{4n} + 1) = F_{2n−1},  (5)
gcd(F_{4n} + 1, F_{4n+1} + 1) = \begin{cases}2, & if n ≡ 1 (mod 3), \\ 1, & otherwise, \end{cases}  (6)
gcd(F_{4n+1} + 1, F_{4n+2} + 1) = L_{2n},  (7)
gcd(F_{4n+2} + 1, F_{4n+3} + 1) = \begin{cases}2, & if n ≡ 2 (mod 3), \\ 1, & otherwise. \end{cases}  (8)

Proof. Let m = 4n − 1, k = n, and a = 1 in (4):

gcd(F_{4n−1} + 1, F_{4n} + 1) = gcd(F_{2n−1} + F_{2n−1}, F_{2n−2} − F_{2n})
= gcd(2F_{2n−1}, −F_{2n−1})
= F_{2n−1},

giving (5). Let m = 4n + 1, k = n, and a = 1 in (4):

gcd(F_{4n+1} + 1, F_{4n+2} + 1) = gcd(F_{2n+1} + F_{2n−1}, F_{2n} − F_{2n})
= F_{2n+1} + F_{2n−1}
= L_{2n},

giving (7). Let m = 4n, k = n, and a = 1 in (4):

gcd(F_{4n} + 1, F_{4n+1} + 1) = gcd(F_{2n} + F_{2n−1}, F_{2n−1} − F_{2n})
= gcd(F_{2n+1}, −F_{2n−2}).

Since gcd(F_{qn+r}, F_{n}) = gcd(F_{n}, F_{r}) for integers q, r, and n. This gives

gcd(F_{4n} + 1, F_{4n+1} + 1) = gcd(F_{2n−2}, F_{3}).

Because gcd(F_{k}, F_{r}) = F_{gcd(k,r)} for integers k and r,

gcd(F_{4n} + 1, F_{4n+1} + 1) = gcd(F_{2n−2}, F_{3})
= F_{gcd(2n−2,3)}
= \begin{cases}F_{3} = 2, & n ≡ 1 (mod 3), \\ F_{1} = 1, & otherwise, \end{cases}

which is (6). Let m = 4n + 2, k = n + 1, and a = 1 in (4):

gcd(F_{4n+2} + 1, F_{4n+3} + 1) = gcd(F_{2n} + F_{2n+1}, F_{2n−1} − F_{2n+2})
= gcd(F_{2n+2}, F_{2n−1} − F_{2n+2})
= gcd(F_{2n+2}, F_{2n−1})
= gcd(F_{3}, F_{2n−1})
= F_{gcd(3,2n−1)}
= \begin{cases}F_{3} = 2, & n ≡ 2 (mod 3), \\ F_{1} = 1, & otherwise, \end{cases}

which is (8).

4 The sequence (f_{n}(2))

Theorem 4. For any integer n, we have

gcd(F_{4n−1} + 2, F_{4n} + 2) = 1,  (9)
gcd(F_{4n} + 2, F_{4n+1} + 2) = 1,  (10)
gcd(F_{4n+1} + 2, F_{4n+2} + 2) = \begin{cases}3, & if n ≡ 0 (mod 2), \\ 1, & if n ≡ 1 (mod 2), \end{cases}  (11)
gcd(F_{4n+2} + 2, F_{4n+3} + 2) = \begin{cases}5, & if n ≡ 1 (mod 5), \\ 1, & otherwise. \end{cases}  (12)

Proof. Let m = 4n − 1, k = n, and a = 2 in (4):

gcd(F_{4n−1} + 2, F_{4n} + 2) = gcd(F_{2n−1} + 2F_{2n−1}, F_{2n−2} − 2F_{2n})
= gcd(3F_{2n−1}, F_{2n−1} + F_{2n})
= gcd(3F_{2n−1}, F_{2n+1}).

Since gcd(a, bc) = gcd(a, gcd(a, b)c) and gcd(F_{2n−1}, F_{2n+1}) = gcd(F_{2n−1}, F_{2}) = 1, we have

gcd(F_{4n−1} + 2, F_{4n} + 2) = gcd(3 gcd(F_{2n−1}, F_{2n+1}), F_{2n+1})
= gcd(3, F_{2n+1}) = gcd(F_{4}, F_{2n+1})
= F_{gcd(4,2n+1)} = F_{1} = 1,

which is (9). Let m = 4n, k = n, and a = 2 in (4):

gcd(F_{4n} + 2, F_{4n+1} + 2) = gcd(F_{2n} + 2F_{2n−1}, F_{2n−1} − 2F_{2n})
= gcd(F_{2n−1} + F_{2n+1}, −F_{2n} − F_{2n−2})
= gcd(L_{2n}, L_{2n−1})
= 1,

which is (10). Let m = 4n + 1, k = n, and a = 2 in (4):

gcd(F_{4n+1} + 2, F_{4n+2} + 2) = gcd(F_{2n+1} + 2F_{2n−1}, F_{2n} − 2F_{2n})
= gcd(F_{2n+1} + 2F_{2n−1} + 2F_{2n}, F_{2n})
= gcd(3F_{2n+1}, F_{2n})
= gcd(3, F_{2n}) = gcd(F_{4}, F_{2n})
= F_{gcd(4,2n)}
= \begin{cases}F_{4} = 3, & if n ≡ 0 (mod 2), \\ F_{1} = 1, & if n ≡ 1 (mod 2), \end{cases}

which is (11). Let m = 4n + 2, k = n, and a = 2 in (4):

gcd(F_{4n+2} + 2, F_{4n+3} + 2) = gcd(F_{2n+2} + 2F_{2n−1}, F_{2n+1} − 2F_{2n})
= gcd(F_{2n+2} + 2F_{2n−1}, −F_{2n} + F_{2n−1})
= gcd(F_{2n+2} + 2F_{2n−1}, −F_{2n−2})
= gcd(F_{2n−2}, F_{2n+2} + 2F_{2n}).

Since F_{2n+2} + 2F_{2n} = F_{2n+1} + 3F_{2n} = 4F_{2n} + F_{2n−1}, we have

gcd(F_{4n+2} + 2, F_{4n+3} + 2) = gcd(F_{2n−2}, 4F_{2n} + F_{2n−1})
= gcd(F_{2n−2}, 5F_{2n})
= gcd(F_{2n−2}, 5 gcd(F_{2n−2}, F_{2n}))
= gcd(F_{2n−2}, 5) = gcd(F_{2n−2}, F_{5})
= F_{gcd(2n−2,5)}
= \begin{cases}F_{5} = 5, & if n ≡ 1 (mod 5) \\ F_{1} = 1, & otherwise, \end{cases}

which is (12).

5 The sequences (f_{n}(−1)), (f_{n}(−2)), and (ℓ_{n}(1))

Applying the same methods we get Theorem 5. For any integer n, we have

gcd(F_{4n−1} − 1, F_{4n} − 1) = L_{2n−1},
gcd(F_{4n} − 1, F_{4n+1} − 1) = \begin{cases}2, & if n ≡ 1 (mod 3), \\ 1, & otherwise, \end{cases}
gcd(F_{4n+1} − 1, F_{4n+2} − 1) = F_{2n},
gcd(F_{4n+2} − 1, F_{4n+3} − 1) = \begin{cases}2, & if n ≡ 2 (mod 3), \\ 1, & otherwise. \end{cases}

Theorem 6. For any integer n, we have

gcd(F_{4n−1} − 2, F_{4n} − 2) = 1,
gcd(F_{4n} − 2, F_{4n+1} − 2) = \begin{cases}5, & if n ≡ 4 (mod 5), \\ 1, & otherwise,. \end{cases}
gcd(F_{4n+1} − 2, F_{4n+2} − 2) = \begin{cases}1, & if n ≡ 0 (mod 2), \\ 3, & if n ≡ 1 (mod 2), \end{cases}
gcd(F_{4n+2} − 2, F_{4n+3} − 2) = 1.

Theorem 7. For any integer n, we have

gcd(L_{4n−1} + 1, L_{4n} + 1) = \begin{cases}3, & if n ≡ 0 (mod 6), \\ 1, & if n ≡ 1 (mod 6), \\ 6, & if n ≡ 2 (mod 6), \\ 1, & if n ≡ 3 (mod 6), \\ 3, & if n ≡ 4 (mod 6), \\ 2, & if n ≡ 5 (mod 6). \end{cases}

gcd(L_{4n} + 1, L_{4n+1} + 1) = \begin{cases}4, & if n ≡ 1 (mod 3), \\ 1, & otherwise, \end{cases}
gcd(L_{4n+1} + 1, L_{4n+2} + 1) = \begin{cases}2, & if n ≡ 0 (mod 3), \\ 1, & otherwise, \end{cases}
gcd(L_{4n+2} + 1, L_{4n+3} + 1) = \begin{cases}4, & if n ≡ 2 (mod 3), \\ 1, & otherwise. \end{cases}

6 The proofs of Theorems 1 and 2

First we give the proof of Theorem 1. Let m = 4n − 1 and k = n in (4):

gcd(G_{4n−1} + a, G_{4n} + a) = gcd(G_{2n−1} + aF_{2n−1}, G_{2n−2} − aF_{2n})
= gcd(αF_{2n−3} + βF_{2n−2} + aF_{2n−1}, αF_{2n−4} + βF_{2n−3} − aF_{2n}).

Using the recursion relation for F_{n}, let

a_{n} = αF_{2n−3} + βF_{2n−2} + aF_{2n−1} = (α + a)F_{2n−3} + (β + a)F_{2n−2}

and

b_{n} = αF_{2n−4} + βF_{2n−3} − aF_{2n} = (−α + β − a)F_{2n−3} + (α − 2a)F_{2n−2}.

Since gcd(a_{n}, b_{n}) divides γa_{n} + θb_{n} for any integers γ and θ, and

(α + a)b_{n} − (−α + β − a)a_{n} = (α^{2} + αβ − β^{2} − a^{2})F_{2n−2}
(α − 2a)a_{n} − (β + a)b_{n} = (α^{2} + αβ − β^{2} − a^{2})F_{2n−3},

we see that if α^{2} + αβ − β^{2} − a^{2} ≠ 0, then the greatest common divisor of the two numbers is |α^{2} + αβ − β^{2} − a^{2}|. Therefore gcd(a_{n}, b_{n}) divides α^{2} + αβ − β^{2} − a^{2}. That is to say,

gcd(G_{4n−1} + a, G_{4n} + a) ≤ |α^{2} + αβ − β^{2} − a^{2}|.

If we let m = 4n + 1 and k = n in (4) we have, in exactly the same way, that

gcd(G_{4n+1} + a, G_{4n+2} + a) ≤ |α^{2} + αβ − β^{2} − a^{2}|.

In the following we give the proof of Theorem 2. Let m = 4n and k = n in (4):

gcd(G_{4n} + a, G_{4n+1} + a) = gcd(G_{2n} + aF_{2n−1}, G_{2n−1} − aF_{2n})
= gcd(αF_{2n−2} + βF_{2n−1} + aF_{2n−1}, αF_{2n−3} + βF_{2n−2} − aF_{2n}).

Using the recursion relation for F_{n}, let

a_{n} = αF_{2n−2} + βF_{2n−1} + aF_{2n−1} = αF_{2n−2} + (β + a)F_{2n−1}

and

b_{n} = αF_{2n−3} + βF_{2n−2} − aF_{2n} = (−α + β − a)F_{2n−2} + (α − a)F_{2n−1}.

Since gcd(a_{n}, b_{n}) divides γa_{n} + θb_{n} for any integers γ and θ, and

(α − a)a_{n} − (a + β)b_{n} = (α^{2} + αβ − β^{2} + a^{2})F_{2n−2}
αb_{n} − (β − α − a)a_{n} = (α^{2} + αβ − β^{2} + a^{2})F_{2n−1},

we see that if α^{2} + αβ − β^{2} + a^{2} ≠ 0, then the greatest common divisor of the two numbers is |α^{2} + αβ − β^{2} + a^{2}|. Therefore gcd(a_{n}, b_{n}) divides α^{2} + αβ − β^{2} + a^{2}. That is to say,

gcd(G_{4n} + a, G_{4n+1} + a) ≤ |α^{2} + αβ − β^{2} + a^{2}|.

If we let m = 4n + 2 and k = n in (4) we have, in exactly the same way, that

gcd(G_{4n+2} + a, G_{4n+3} + a) ≤ |α^{2} + αβ − β^{2} + a^{2}|.

7 Acknowledgement

The author would like to thank the referee for some useful comments and suggestions.

References

[1] U. Dudley and B. Tucker, Greatest common divisors in altered Fibonacci sequences, Fibonacci Quart. 9 (1971), 89–91.

[2] S. Hernández and F. Luca, Common factors of shifted Fibonacci numbers, Period. Math. Hungar. 47 (2003), 95–110.

[3] T. Koshy, Fibonacci and Lucas Numbers with Applications, Wiley-Interscience, 2001.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11A05. Keywords: Fibonacci numbers, Lucas numbers, generalized Fibonacci numbers.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000071}, \underline{A001611}, and \underline{A157725}.)

Received January 31 2011; revised version received March 26 2011. Published in Journal of Integer Sequences, March 26 2011.

Return to Journal of Integer Sequences home page.