The Greatest Common Divisor of Shifted Fibonacci Numbers

Le Duc Hieu École Polytechnique

Institut Polytechnique de Paris Palaiseau France

hieu.le@polytechnique.edu

Jürgen Spilker Institute of Mathematics University of Freiburg

79085 Freiburg im Breisgau

Germany

juergen.spilker@t-online.de

Luu Ba Thang

Department of Mathematics and Informatics

Hanoi National University of Education

136 Xuan Thuy Cau Giay Hanoi Vietnam

thanglb@hnue.edu.vn

Abstract

Let F_{n} and L_{n} denote the Fibonacci and Lucas numbers, respectively. We generalize the well-known formula gcd(F_{6n+3} + 1, F_{6n+6} + 1) = L_{3n+2} if n is even. We find conditions on a, s, and t so that the functions n ↦ gcd(F_{n} + s, F_{n+a} + s) and n ↦ gcd(F_{n} + s, F_{n+1} + t) are unbounded. Finally, we generalize this for three shifted Fibonacci numbers.

1 Introduction

The Fibonacci sequence (F_{n})_{n≥0} and Lucas sequence (L_{n})_{n≥0} are defined by the recursions

F_{0} = 0, F_{1} = 1; F_{n} = F_{n−1} + F_{n−2}, n ≥ 2;

and

L_{0} = 2, L_{1} = 1; L_{n} = L_{n−1} + L_{n−2}, n ≥ 2.

Notice that F_{n} and L_{n} can be extended to integer indices by the recursion. In 1971, Dudley and Tucker [3] showed that gcd(F_{n} + s, F_{n+1} + s) is unbounded for s = ±1. In 2011, Chen [1] determined gcd(F_{n} + s, F_{n+1} + s) for s ∈ {±1, ±2} and proved that gcd(F_{n} + s, F_{n+1} + s) is bounded for s ≠ ±1. In 2018, Rahn and Kreh [7] determined gcd(F_{n} + s, F_{n+1} + s) for s = ±3. In 2016, Spilker [8] proved that gcd(F_{n} + s, F_{n+1} + s) divides s^{2} + (−1)^{n}. If s ≠ ±1 then the function n ↦ gcd(F_{n} + s, F_{n+1} + s) is periodic. In 2020, Chen and Pan [2] considered general second-order linear homogeneous recurrence functions W_{n}. They proved a criterion of periodicity of gcd(W_{n} + s, W_{n+k} + t). They transformed problems about the gcd(W_{n} + s, W_{n+k} + t) with arbitrarily k into those with k = 1 and calculated on this way some gcd(W_{n} + s, W_{n+1} + t).

Let ℕ denote the set of positive integers, ℕ_{0} denote the set of non-negative integers, and ℤ denote the set of integers. In this article, we generalize these ideas to compute

gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+i+k} + (−1)^{b}F_{k−1})

in Theorem 2. Then in Theorem 7, we investigate necessary and sufficien conditions on a ∈ ℕ, s ∈ ℤ, so that the function

\begin{matrix}D_{a,s} : ℕ_{0} & → ℕ \\ n & ↦ gcd(F_{n} + s, F_{n+a} + s) \end{matrix}

is bounded. In Theorem 8, we treat the same problem for C_{s,t}(n) := gcd(F_{n} + s, F_{n+1} + t). If D_{a,s}(n) and C_{s,t}(n) are bounded, they are periodic (Theorem 9 and Theorem 10). Finally, we prove that the function

\begin{matrix}E_{a,s} : ℕ_{0} & → ℕ \\ n & ↦ gcd(F_{n} + s, F_{n+a} + s, F_{n+2a} + s) \end{matrix}

is bounded without exceptions.

2 Results

Firstly, we have a theorem on the gcd of Fibonacci numbers with shift 1 and with general shift k ≥ 1.

Theorem 1. Let a, b, i ∈ ℤ with i = 2j + 1 and set

D := gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+i+1} + (−1)^{b}).

Then

D = \begin{cases}F_{an+b+j}, & if an + j is odd; \\ L_{an+b+j}, & if an + j is even \end{cases}

