Greatest Common Divisors of Shifted Fibonacci Sequences Revisited

Annalena Rahn and Martin Kreh Institute of Mathematics and Applied Computer Science University of Hildesheim Samelsonplatz 1 31141 Hildesheim Germany

               rahnan@uni-hildesheim.de
              kreh@imai.uni-hildesheim.de

Abstract

In 2011, Chen computed the greatest common divisors of consecutive shifted Fibonacci numbers F_{n} + a and F_{n+1} + a for a ∈ {±1, ±2}. He also showed that gcd(F_{n} + a, F_{n+1} + a) is bounded if a ≠ ±1. This was later generalized by Spilker, who also showed that gcd(F_{n} + a, F_{n+1} + a) is periodic if a ≠ ±1. In this article, we compute the greatest common divisor for a = ±3 and we show how the results given in this article compare to bounds derived by Chen and periods derived by Spilker. We further give a necessary criterion for an integer d to occur as such a greatest common divisor.

1 Introduction and results

Let (F_{n})_{n≥1} be the Fibonacci sequence defined by the recursion

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

Using this recursion, F_{n} can be extended to integer indices, where we have the relation F_{−n} = (−1)^{n+1}F_{n}. In this article, we want to investigate greatest common divisors of the form gcd(F_{n} + a, F_{n+1} + a).

It is well known, that gcd(F_{n}+a, F_{n+1}+a) = 1 for all n if a = 0, i.e., consecutive Fibonacci numbers are coprime. In 1971, Dudley and Tucker [2] showed that gcd(F_{n} + a, F_{n+1} + a) is unbounded for a = ±1 by showing that

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

Here (L_{n})_{n≥1} denotes the Lucas sequence defined by L_{n} = L_{n−1} + L_{n−2}, L_{1} = 1, L_{2} = 3. In 2011, Chen [1] determined gcd(F_{n} + a, F_{n+1} + a) for a ∈ {±1, ±2} and proved the

following bound.

Theorem A ([1]). Let n, a ∈ ℤ. Then

• 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.

Spilker [4] generalized some of Chen’s results. Among other, he showed the following theorems (in even greater generality than mentioned here).

Theorem B ([4]). For all a ∈ ℤ, gcd(F_{n} + a, F_{n+1} + a) divides a^{2} + (−1)^{n}. If a ≠ ±1, the function n ↦ gcd(F_{n} + a, F_{n+1} + a) is simply periodic and a period p ≤ (a^{4} − 1)^{2} can be chosen by

F_{p} ≡ 0 (mod a^{4} − 1), F_{p+1} ≡ 1 (mod a^{4} − 1).  (5)

Theorem C ([4]). Let a ∈ ℤ with |a| > 1, k ∈ ℕ and i ∈ {0, 1}.

1. If F_{2k−i} ≡ α_{i} (mod a^{2} + 1) with 0 ≤ α_{i} < a^{2} + 1, then

gcd(F_{4k} + a, F_{4k+1} + a) = gcd(α_{0} + aα_{1}, aα_{0} − α_{1}, a^{2} + 1),  (6)
gcd(F_{4k−2} + a, F_{4k−1} + a) = gcd(α_{0} + (a − 1)α_{1}, aα_{0} − (a + 1)α_{1}, a^{2} + 1). (7)

2. If F_{2k−i} ≡ β_{i} (mod a^{2} − 1) with 0 ≤ α_{i} < a^{2} − 1, then

gcd(F_{4k−1} + a, F_{4k} + a) = gcd((a + 1)β_{1}, (a − 1)β_{0} − aβ_{1}, a^{2} − 1),  (8)
gcd(F_{4k−3} + a, F_{4k−2} + a) = gcd(β_{0} − (a + 2)β_{1}, (a − 1)β_{0} − (a − 1)β_{1}, a^{2} − 1). (9)

Spilker also answered the question in which cases the upper bound of Chen is being attained. To state this, define the entry point of m ∈ ℕ as e(m) := min{i ∈ ℕ : m|F_{i}} (the existence of e(m) follows from [5, Theorem 1]).

