Generalization of Greatest Common Divisor of Shifted Fibonacci Numbers

Tran Quang Do and Luu Ba Thang^{1} Department of Mathematics and Informatics Hanoi National University of Education 136 Xuan Thuy Cau Giay Hanoi Vietnam

                     quangdo1501@gmail.com
                      thanglb@hnue.edu.vn

Abstract Let F_{n} denote the n’th Fibonacci number and let k be a positive integer. We find necessary and sufficient conditions on s and t so that the function n ↦ gcd(F_{n} + s, F_{n+k} + t) is unbounded.

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.

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}. 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 also 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). In 2022, Hieu, Spilker, and Thang [5] investigated the necessary and sufficient conditions on k ∈ ℕ, s, t ∈ ℤ, so that the function gcd(F_{n} + s, F_{n+k} + s) and the function gcd(F_{n} + s, F_{n+1} + t) are unbounded. They proposed the open problem to characterize the function gcd(F_{n} + s, F_{n+k} + t) for k ∈ ℕ, s, t ∈ ℤ. Let ℕ_{0} denote the set of non-negative integers. In this article, given a positive integer k, we investigate necessary and sufficient conditions on s, t ∈ ℤ (depend on k), so that the function

1Corresponding author.

\begin{matrix}B_{s,t}^{k} : ℕ_{0} & → ℕ \\ n & ↦ gcd(F_{n} + s, F_{n+k} + t) \end{matrix}

is bounded (Theorem 1). If B_{s,t}^{k} is bounded, it is periodic (Theorem 2). In more detail, we obtain the following results:

Theorem 1. Let s, t ∈ ℤ and n ∈ ℕ_{0}. The following assertions on B_{s,t}^{k}(n) are equivalent:

1. n ↦ B_{s,t}^{k}(n) is unbounded on ℕ_{0};

2. (s, t) ∈ R := {±(F_{j}, F_{j+k}) : j ∈ ℤ};

3. e_{s,t}^{k∗} = 0,

where e_{s,t}^{k}(n) := t^{2} − L_{k}st + (−1)^{k}s^{2} − (−1)^{n}F_{k}^{2} and e_{s,t}^{k∗} := e_{s,t}^{k}(0)e_{s,t}^{k}(1).

Theorem 2. If (s, t) ∉ R, then the function B_{s,t}^{k}(n) is simply periodic on ℕ_{0}, which means there exists a positive integer p such that B_{s,t}^{k}(n + p) = B_{s,t}^{k}(n) for all n ≥ 0. A period p ≤ c^{2} can be chosen where c := |e_{s,t}^{k∗}| such that

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

2 Auxiliary results

The following lemma contains some well-known facts on (F_{n})_{n≥0} and (L_{n})_{n≥0}, which we have used. Notice that F_{n} and L_{n} can be extended to integer indices by the recursion.

Lemma 3 ([6]). Let k ∈ ℕ, n, m ∈ ℤ. Then we have

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

(b) F_{n+2k} = L_{k}F_{n+k} − (−1)^{k}F_{n}; (c) F_{\frac{m−n}{2}} divides F_{m} + F_{n} if \frac{m − n}{2} is an odd integer;

(d) F_{\frac{m−n}{2}} divides F_{m} − F_{n} if \frac{m − n}{2} is an even integer;

(e) \frac{L_{k}^{2}}{4} − (−1)^{k} = \frac{5}{4}F_{k}^{2};

(f) 2F_{n+k} = L_{k}F_{n} + L_{n}F_{k}.

3 Proof of Theorem 1 and 2

Set B := B_{s,t}^{k}(n). We need the following lemma. Lemma 4. Let s, t ∈ ℤ, n ∈ ℕ_{0}. Then

(a) B divides e_{s,t}^{k}(n);

(b) B divides e_{s,t}^{k∗}. Proof. By using Lemma 3 (a) we have:

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

By using Lemma 3 (b) we have:

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

Since B_{s,t}^{k}(n) = gcd(F_{n} + s, F_{n+k} + t), by applying

F_{n+k} ≡ −t (mod B) and F_{n} ≡ −s (mod B),

we deduce that

t^{2} − L_{k}st + (−1)^{k}s^{2} ≡ (−1)^{n}F_{k}^{2} (mod B).

Hence, e_{s,t}^{k}(n) ≡ 0 (mod B) and e_{s,t}^{k∗} ≡ 0 (mod B).

Corollary 5. If s, t ∈ ℤ and e_{s,t}^{k∗} ≠ 0, then the function n ↦ B_{s,t}^{k}(n) is bounded on ℕ_{0}. Proof of Theorem 1. Now, we give a proof of Theorem 1 by the implications (1) ⇒ (3) ⇒ (2) ⇒ (1).

(1) ⇒ (3): by Corollary 5.

(3) ⇒ (2): We have

t^{2} − L_{k}st + (−1)^{k}s^{2} = (t − \frac{L_{k}}{2} s)^{2} + ((−1)^{k} − \frac{L_{k}^{2}}{4} ) s^{2}

= (t − \frac{L_{k}}{2} s)^{2} − \frac{5}{4}F_{k}^{2}s^{2} (by Lemma 3 (e)).

Hence

(t − \frac{L_{k}}{2} s)^{2} − \frac{5}{4}F_{k}^{2}s^{2} = ±F_{k}^{2}.  (1)