for all n ∈ ℕ_{0}. Theorem 2. Let a, b, i, k ∈ ℤ with i = 2j − 1, k ≥ 1 and set

D := gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+i+k} + (−1)^{b}F_{k−1}).

Then

D = \begin{cases}F_{an+b+j} gcd(L_{an+b+j−1}, F_{k}), & if an + j is odd; \\ L_{an+b+j} gcd(F_{an+b+j−1}, F_{k}), & if an + j is even, \end{cases}

for all n ∈ ℕ_{0}. Corollary 3. Let a, b, i ∈ ℤ with i = 2j − 1. Then

gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+i+1}) = \begin{cases}F_{an+b+j}, & if an + j is odd; \\ L_{an+b+j}, & if an + j is even, \end{cases}

for all n ∈ ℕ_{0}. Corollary 4. Let a, b, i, j ∈ ℤ with i = 2j − 1. Then

gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+i+2} + (−1)^{b}) = \begin{cases}F_{an+b+j}, & if an + j is odd; \\ L_{an+b+j}, & if an + j is even, \end{cases}

for all n ∈ ℕ_{0}. Corollary 5. Let a, b, i, j ∈ ℤ with i = 2j − 1. Then

gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+i+3} + (−1)^{b}) = \begin{cases}λF_{an+b+j}, & if an + j is odd; \\ λL_{an+b+j}, & if an + j is even, \end{cases}

for all n ∈ ℕ_{0}, where

λ := \begin{cases}2, & if an + b + j ≡ 1 (mod 3); \\ 1, & otherwise. \end{cases}

Corollary 6. Let a, b, i ∈ ℤ with i = 2j − 1. Then

gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+i+4} + (−1)^{b}2) = \begin{cases}λF_{an+b+j}, & if an + j is odd; \\ δL_{an+b+j}, & if an + j is even, \end{cases}

for n ∈ ℕ_{0}, where

λ := \begin{cases}3, & if an + b + j ≡ 3 (mod 4); \\ 1, & otherwise, \end{cases}

and

δ := \begin{cases}3, & if an + b + j ≡ 1 (mod 4); \\ 1, & otherwise. \end{cases}

The next theorem characterizes the boundedness of D_{a,s}(n) := gcd(F_{n} + s, F_{n+a} + s). Theorem 7. Let a ∈ ℕ, s ∈ ℤ, and set S := {(1, 1), (1, −1), (3, 1), (3, −1)} ∪ {(4k + 2, F_{2k+1}) : k ≥ 0} ∪ {(4k + 2, −F_{2k+1}) : k ≥ 0}. Then D_{a,s}(n) is bounded on ℕ_{0} if and only if (a, s) ∉ S.

Let e_{s,t}(n) := s^{2}+st−t^{2}+(−1)^{n} and e_{s,t}^{∗} := e_{s,t}(0)e_{s,t}(1). We characterize the boundedness of

C_{s,t}(n) := gcd(F_{n} + s, F_{n+1} + t).

Theorem 8. Let s, t ∈ ℤ and n ∈ ℕ_{0}. The following assertions on C_{s,t}(n) are equivalent: a) n ↦ C_{s,t}(n) is unbounded on ℕ_{0};

b) (s, t) ∈ R := {±(F_{j−1}, F_{j}), ±(F_{j}, −F_{j−1}) : j ∈ ℕ_{0}};

c) e^{∗}(s, t) = 0.

The next two theorems show the boundedness of D_{a,s}(n) and C_{s,t}(n) respectively imply periodicity. Theorem 9. Let a ∈ ℕ and s ∈ ℤ. If (a, s) ∉ S, then the function D_{a,s}(n) is simply periodic on ℕ_{0}, which means there exists a positive integer p such that D_{a,s}(n + p) = D_{a,s}(n) for all n ≥ 0. A period p ≤ c^{2} can be chosen such that

F_{p} ≡ 0 (mod c) and F_{p+1} ≡ 1 (mod c)  (1)