Theorem D ([4]). Let |a| > 1. The function n ↦ gcd(F_{n} + a, F_{n+1} + a) has the upper bound m = a^{2} + 1 as a value if and only if e(m) is odd and a ≡ ±F_{e(m)+1} (mod m). The function n ↦ gcd(F_{n} + a, F_{n+1} + a) has the value m = a^{2} − 1 on the odd integers if and only if a = 2 or e(m) is even and a ≡ −F_{e(m)+1} (mod m).

In this article, we will use Chen’s method to determine gcd(F_{n} + a, F_{n+1} + a) for a = ±3. More precisely, we will show the following theorems.

Theorem 1. We have

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

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

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

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

Theorem 2. We have

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

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

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

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

We will further examine the sets

G_{0}(a) := {gcd(F_{2n} +a, F_{2n+1} +a) : n ∈ ℤ} and G_{1}(a) := {gcd(F_{2n+1} +a, F_{2n+2} +a) : n ∈ ℤ}.

(10)

Let D(n) denote the set of divisors of n. We already know from Theorem B that G_{0}(a) ⊂ D(a^{2} + 1) and G_{1}(a) ⊂ D(a^{2} − 1) Theorem D characterizes the cases in which a^{2} + 1 ∈ G_{0}(a) and a^{2} − 1 ∈ G_{1}(a). We will show the following extension.

Theorem 3.

1. We have 1 ∈ G_{0}(a) and {1, a + 1} ⊂ G_{1}(a) for all a.

2. We have 2 ∈ G_{0}(a) if and only if a ≡ 1 (mod 2) and 2 ∈ G_{1}(a) if and only if a ≡ 1 (mod 4).

3. Let d ≠ 1, 2 be a divisor of a^{2}+1. If d ∈ G_{0}(a), then e(d) is odd and a ≡ ±F_{e(d)+1} (mod d).

4. Let d ≠ 1, 2 be a divisor of a^{2} − 1 such that a ≢ ±1 (mod d). If d ∈ G_{1}(a), then e(d) is even and a ≡ −F_{e(d)+1} (mod d).

Before proving Theorems 1, 2, and 3, we will start with some lemmas in the next section. In Section 5, we will compare our results to those of Spilker and raise some new questions.

2 Preliminaries

We will need a few results about divisibility and greatest common divisors of Fibonacci numbers. We will state common facts without proof and prove some special identities. In the following we always assume that n is a (not necessarily positive) integer. Lemma 4. For all a, b, c ∈ ℤ we have gcd(a, bc) = gcd(a, gcd(a, b)c). Lemma 5 ([3]). We have the following identities and rules about divisibility and greatest common divisors of Fibonacci numbers.

• For all m, n ∈ ℕ we have F_{m+n} = F_{m+1}F_{n} + F_{m}F_{n−1}.

• For all n ∈ ℕ we have F_{n+1}F_{n−1} = F_{n}^{2} + (−1)^{n}.

• F_{n} ≡ 0 (mod 2) ⇔ n ≡ 0 (mod 3).

• F_{n} ≡ 0 (mod 4) ⇔ n ≡ 0 (mod 6).

• F_{n} ≡ 0 (mod 5) ⇔ n ≡ 0 (mod 5).

• F_{n} ≡ 0 (mod 8) ⇔ n ≡ 0 (mod 6).

• For all n ∈ ℕ we have gcd(F_{n}, F_{n+1}) = 1.

• For all m, n ∈ ℕ we have gcd(F_{m}, F_{n}) = F_{gcd(m,n)}. Lemma 6. For all n ∈ ℤ we have

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

Proof. Let n = 3m + k with k ∈ {−1, 0, 1}. Then we get with Lemma 5

gcd(F_{2n}, 4) = gcd(F_{6m+2k}, 4) = \begin{cases}4, & if k = 0; \\ 1, & otherwise. \end{cases}  (12)

Lemma 7. For all n ∈ ℤ we have

gcd(10, F_{2n−1} − 2F_{2n}) = \begin{cases}2, & if n ≡ 2 (mod 3); \\ 1, & otherwise. \end{cases}  (13)