If s is even, from (1) we have F_{k} | t − \frac{L_{k}}{2} s. Hence,

\frac{t − \frac{L_{k}}{2} s}{F_{k}} − \frac{\sqrt{5}}{2}s = (\frac{t − \frac{L_{k}}{2} s}{F_{k}} + \frac{s}{2}) − s\frac{\sqrt{5} + 1}{2}

is integer in the quadratic field ℚ(\sqrt{5}).

If s is odd, from (1) we have \frac{t − \frac{L_{k}}{2} s}{F_{k}} = \frac{c}{2} where c is odd. Hence,

\frac{t − \frac{L_{k}}{2}}{F_{k}} − \frac{\sqrt{5}}{2}s = \frac{c − s}{2} + s\frac{\sqrt{5} + 1}{2}

is integer in the quadratic field ℚ(\sqrt{5}). By dividing F_{k}^{2} of two sides in (1), we have

\begin{aligned}±1 & = (\frac{t − \frac{L_{k}}{2} s}{F_{k}})^{2} − \frac{5}{4}s^{2} \\ & = (\frac{t − \frac{L_{k}}{2} s}{F_{k}} − \frac{\sqrt{5}}{2}s) (\frac{t − \frac{L_{k}}{2} s}{F_{k}} + \frac{\sqrt{5}}{2}s) . \end{aligned}

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

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

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

t = ±\frac{F_{j}L_{k} + F_{k}L_{j}}{2} = ±F_{j+k} (by Lemma 3.f).

This implies (s, t) ∈ R.

(2) ⇒ (1): If (s, t) = (F_{j}, F_{j+k}), we choose n such that \frac{n − j}{2} is an odd integer. Then

F_{\frac{n−j}{2}} | F_{n} + F_{j} and F_{\frac{n−j}{2}} | F_{n+k} + F_{j+k} (by Lemma 3 (c)).

If (s, t) = −(F_{j}, F_{j+k}), we choose n such that \frac{n − j}{2} is an even integer, then

F_{\frac{n−j}{2}} | F_{n+k} − F_{j+k} and F_{\frac{n−j}{2}} | F_{n} − F_{j} (by Lemma 3 (d) ).

Hence, B_{s,t}^{k}(n) is unbounded. The proof of Theorem 1 is completed.

Proof of Theorem 2. The proof of Theorem 2 is completely analogous to the one in [8] with k = 1 and s = t. Set e_{s,t}^{k}(n) := t^{2} − L_{k}st + (−1)^{k}s^{2} − (−1)^{n}F_{k}^{2} and c := |e_{s,t}^{k}(0)e_{s,t}^{k}(1)|. Then c ≠ 0 and B_{s,t}^{k}(n) divides c for (s, t) ∉ R. Then there is a positive integer p ≤ c^{2} such that

F_{n} ≡ F_{n+p} (mod c) for all n ∈ ℕ.

We have B_{s,t}^{k}(n) = gcd(F_{n} + s, F_{n+k} + t) | c and F_{n+p} − F_{n}, F_{n+k+p} − F_{n+k} are divisible by c, then

B_{s,t}^{k}(n) | ((F_{n+p} − F_{n}) + (F_{n} + s)) and B_{s,t}^{k}(n) | ((F_{n+k+p} − F_{n+k}) + (F_{n+k} + t)).

Thus,

B_{s,t}^{k}(n) | (F_{n+p} + s) and B_{s,t}^{k}(n) | (F_{n+k+p} + t).

This implies B_{s,t}^{k}(n) | gcd(F_{n+k} + s, F_{n+p+k} + t). Hence, B_{s,t}^{k}(n) | B_{s,t}^{k}(n + p). Similarly, we have also B_{s,t}^{k}(n + p) | B_{s,t}^{k}(n). Therefore, B_{s,t}^{k}(n + p) = B_{s,t}^{k}(n).

This p is a period of B_{s,t}^{k}(n). However, a period p that we get by this method is not necessarily the smallest positive one. For example, if we choose s = t = 2 and k = 1 then we have c = 15 and F_{n+80} ≡ F_{n} (mod 15). Hence p = 80 but 40 is also a period of B_{1,2}^{1}(n) and it is the smallest one.

Remark 6. If s = t, we obtain Theorem 7 in [5]. If k = 1, we obtain Theorem 8 in [5].

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

Theorem 8. Let k ∈ ℕ, s, t ∈ ℤ. The following assertions on B_{s,t}^{k∗}(n) are equivalent:

1. The function B_{s,t}^{k∗}(n) := gcd(L_{n} + s, L_{n+k} + t) is unbounded on ℕ_{0};

2. (s, t) ∈ S := {±(L_{j}, L_{j+k}) : j ∈ ℤ};

3. t^{2} − L_{k}st + (−1)^{k}s^{2} = ±5F_{k}^{2}.

4 Acknowledgment

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

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] L. D. Hieu, J. Spilker, and L. B. Thang, The greatest common divisor of shifted Fibonacci numbers, J. Integer Sequences 25 (2022), Article 22.1.7.

[6] T. Koshy, Fibonacci and Lucas Numbers With Applications, Wiley, 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, Lucas number, recurrence, greatest common divisor.

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

Received October 18 2022; revised versions received November 8 2022; November 11 2022. Published in Journal of Integer Sequences, November 13 2022.

Return to Journal of Integer Sequences home page.