where c := |F_{a}^{4} − s^{4}(L_{a} − 1 + (−1)^{a+1})^{2}|. Theorem 10. If (s, t) ∉ R, then the function C_{s,t}(n) is simply periodic on ℕ_{0}. A period p ≤ c^{2} can be chosen by (1), where c := |(s^{2} + st − t^{2})^{2} − 1|.

A theorem on three shifted Fibonacci numbers is given in the following last main result. Theorem 11. Let a ∈ ℕ and s ∈ ℤ and set

E_{a,s}(n) := gcd(F_{n} + s, F_{n+a} + s, F_{n+2a} + s),

for all n ∈ ℕ_{0}. Then we have a) E_{a,s}(n) divides d where

d := \begin{cases}s(L_{a} − 1 + (−1)^{a+1}), & if s ≠ 0; \\ F_{a}, & if s = 0. \end{cases}

b) The function n ↦ E_{a,s}(n) is simply periodic.

3 Auxiliary results

In the following proofs we need some well-known facts on the sequences (F_{n})_{n≥0} and (L_{n})_{n≥0}, which we have collected in the following lemma: Lemma 12 ([6]). Let n, m ∈ ℤ. Then we have

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

b) gcd(L_{n}, L_{n+1}) = 1;

c) F_{−n} = (−1)^{n+1}F_{n};

d) L_{−n} = (−1)^{n}L_{n};

e) gcd(F_{m}, F_{n}) = F_{gcd(m,n)};

f) F_{m} | F_{n} if and only if m | n;

g) F_{2n} = F_{n}L_{n};

h) L_{n} = F_{n+1} + F_{n−1};

i) 5F_{n} = L_{n+1} + L_{n−1};

j) F_{m+n} = F_{m}L_{n} + (−1)^{n+1}F_{m−n}, m ≥ n;

k) F_{m+n} = F_{n}L_{m} + (−1)^{n}F_{m−n}, m ≥ n;

l) 5F_{n} = L_{m}L_{n−m+1} + L_{m−1}L_{n−m};

m) F_{m+n} = F_{m}F_{n+1} + F_{m−1}F_{n};

n) F_{m+2n}F_{m} − F_{m+n}^{2} = (−1)^{m+1}F_{n}^{2};

o) L_{4n+2} − 2 = L_{2n+1}^{2};

p) 5F_{2n}^{2} = L_{4n} − 2.

4 Proofs of Theorems 1 and 2 and Corollaries 3–6

Proof of Theorem 1. Using the property gcd(u, v) = gcd(u, v − u), observe that

D = gcd(F_{2an+2b+i} + (−1)^{b}, F_{2an+2b+2j}).

By Lemma 12.g, we have

F_{2an+2b+2j} = F_{an+b+j}L_{an+b+j}.

If an + j is odd, then by Lemma 12.k, it follows that

F_{2an+2b+i} + (−1)^{b} = F_{an+b+j}L_{an+b+j+1}.

This implies

D = F_{an+b+j} gcd(L_{an+b+j+1}, L_{an+b+j}),

and hence by Lemma 12.b, we have D = F_{an+b+j}.

If an + j is even, then

F_{2an+2b+i} + (−1)^{b} = F_{an+b+j+1}L_{an+b+j}.

and

D = L_{an+b+j} gcd(F_{an+b+j+1}, F_{an+b+j}) = L_{an+b+j}.

Proof of Theorem 2. Using Lemma 12.m, we deduce that

F_{2an+2b+i+k} = F_{k}F_{2an+2b+i+1} + F_{k−1}F_{2an+2b+i}.

Thus, by gcd(u, v) = gcd(u, v − F_{k−1}u), we have

D = gcd(F_{2an+2b+i} + (−1)^{b}, F_{k}F_{2an+2b+i+1}).

Using Lemma 12.g, we deduce that

F_{2an+2b+i+1} = F_{an+b+j}L_{an+b+j}.

Now we consider two cases: an + j is odd or an + j is even.

If an + j is odd, then by Lemma 12.j, we have