Proof. Analogously to above, F_{2n−1} −2F_{2n} is divisible by 2 if and only if 2n−1 ≡ 0 (mod 3), i.e., if n ≡ 2 (mod 3). Further we have

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

and for any residue class of n modulo 5 we can pick one of the three terms above such that one summand is divisible by 5 while the other is not (for example, if n ≡ 4 (mod 5) then F_{2n−3} is divisible by 5 and 3F_{2n−2} is not divisible by 5 due to Lemma 5). Thus F_{2n−1} − 2F_{2n} is not divisible by 5.

Lemma 8. For all n ∈ ℤ we have

gcd(10, F_{2n−1} − 3F_{2n}) = \begin{cases}2, & if n ≡ 1 (mod 3) and n ≢ 4 (mod 5); \\ 5, & if n ≢ 1 (mod 3) and n ≡ 4 (mod 5); \\ 10, & if n ≡ 1 (mod 3) and n ≡ 4 (mod 5); \\ 1, & otherwise. \end{cases}  (15)

Proof. It suffices to show that 2|F_{2n−1} −3F_{2n} if and only if n ≡ 1 (mod 3) and 5|F_{2n−1} −3F_{2n} if and only if n ≡ 4 (mod 5). With Lemma 5, F_{2n−1} − 3F_{2n} = −F_{2n−2} − 2F_{2n} is divisible by 2 if and only if 2n − 2 ≡ 0 (mod 3), i.e., if n ≡ 1 (mod 3) and F_{2n−1} − 3F_{2n} = −5F_{2n} + F_{2n+2} is divisible by 5 if and only if 2n + 2 ≡ 0 (mod 5), i.e., if n ≡ 4 (mod 5).

Lemma 9. For all n ∈ ℤ we have

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

Proof. Let n = 3m + k with k ∈ {−1, 0, 1}. Then we get with Lemma 5

F_{2n−1} = F_{6m+2k−1} ≡ \begin{cases}2 (mod 4), & if k = −1; \\ 1 (mod 2), & otherwise, \end{cases}  (17)

and this shows the lemma.

Lemma 10. For all n ∈ ℤ we have

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

Proof. Since F_{2n−1} + 3F_{2n} = F_{−2n+1} − 3F_{−2n} = F_{−2n−1} − 2F_{−2n}, this follows from Lemma 7. Lemma 11. For all n ∈ ℤ we have

gcd(10, F_{2n+1} + 3F_{2n}) = \begin{cases}2, & if n ≡ 2 (mod 3) and n ≢ 1 (mod 5); \\ 5, & if n ≢ 2 (mod 3) and n ≡ 1 (mod 5); \\ 10, & if n ≡ 2 (mod 3) and n ≡ 1 (mod 5); \\ 1, & otherwise. \end{cases}  (19)

Proof. Since F_{2n+1} + 3F_{2n} = F_{−2n−1} − 3F_{−2n}, this follows from Lemma 8.

The following lemma due to Chen is the main part for computing the greatest common divisors. Lemma 12 ([1]). For all m, k, a ∈ ℤ we have

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

3 Proof of Theorem 1 and Theorem 2

In this section we will give the proof for Theorems 1 and 2. Proof of Theorem 1.

1. We use Lemma 12 with m = 4n − 1, k = n, a = 3 to get

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

Since gcd(F_{2n+1}, F_{2n+2}) = 1, we get with Lemma 5

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

and since

gcd(6, 2n + 2) = \begin{cases}6, & if n ≡ 2 (mod 3); \\ 2, & otherwise, \end{cases}  (24)

this proves the first case.

2. We use Lemma 12 with m = 4n, k = n, a = 3 to get

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

With Lemma 4 we get

gcd(F_{4n} + 3, F_{4n+1} + 3) = gcd(10 · gcd(F_{2n}, F_{2n−1} − 3F_{2n}), F_{2n−1} − 3F_{2n})  (28)
= gcd(10, F_{2n−1} − 3F_{2n}),  (29)

thus the claim follows with Lemma 8.