F_{2an+2b+i} + (−1)^{b} = F_{an+b+j}L_{an+b+j−1} + (−1)^{an+b+j} + (−1)^{b} = F_{an+b+j}L_{an+b+j−1}. Thus, combining with Lemma 12.b, we have

D = F_{an+b+j} gcd(L_{an+b+j−1}, F_{k}L_{an+b+j}) = F_{an+b+j} gcd(L_{an+b+j−1}, F_{k}). If an + j is even, then by Lemma 12.k, we deduce that F_{2an+2b+i} + (−1)^{b} = L_{an+b+j}F_{an+b+j−1} + (−1)^{an+b+j−1} + (−1)^{b} = L_{an+b+j}F_{an+b+j−1}.

Thus, combining with Lemma 12.a, we have that D = L_{an+b+j} gcd(F_{an+b+j−1}, F_{k}F_{an+b+j}) = L_{an+b+j} gcd(F_{an+b+j−1}, F_{k}).

Proof of Corollary 3 and Corollary 4. Notice that we have

gcd(L_{an+b+j−1}, F_{1}) = gcd(F_{an+b+j−1}, F_{1}) = 1,

and

gcd(L_{an+b+j−1}, F_{2}) = gcd(F_{an+b+j−1}, F_{2}) = 1.

So we obtain Corollary 3 and Corollary 4 from Theorem 2 by setting k = 1 or k = 2. Proof of Corollary 5. We have

\begin{cases}F_{m} ≡ 0 (mod 2), & if and only if m ≡ 0 (mod 3); \\ L_{m} ≡ 0 (mod 2), & if and only if m ≡ 0 (mod 3); \end{cases}

and

gcd(F_{an+b+j−1}, F_{3}) = \begin{cases}2, & if an + b + j ≡ 1 (mod 3); \\ 1, & otherwise; \end{cases}

and

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

Therefore, we conclude that Corollary 5 is the case k = 3 in Theorem 2. Example 13. If a = 3, b = 0, i = 3 and n is even, we get

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

Proof of Corollary 6. The proof is similar to the proof of Corollary 5 by using the fact that F_{4} = 3 and

\begin{cases}F_{m} ≡ 0 (mod 3) & if and only if m ≡ 0 (mod 4); \\ L_{m} ≡ 0 (mod 3) & if and only if m ≡ 2 (mod 4). \end{cases}

5 Proof of Theorem 7

Let D = D_{a,s}(n). We need two lemmas. Lemma 14. For all a ∈ ℕ, s ∈ ℤ, and n ∈ ℕ_{0}, we have D_{a,s}(n) divides the value F_{a}^{2} + (−1)^{n}s^{2}(L_{a} − 1 + (−1)^{a+1}).

Proof. We apply Lemma 12.n and get on the one hand

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

hence

−sF_{n+2a} − s^{2} ≡ (−1)^{n+1}F_{a}^{2} (mod D).

On the other hand, we have

F_{n+2a} = F_{n+a}L_{a} + (−1)^{a+1}F_{n}

by Lemma 12.j and

F_{n+2a} ≡ −sL_{a} + (−1)^{a}s (mod D).

Together, this gives us

s^{2}(L_{a} + (−1)^{a+1} − 1) ≡ (−1)^{n+1}F_{a}^{2} (mod D).

Lemma 15. Let (a, s) ∈ ℤ^{2} and a > 0. Then

1) F_{a}^{2} + s^{2}(L_{a} − 1 + (−1)^{a+1}) = 0 is impossible.

2) F_{a}^{2} − s^{2}(L_{a} − 1 + (−1)^{a+1}) = 0 implies (a, s) ∈ S.

Proof. Let (a, s) be a solution of the equation F_{a}^{2} + s^{2}(L_{a} − 1 + (−1)^{a+1}) = 0. If a = 1, then 1 + s^{2} = 0, a contradiction. If a > 1, then L_{a} − 1 + (−1)^{a+1} ≥ L_{a} − 2 > 0; hence F_{a} = 0 and s = 0, also a contradiction.

Let (a, s) be a solution of the equation F_{a}^{2} − s^{2}(L_{a} − 1 + (−1)^{a+1}) = 0. Then we have