3. We use Lemma 12 with m = 4n + 1, k = n, a = 3 and Lemma 4 to get

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

With Lemma 6 and Lemma 5 we get

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

4. We use Lemma 12 with m = 4n + 2, k = n, a = 3 to get

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

With Lemma 4 we get

gcd(F_{4n+2} + 3, F_{4n+3} + 3) = gcd(10 · gcd(F_{2n}, F_{2n−1} − 2F_{2n}), F_{2n−1} − 2F_{2n}) (38)
= gcd(10, F_{2n−1} − 2F_{2n}),  (39)

hence the statement follows with Lemma 7.

Proof of Theorem 2.

1. We use Lemma 12 with m = 4n − 1, k = n, a = −3 to get

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

Using Lemma 4 we get

gcd(F_{4n−1} − 3, F_{4n} − 3) = gcd(8 · gcd(F_{2n}, 4F_{2n} − F_{2n−1}), 4F_{2n} − F_{2n−1})  (43)
= gcd(8, 4F_{2n} − F_{2n−1}),  (44)

thus the claim folows with Lemma 9.

2. We use Lemma 12 with m = 4n, k = n, a = −3 to get

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

(45)

Using Lemma 4 gives

gcd(F_{4n} − 3, F_{4n+1} − 3) = gcd(10 · gcd(F_{2n}, F_{2n−1} + 3F_{2n}), F_{2n−1} + 3F_{2n})  (46)
= gcd(10, F_{2n−1} + 3F_{2n}),  (47)

and Lemma 10 gives the result.

3. We use Lemma 12 with m = 4n + 1, k = n, a = −3 to get

gcd(F_{4n+1} − 3, F_{4n+2} − 3) = gcd(F_{2n+1} − 3F_{2n−1}, 4F_{2n})  (48)
= gcd(F_{2n−3}, 8F_{2n−1} − 4F_{2n−3}) = gcd(F_{2n−3}, 8F_{2n−1}) (49)
= gcd(F_{2n−3}, 8) = gcd(F_{2n−3}, F_{6}).  (50)

Using Lemma 5 gives gcd(F_{4n+1} − 3, F_{4n+2} − 3) = F_{gcd(6,2n−3)}, and since

gcd(6, 2n − 3) = \begin{cases}3, & if n ≡ 0 (mod 3); \\ 1, & otherwise, \end{cases}  (51)

we get

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

4. We use Lemma 12 with m = 4n + 2, k = n, a = −3 to get

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

Using Lemma 4, we get gcd(F_{4n+2} − 3, F_{4n+3} − 3) = gcd(10, F_{2n+1} + 3F_{2n}), hence the statement follows with Lemma 11.

4 Proof of Theorem 3

To prove Theorem 3, we first note that

gcd(F_{0} + a, F_{1} + a) = gcd(a, a + 1) = 1,  (56)
gcd(F_{1} + a, F_{2} + a) = gcd(a + 1, a + 1) = a + 1,  (57)
gcd(F_{3} + a, F_{4} + a) = gcd(a + 2, a + 3) = 1.  (58)

This proves the first statement. For the second statement, note that a has to be odd, since otherwise 2 ∤ a^{2} ± 1. So suppose that a is odd. Then we have

gcd(F_{4} + a, F_{5} + a) = gcd(a + 3, a + 5) = 2,  (59)

hence 2 ∈ G_{0}(a). We turn our attention to G_{1}(a). First let a ≡ 1 (mod 4). We have gcd(F_{7} + a, F_{8} + a) = gcd(F_{7} + a, F_{6})|8 and F_{7} + a ≡ 2 (mod 4), F_{8} + a ≡ 2 (mod 4), hence

2 = gcd(F_{7} + a, F_{8} + a) ∈ G_{1}(a).  (60)

Assume now that a ≡ 3 (mod 4). We will use the formula of the greatest common divisor given in Theorem C. Let

A_{1} := (a+1)β_{1}, B_{1} := (a−1)β_{0} −aβ_{1}, A_{2} := β_{0} −(a+2)β_{1}, B_{2} := (a−1)β_{0} −(a−1)β_{1},

(61)

where β_{0}, β_{1} are defined as in Theorem C. Since a^{2} − 1 ≡ 0 (mod 4), we can only have 2 ∈ G_{1}(a) if there is an i ∈ {1, 2} such that both A_{i} and B_{i} are even and further A_{i} ≡ 2 (mod 4) or B_{i} ≡ 2 (mod 4).

• Then we have A_{1} ≡ 0 (mod 4) in any case.

• We have B_{1} ≡ 2 (mod 4) if and only if 2β_{0}+β_{1} ≡ 2 (mod 4). Since β_{i} ≡ F_{2k−i} (mod a^{2}− 1), this holds if and only if 2F_{2k} + F_{2k−1} ≡ 2 (mod 4), i.e., if and only if F_{2k+2} ≡ 2 (mod 4). From Lemma 5, this holds if and only if 2k + 2 ≡ 0 (mod 3) and 2k + 2 ≢ 0 (mod 6), which is impossible.

• We have A_{2} ≡ 2 (mod 4) if and only if β_{0} − β_{1} ≡ 2 (mod 4). This is the case precisely when F_{2k} − F_{2k−1} = F_{2k−2} ≡ 2 (mod 4). From Lemma 5, this holds if and only if 2k − 2 ≡ 0 (mod 3) and 2k − 2 ≢ 0 (mod 6), which is impossible.

• Finally, we have B_{2} ≡ 2 (mod 4) if and only if β_{0} − β_{1} ≡ 1 (mod 2), in which case we also have A_{2} ≡ 1 (mod 2).

Hence 2 ∉ G_{1}(a) if a ≡ 3 (mod 4).

For the proof of the fourth statement, we mimic Spilker’s proof of Theorem D. We use the identity F_{m+n} = F_{m+1}F_{n} + F_{m}F_{n−1} from Lemma 5 to find, that the integers F_{1}, F_{2}, … are modulo d equivalent to

F_{1},  F_{2},  …,  F_{e(d)−1},  0,  (62)
F_{e(d)+1}F_{1},  F_{e(d)+1}F_{2},  …,  F_{e(d)+1}F_{e(d)−1},  0,  (63)
F_{e(d)+1}^{2}F_{1},  F_{e(d)+1}^{2}F_{2},  …,  F_{e(d)+1}^{2}F_{e(d)−1},  0,  …  (64)

where F_{n}^{k} := (F_{n})^{k}. Hence

F_{ke(d)} ≡ 0 (mod d) and F_{ke(d)+1} ≡ F_{e(d)+1}^{k} (mod d) for all k ∈ ℕ.  (65)

From Lemma 5, we get

F_{e(d)+1} = F_{e(d)} + F_{e(d)−1} ≡ F_{e(d)−1} (mod d),  (66)
F_{e(d)+1}F_{e(d)−1} = F_{e(d)}^{2} + (−1)^{e(d)} ≡ (−1)^{e(d)} (mod d),  (67)

hence we further have

F_{e(d)+1}^{2} ≡ (−1)^{e(d)} (mod d).  (68)

We begin with the set G_{0}(a). Suppose that d ∈ G_{0}(a), i.e.,

d = gcd(F_{n_{0}} + a, F_{n_{0}+1} + a) = gcd(F_{n_{0}} + a, F_{n_{0}−1})  (69)

for some even integer n_{0}. Then F_{n_{0}} + a ≡ 0 (mod d) and F_{n_{0}−1} ≡ 0 (mod d). From [5, Theorem 3], n_{0} − 1 is a multiple of e(d), i.e., n_{0} = ke(d) + 1 for some k ∈ ℤ. Since n_{0} is even, k and e(d) are odd, thus (65) and (68) give

F_{n_{0}} = F_{ke(d)+1} ≡ F_{e(d)+1}^{k} ≡ (−1)^{\frac{k−1}{2}} F_{e(d)+1} (mod d),  (70)

hence a ≡ ±F_{e(d)+1} (mod d), and this proves the statement for G_{0}(a).