F_{a}^{2} = s^{2}(L_{a} − 1 + (−1)^{a+1}).

Now we consider two cases for a.

First case: a is odd, that is F_{a}^{2} = s^{2}L_{a}. If a = 1, then 1 = s^{2} and (a, s) = (1, ±1) ∈ S. We can assume a ≥ 3. Let p a prime divisor of L_{a}, hence of F_{a}. Since

gcd(F_{a}, L_{a}) = gcd(F_{a}, L_{a} − F_{a}) = gcd(F_{a}, 2F_{a−1}) ∈ {1, 2},

we get p = 2, L_{a} = 2^{2α}, F_{a} = |s| 2^{α}, α ≥ 1. Since a is odd and F_{a} is even, we see from Table 1 that a ≡ 3 (mod 6) and F_{a} ≢ 0 (mod 4); hence α = 1, L_{a} = 4 and (a, s) = (3, ±1) ∈ S.

\begin{matrix}a & 3 & 5 & 7 & 9 & 11 \\ F_{a} & 2 & 5 & 13 & 34 & 89 \\ F_{a} mod 2 & 0 & 1 & 1 & 0 & 1 \\ F_{a} mod 4 & 2 & 1 & 3 & 2 & 1 \end{matrix}

Table 1: Residue Second case: a is even, that is F_{a}^{2} = s^{2}(L_{a} − 2). If a ≡ 0 (mod 4), say a = 4k, k > 0, then F_{a}^{2} = s^{2}5F_{2k}^{2} by Lemma 12.p and 5 is square, a contradiction. Now we can assume a ≡ 2 (mod 4), say a = 4k + 2, k ≥ 0. Then L_{a} − 2 = L_{2k+1}^{2} by Lemma 12.o and

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

by Lemma 12.g. This implies (a, s) = (4k + 2, ±F_{2k+1}) ∈ S. The proof is completed.

Proof of Theorem 7. First, let (a, s) ∈ ℕ × ℤ, (a, s) ∉ S. By Lemma 15, we have

F_{a}^{2} + (−1)^{n}s^{2}(L_{a} − 1 + (−1)^{a+1}) ≠ 0 for n ∈ {0, 1}

and by Lemma 14, the function D_{a,s}(n) is bounded.

On the other hand, if (a, s) ∈ S, then we see that D_{a,s} is unbounded, since for n ∈ ℕ by Theorem 1, we have

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

and by Corollary 5, we have

D_{3,1}(4n + 1) = λF_{2n+1} ≥ F_{2n+1} and D_{3,−1}(4n + 1) = λL_{2n+1} ≥ L_{2n+1}.

If n = 4m + 2k + 3 then

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

= gcd(F_{4m+2k+3} + F_{2k+1}, F_{4m+6k+5} − F_{4m+2k+3})

= gcd(F_{2m+1}L_{2m+2k+2}, F_{4m+4k+4}L_{2k+1})

( by Lemma 12.j and 12.k) = L_{2m+2k+2} gcd(F_{2m+1}, F_{2m+2k+2}L_{2k+1}) (by Lemma 12.g) .

Then L_{2m+2k+2} divides D_{4k+2,F_{2k+1}}(n). Hence, D_{4k+2,F_{2k+1}}(n) is unbounded.

Same argumentation, we obtain the unboundedness of D_{4k+2,−F_{2k+1}}(n). So all (a, s) ∈ S generate unbounded functions D_{a,s}(n).

Remark 16. The same arguments as in the proof of Theorem 7 give the following result on Lucas numbers.

Theorem 17. Let a ∈ ℕ, s ∈ ℤ. Then the conditions a) and b) are equivalent:

a) The function D_{a,s}^{∗}(n) = gcd(L_{n} + s, L_{n+a} + s) is unbounded on ℕ_{0};

b) a = 4b, s = ±L_{2b} for b ∈ ℕ.

6 Proof of Theorem 8

We need the following lemma. Lemma 18. Let s, t ∈ ℤ, n ∈ ℕ_{0}. Then