The statement for the set G_{1}(a) can be proved almost analogously. Since here n_{0} is odd, ke(d) is even. If k was even, we would get

F_{n_{0}} ≡ F_{e(d)+1}^{k} ≡ ±1 (mod d),  (71)

hence a ≡ ±1 (mod d). This contradiction yields that k is odd, thus e(d) is even and we get

a ≡ −F_{n_{0}} ≡ −F_{e(d)+1}^{k} ≡ − ((−1)^{e(d)})^{\frac{k−1}{2}} F_{e(d)+1} ≡ −F_{e(d)+1} (mod d).  (72)

5 Remarks and future work

In this section we will briefly compare our results to the general results of Spilker [4].

For a = ±2, Theorems B, C, and D state, that gcd(F_{n} ± 2, F_{n+1} ± 2) is a divisor of 5 respectively 3, a period of gcd(F_{n} ± 2, F_{n+1} ± 2) is given by 40, and since

e(3) = 4, F_{5} = 5 ≡ 2 (mod 3)  and  e(5) = 5, F_{6} = 8 ≡ −2 (mod 5), (73)

the values 3 and 5 are attained. The exact values of gcd(F_{n} ± 2, F_{n+1} ± 2) can be found in [1] and [4], it turns out, that 40 is indeed the smallest period.

For a = ±3, Theorems B, C, and D state, that gcd(F_{n} ± 3, F_{n+1} ± 3) is a divisor of 10 respectively 8, a period of gcd(F_{n} ± 3, F_{n+1} ± 3) is given by 120, and since

e(8) = 6, F_{7} = 13 ≡ −3 (mod 8)  and  e(10) = 15, F_{16} = 987 ≡ −3 (mod 10),

(74)

the values 8 and 10 are attained. Theorem 3 additionally states, that the value 2 is attained by gcd(F_{n_{0}} ± 3, F_{n_{0}+1} ± 3) for some even n_{0}, while it is attained for some odd n_{0} only in the case a = −3. This, together with Theorems 1 and 2, shows that the cases a = ±3 are the first ones, in which not every divisor of a^{2} + 1 respectively a^{2} − 1 occurs as a greatest common divisor. From the exact values computed in Theorems 1 and 2, we also see that the smallest period of gcd(F_{n} ± 3, F_{n+1} ± 3) is not 120, but 60.

These observations give rise to some new questions:

Problem 13. Given a ∈ ℤ with |a| ≥ 2, what is the smallest period of gcd(F_{n} +a, F_{n+1} +a)?

Problem 14. Theorem 3 only gives a necessary but not a sufficient condition for a divisor d of a^{2} ± 1 to occur as a greatest common divisor. Theorem D gives also a sufficient condition for d = a^{2} ± 1 to occur as a greatest common divisor. Are there any sufficient conditions for d ≠ a^{2} ± 1?

Problem 15. Let a ∈ ℤ with |a| ≥ 2. Since G_{0}(a) ⊂ D(a^{2} + 1) and G_{1}(a) ⊂ D(a^{2} − 1), we have |G_{0}(a)| ≤ τ(a^{2} + 1) and |G_{1}(a)| ≤ τ(a^{2} − 1) (where τ(n) = ∑_{d|n} 1 denotes the divisor function). What are the (exact or asymptotic) sizes of G_{0}(a) and G_{1}(a)?

References

[1] K.-W. Chen, Greatest common divisors in shifted Fibonacci sequences, J. Integer Sequences 14 (2011), Article 11.4.7.

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

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

[4] J. Spilker, The gcd of the shifted Fibonacci sequence, in Jürgen Sander, Jörn Steuding, and Rasa Steuding, eds., From Arithmetic to Zeta-Functions, Springer, 2016, pp. 473– 483.

[5] D. D. Wall, Fibonacci series modulo m, Amer. Math. Monthly 67 (1960), 525–532.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11A05. Keywords: shifted Fibonacci sequence, greatest common divisor.

(Concerned with sequence \underline{A000045}.)

Received January 31 2018; revised version received June 20 2018. Published in Journal of Integer Sequences, August 22 2018.

Return to Journal of Integer Sequences home page.