1) C = C_{s,t}(n) divides e_{s,t}(n);

2) C divides e_{s,t}^{∗}. Proof. Let n ∈ ℕ_{0} and define M(n) and Q as follows:

M(n) := (\begin{matrix}F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n} \end{matrix}) and Q := (\begin{matrix}1 & 1 \\ 1 & 0 \end{matrix}) .

Then M(n + 1) = QM(n) and M(n) = Q^{n}M(0). Taking determinants gives

(−1)^{n+1} = det M(n) = F_{n+2}F_{n} − F_{n+1}^{2}
= (F_{n+1} + F_{n})F_{n} − F_{n+1}^{2}
≡ (t + s)s − t^{2} (mod C).

Hence e_{s,t}(n) ≡ 0 (mod C) and e_{s,t}^{∗} ≡ 0 (mod C). Corollary 19. If s, t ∈ ℤ and e_{s,t}^{∗} ≠ 0, then the function n ↦ C_{s,t}(n) is bounded on ℕ. Proof. Now, we give a proof of Theorem 8 by the circle (a) ⇒ (c) ⇒ (b) ⇒ (a).

(a) ⇒ (c) by Corollary 19.

(c) ⇒ (b) We have

±1 = s^{2} + st − t^{2}

= (s + \frac{t}{2})^{2} − 5(\frac{t}{2})^{2}

= \frac{2s + t + t\sqrt{5}}{2} · \frac{2s + t − t\sqrt{5}}{2}.

These fractions are units in the quadratic field ℚ(\sqrt{5}); hence by [4, Theorem 257]

\frac{2s + t + t\sqrt{5}}{2} = ±α^{j}, where α := \frac{1 + \sqrt{5}}{2}, j ∈ ℤ.

Since α^{j} = \frac{L_{j} + F_{j}\sqrt{5}}{2}, we get t = ±F_{j} and

s = ±\frac{L_{j} − t}{2} = ±\frac{F_{j+1} + F_{j−1} − F_{j}}{2} = ±F_{j−1}, j ∈ ℤ.

Since F_{−j} = (−1)^{j+1}F_{j}, we get (s, t) ∈ R.

(b) ⇒ (a) Let i ≥ 2. By Jacobson [5] we have

F_{2^{i}3} ≡ 0 (mod 2^{i+1}); F_{2^{i}3−1} ≡ 1 (mod 2^{i+1}).

Hence, by Lemma 12.m

\begin{aligned}F_{2^{i}3+j} & = F_{2^{i}3}F_{j+1} + F_{2^{i}3−1}F_{j} \\ & ≡ F_{j} (mod 2^{i+1}) \end{aligned}

and F_{2^{i}3−j} ≡ F_{−j} ≡ (−1)^{j+1}F_{j} (mod 2^{i+1}). We see that the function n ↦ C_{s,t}(n) is unbounded on ℕ if (s, t) = −(F_{j}, F_{j+1}) and (s, t) = (−1)^{j}(F_{j}, −F_{j−1}), j ∈ ℕ_{0}. If (s, t) = (F_{j}, F_{j−1}), j ∈ ℕ_{0}, then

C_{s,t}(n) = gcd(F_{n} + F_{j}, F_{n+1} + F_{j+1})
= gcd(F_{n−1} + F_{j−1}, F_{n} + F_{j})
= gcd(F_{n−2} + F_{j−2}, F_{n−1} + F_{j−1})
= gcd(F_{n−j}, F_{n−j+1} + 1).

Since F_{2m} = F_{m}L_{m} and F_{2m+1} + 1 = F_{m}L_{m+1} if m is odd, we have for m is odd

C_{s,t}(2m + j) = gcd(F_{2m}, F_{2m+1} + 1) = F_{m} gcd(L_{m}, L_{m+1}) = F_{m},

so C_{s,t}(n) is unbounded. The last case (s, t) = (−1)^{j+1}(F_{j}, −F_{j−1}) = (F_{−j}, F_{−(j−1)}), j ∈ ℕ_{0} is proved in a similar way. Thus, the proof of Theorem 8 is completed. Remark 20. It is an open problem to characterize the general function

n ↦ gcd(F_{n} + s, F_{n+a} + t), a ∈ ℕ, s, t ∈ ℤ.

7 Proof of periodicity (Theorem 9 and 10)

The proof of Theorem 9 and Theorem 10 are completely analogous to the one in [8] with a = 1. Set c_{n} := F_{a}^{2} + (−1)^{n}s^{2}(L_{a} − 1 + (−1)^{a+1}) and c := |c_{0}c_{1}| , then c ≠ 0 and D_{a,s}(n) divides c for (a, s) ∉ S. Then there is an integer 1 ≤ p ≤ c^{2} such that F_{n+p} ≡ F_{n} (mod c) for all n ∈ ℕ. This p is a period of D_{a,s}(n). Same argumentation, we obtain the proof of Theorem 10.

A period p that we get by this method is not necessarily the smallest positive one. For example, if a = 1, s = 2 in Theorem 9 or t = s = 2 in Theorem 10, then we have c = 15 and F_{n+80} ≡ F_{n} (mod 15). Hence p = 80, but 40 is also a period of D_{1,2}(n) and it is the smallest one [1].

One cannot always get the smallest period by this method. For example, if a = 4, s = −2 in Theorem 9; hence c = 319. Then 10 is the smallest period, but F_{10} ≢ F_{0} (mod 319). If s = 7, t = 2 in Theorem 10, then we have c = 3480 and p = 840, but 120 is the smallest period and F_{120} ≢ F_{0} (mod 3480).

8 Gcd of three shifted Fibonacci numbers

Proof of Theorem 11. Fix a > 0, n ≥ 0 and s ∈ ℤ, and set E(n) = E_{a,s}(n). Then by Lemma 12.j, we have

F_{n+2a} = F_{n+a}L_{a} + (−1)^{a+1}F_{n},

which gives us that

−s ≡ −sL_{a} − (−1)^{a+1}s (mod E(n)).

So E(n) divides s(L_{a} − 1 + (−1)^{a+1}). If s = 0, then by Lemma 12.e we have

E(n) = gcd(F_{n}, F_{n+a}, F_{n+2a}) = F_{gcd(n,n+a,n+2a)} = F_{gcd(n,a)} = gcd(F_{n}, F_{a}).

Hence, E(n) divides F_{a}. Let

d := \begin{cases}s(L_{a} − 1 + (−1)^{a+1}), & if s ≠ 0; \\ F_{a}, & if s = 0. \end{cases}

Then d ≠ 0, and we deduce that E(n) divides d. In particular, the function E(n) is bounded. As in the proof of Theorem 9, we conclude that this function is simply periodic.

Remark 21. If s = 0, then E(a) = gcd(F_{a}, F_{2a}, F_{3a}) = F_{a} so arbitrarily large values are possible.

9 Acknowledgments

The authors would like to thank the referee and the editor-in-chief for many useful comments and suggestions. The third author would like to thank Hanoi National University of Education for the support during his work, No. SPHN 21-03 TT.

References

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

[2] K.-W. Chen and Y.-R. Pan, Greatest common divisors of shifted Horadam sequences, J. Integer Sequences 23 (2020), Article 20.5.8.

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

[4] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1954.

[5] E. Jacobson, Distribution of the Fibonacci numbers mod 2^{k}, Fibonacci Quart. 30 (1992), 211–215.

[6] T. Koshy, Fibonacci and Lucas Numbers With Applications, A Wiley—Interscience Series of Text, 2001.

[7] A. Rahn and M. Kreh, Greatest common divisors of shifted Fibonacci sequence revisited, J. Integer Sequences 21 (2018), Article 18.6.7.

[8] 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.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B37. Keywords: Fibonacci number, recurrence.

(Concerned with sequence \underline{A000045} and \underline{A000204}.)

Received June 15 2020; revised versions received October 30 2020; January 3 2021; July 4 2021; July 22 2021; November 25 2021; January 21 2022. Published in Journal of Integer Sequences, January 26 2022.

Return to Journal of Integer Sequences home page.