On Equivalence Classes of Generalized Fibonacci Sequences

Miho Aoki and Yuho Sakai Department of Mathematics Shimane University Matsue, Shimane 690-8504 Japan

               aoki@riko.shimane-u.ac.jp
             s149410@matsu.shimane-u.ac.jp

Abstract

We consider a generalized Fibonacci sequence (G_{n}) by G_{1}, G_{2} ∈ ℤ and G_{n} = G_{n−1} + G_{n−2} for any integer n. Let p be a prime number and let d(p) be the smallest positive integer n which satisfies p | F_{n}. In this article, we introduce equivalence relations for the set of generalized Fibonacci sequences. One of the equivalence relations is defined as follows. We write (G_{n}) ∼^{∗} (G′_{n}) if there exist integers m and n satisfying G_{m+1}G′_{n} ≡ G′_{n+1}G_{m} (mod p). We prove the following: if p ≡ ±2 (mod 5), then the number of equivalence classes \overline{(G_{n})} satisfying p ∤ G_{n} for any integer n is (p+1)/d(p)−1. If p ≡ ±1 (mod 5), then the number is (p − 1)/d(p) + 1. Our results are refinements of a theorem given by Kôzaki and Nakahara in 1999. They proved that there exists a generalized Fibonacci sequence (G_{n}) such that p ∤ G_{n} for any n ∈ ℤ if and only if one of the following three conditions holds: (1) p = 5; (2) p ≡ ±1 (mod 5); (3) p ≡ ±2 (mod 5) and d(p) < p + 1.

1 Introduction and main results

We consider a generalized Fibonacci sequence (G_{n}) defined by

G_{1}, G_{2} ∈ ℤ, G_{n} = G_{n−1} + G_{n−2} (n ∈ ℤ).

If G_{1} = 1 and G_{2} = 1, then it is the Fibonacci sequence (F_{n}), and if G_{1} = 1 and G_{2} = 3, then it is the Lucas sequence (L_{n}). It is well-known that such generalized Fibonacci sequences are periodic modulo m for any natural numbers m. For example, the sequence (F_{n} mod 3) is … 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, … (the period is 8). There are many interesting results concerning the generalized Fibonacci sequences. We recommend two books by Koshy [2, §7] and Nakamura [4] as references.

We fix a prime number p, and define two relations ∼ and ∼^{∗} for the set of generalized Fibonacci sequences. The first relation ∼ is defined in our previous paper [1].

Definition 1. Let (G_{n}) and (G′_{n}) be generalized Fibonacci sequences. We write (G_{n}) ∼ (G′_{n}) if the congruence G_{2}G′_{1} ≡ G′_{2}G_{1} (mod p) holds.

Definition 2. Let (G_{n}) and (G′_{n}) be generalized Fibonacci sequences. We write (G_{n}) ∼^{∗} (G′_{n}) if there are some integers m and n satisfying G_{m+1}G′_{n} ≡ G′_{n+1}G_{m} (mod p).

By the definitions, the next lemma follows.

Lemma 3. If (G_{n}) ∼ (G′_{n}), then we have (G_{n}) ∼^{∗} (G′_{n}).

Note that if (G_{n}) satisfies p | G_{1} and p | G_{2}, then we have (G_{n}) ∼ (G′_{n}) and (G_{n}) ∼^{∗} (G′_{n}) for any generalized Fibonacci sequences (G′_{n}). We can show by the definition that the first relation ∼ is an equivalence relation for the set {(G_{n})| p ∤ G_{1} or p ∤ G_{2}}.

We will show in §2 that the second relation ∼^{∗} is also an equivalence relation. Since the relations ∼ and ∼^{∗} are equivalence relations, we can consider the quotient sets using these relations. We put

X_{p} := \{(G_{n}) | p ∤ G_{1} or p ∤ G_{2}\}/ ∼,  Y_{p} := \{\overline{(G_{n})} ∈ X_{p} | p ∤ G_{n} for any n ∈ ℤ\}.
X_{p}^{∗} := \{(G_{n}) | p ∤ G_{1} or p ∤ G_{2}\}/ ∼^{∗}, Y_{p}^{∗} := \{\overline{(G_{n})} ∈ X_{p}^{∗} | p ∤ G_{n} for any n ∈ ℤ\}.

The sets Y_{p} and Y_{p}^{∗} are well-defined by [1, Lemma 2] and Lemma 10 in §2. We considered the set X′_{p} = \{(G_{n}) | p ∤ G_{1} and p ∤ G_{2}\}/ ∼ and Y′_{p} = \{\overline{(G_{n})} ∈ X′_{p} | p ∤ G_{n} for any n ∈ ℤ\} instead of X_{p} and Y_{p} [1]. Note that the cardinality of Y_{p} and Y′_{p} are equal. Let p be a prime number and let d(p) be the smallest positive integer n for which p | F_{n}. We proved the following theorem in a previous paper [1].

Theorem 4 ([1, Theorem 1 (2)]).

|Y_{p}| = p + 1 − d(p)

In this article, we will reduce the number of equivalence classes by using the new relation ∼^{∗} instead of ∼, and will prove the following theorem in §3.

Theorem 5. (1) If p ≡ ±2 (mod 5), then we have

|Y_{p}^{∗}| = \frac{|Y_{p}|}{d(p)} = \frac{p + 1}{d(p)} − 1.

(2) If p ≡ ±1 (mod 5), then we have

|Y_{p}^{∗}| = 2 + \frac{|Y_{p}| − 2}{d(p)} = \frac{p − 1}{d(p)} + 1.

(3) If p = 5, then we have |Y_{p}^{∗}| = |Y_{p}| = 1.

In §4, we will show that our results imply the following result given by Kôzaki and Nakahara in 1999. An integer m is called the type of a non-divisor when there exists a generalized Fibonacci sequence (G_{n}) such that m ∤ G_{n} for any n ∈ ℤ. For a prime number p, we denote the period of (F_{n} mod p) by k(p). Theorem 6 ([3, Kôzaki and Nakahara]). A prime number p is the type of non-divisor if and only if one of the following three conditions holds.

(1) p = 5.

(2) p ≡ 1, 9, 11, 13, 17, 19 (mod 20).

(3) p ≡ 3, 7 (mod 20) and k(p) < 2(p + 1).

In §5, we will give some examples of the cardinalities of the set Y_{p} and Y_{p}^{∗}.

2 Equivalence relations

In this section, we will give some lemmas on the relation ∼^{∗}. The following lemma follows from the recurrence relation G_{n} = G_{n−1} + G_{n−2}. Lemma 7. Let (G_{n}) be a generalized Fibonacci sequence that satisfies p ∤ G_{1} or p ∤ G_{2}. If p | G_{n}, then we have p ∤ G_{n−1} and p ∤ G_{n+1}. Lemma 8. Let (G_{n}) and (G′_{n}) be generalized Fibonacci sequences. If G_{m+1}G′_{n} ≡ G′_{n+1}G_{m} (mod p), then we have G_{m+2}G′_{n+1} ≡ G′_{n+2}G_{m+1} (mod p). Proof.

G_{m+2}G′_{n+1} = (G_{m+1} + G_{m})G′_{n+1}
= G_{m+1}G′_{n+1} + G_{m}G′_{n+1}
≡ G_{m+1}G′_{n+1} + G_{m+1}G′_{n} (by the assumption)
= G_{m+1}(G′_{n+1} + G′_{n})
= G_{m+1}G′_{n+2}.

For any integer G that is not divisible by p, we denote an inverse element modulo p by G^{−1} (∈ ℤ) (i.e., GG^{−1} ≡ 1 (mod p)).

Lemma 9. The relation ∼^{∗} is an equivalence relation for the set {(G_{n}) | p ∤ G_{1} or p ∤ G_{2}}.

Proof. Since this relation is reflexive and symmetric, we will prove the transitivity: if (G_{n}) ∼^{∗} (G′_{n}) and (G′_{n}) ∼^{∗} (G′′_{n}), then (G_{n}) ∼^{∗} (G′′_{n}). By the assumption, there exist integers m, n, k and ℓ satisfying

G_{m+1}G′_{n} ≡ G′_{n+1}G_{m} (mod p) and G′_{k+1}G′′_{ℓ} ≡ G′′_{ℓ+1}G′_{k} (mod p).

Put t = max(n, k). Using Lemma 8, we get integers m and ℓ satisfying

G_{m+1}G′_{t} ≡ G′_{t+1}G_{m} (mod p) and G′_{t+1}G′′_{ℓ} ≡ G′′_{ℓ+1}G′_{t} (mod p).  (1)

If we assume p | G′_{t}, then we get p ∤ G′_{t+1} using Lemma 7. From (1), we get p | G_{m} and p | G′′_{ℓ}. Therefore we have (G_{n}) ∼^{∗} (G′′_{n}) since G_{m+1}G′′_{ℓ} ≡ 0 ≡ G′′_{ℓ+1}G_{m} (mod p). If we assume p | G′_{t+1}, then we get (G_{n}) ∼^{∗} (G′′_{n}) by the same argument. Next, we assume p ∤ G′_{t} and p ∤ G′_{t+1}. Then we get p ∤ G_{m} and p ∤ G′′_{ℓ} from (1). Hence we get G_{m+1}G_{m}^{−1} ≡ G′_{t+1}G′_{t}^{−1} ≡ G′′_{ℓ+1}G′′_{ℓ}^{−1} (mod p), and hence G_{m+1}G′′_{ℓ} ≡ G′′_{ℓ+1}G_{m} (mod p). This congruence implies (G_{n}) ∼^{∗} (G′′_{n}).

Lemma 10. Assume (G_{n}), (G′_{n}) ∈ {(G_{n}) | p ∤ G_{1} or p ∤ G_{2}}. If (G_{n}) ∼^{∗} (G′_{n}) and p ∤ G_{n} for any n ∈ ℤ. Then we have p ∤ G′_{n} for any n ∈ ℤ.

Proof. We can assume that there exist integers m, n satisfying G_{m+1}G′_{n} ≡ G′_{n+1}G_{m} (mod p). We assume that there exists an integer ℓ such that p | G′_{ℓ}. Due to the periodicity of (G′_{n} mod p), we can assume ℓ ≥ n. Using Lemma 8, there exists an integer k such that G_{k+1}G′_{ℓ} ≡ G′_{ℓ+1}G_{k} (mod p). Since p divides G′_{ℓ} and does not divide G′_{ℓ+1}, we get p | G_{k}. This contradicts the assumption.

Lemma 11. Let (G_{n}) be a generalized Fibonacci sequence. Then there exists an integer n which satisfies p|G_{n} if and only if (G_{n}) ∼^{∗} (F_{n}).

Proof. We first assume that there is an integer n that satisfies p | G_{n}. We have (G_{n}) ∼^{∗} (F_{n}) since F_{1}G_{n} ≡ 0 ≡ G_{n+1}F_{0} (mod p) (note that F_{0} = 0).

Next, we assume (G_{n}) ∼^{∗} (F_{n}). Then there must exist some integers m and n satisfying G_{m+1}F_{n} ≡ F_{n+1}G_{m} (mod p). On the other hand, since F_{0} = 0 and the periodicity of (F_{n} mod p), there exists an integer ℓ satisfying p|F_{ℓ} and ℓ ≥ n. By using Lemma 8, we get an integer k such that G_{k+1}F_{ℓ} ≡ F_{ℓ+1}G_{k} (mod p). Since p ∤ F_{ℓ+1} by Lemma 7, we have p | G_{k}.

Lemma 12.

(1) X_{p}^{∗} = Y_{p}^{∗} ∪ \{\overline{(F_{n})}\}.

(2) For any equivalence classes \overline{(G_{n})} of X_{p}^{∗}, we can choose the representative (G_{n}) satisfying p ∤ G_{1}, G_{2}.

(3) Let \overline{(G_{n})} be an equivalence class of Y_{p}^{∗}. For any sequences (G′_{n}) ∈ \overline{(G_{n})}, we have p ∤ G′_{1}, G′_{2}.

Proof. The assertion (1) follows from Lemma 11. We will prove (2). If p | G_{1} or p | G_{2}, then we have (G_{n}) ∼^{∗} (F_{n}) by Lemma 11. Therefore, we have \overline{(G_{n})} = \overline{(F_{n})} and F_{1} = F_{2} = 1. The assertion (3) follows from Lemma 10.

3 Equivalence classes

In our previous paper [1], we gave the cardinality of the set Y_{p}. In this section, using this result, we will prove the main theorem (Theorem 5 in §1) that gives the cardinality of the set Y_{p}^{∗}.

Lemma 13. Let p (≠ 2, 5) be a prime number.

(1) If p ≡ ±1 (mod 5), then X^{2} − X − 1 = 0 has different two solutions in 𝔽_{p}.

(2) If p ≡ ±2 (mod 5), then X^{2} − X − 1 = 0 does not have a solution in 𝔽_{p}.

Proof. The solutions of X^{2}−X−1 = 0 in \overline{𝔽}_{p} (the algebraic closure of 𝔽_{p}) are X = 2^{−1}(1±\sqrt{5}). By the assumption p ≠ 2, 5, these solutions are different. We get 2^{−1}(1±\sqrt{5}) ∈ 𝔽_{p} if and only

if \sqrt{5} ∈ 𝔽_{p}. Furthermore, this is equivalent to (\frac{5}{p}) = (\frac{p}{5}) = 1, that is, p ≡ ±1 (mod 5).

We next define the number d(p) for a prime number p, and the sequences (f_{n}) and (g_{n}). These are important in this article.

Definition 14. Let p be a prime number. Let d(p) denote the smallest positive integer n which satisfies F_{n} ≡ 0 (mod p).

(1) For any integer n which satisfies n ≢ 0 (mod d(p)), we define the integer f_{n} (0 ≤ f_{n} ≤ p − 1) such that f_{n} ≡ F_{n+1}F_{n}^{−1} (mod p).

(2) Let (G_{n}) be a generalized Fibonacci sequence that satisfies p ∤ G_{n} for any n ∈ ℤ. We can then define the integer g_{n} (1 ≤ g_{n} ≤ p − 1) such that g_{n} ≡ G_{n+1}G_{n}^{−1} (mod p).

We will prove some relations between (f_{n}), (g_{n}) and d(p). The following lemma was given in [1, Lemma 3].

Lemma 15 ([1, Lemma 3]). Let m and n be integers that satisfy m, n ≢ 0 (mod d(p)). We then have f_{m} = f_{n} if and only if m ≡ n (mod d(p)).

We can show the following two lemmas by induction on n and the recurrence relation. Lemma 16. For any n, m ∈ ℤ, we have G_{n} = F_{n−m}G_{m+1} + F_{n−m−1}G_{m}. Lemma 17. For any n ∈ ℤ, we have

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

For simplicity, we introduce a new notation. If a generalized Fibonacci sequence (G_{n}) satisfies G_{1} = a and G_{2} = b, then we denote it as (G_{n}) = (G(a, b)). Theorem 18. Assume that (G_{n}) = (G(a, b)) satisfies p ∤ G_{n} for any n ∈ ℤ. Furthermore, let a and b satisfy b^{2} − ab − a^{2} ≢ 0 (mod p). For any integers n and m, we have g_{n} = g_{m} if and only if n ≡ m (mod d(p)). Proof. First, by the definition of g_{n} and g_{m}, we have g_{n} = g_{m} if and only if G_{m}G_{n+1} ≡ G_{m+1}G_{n} (mod p). Since G_{n+1} = F_{n−m+1}G_{m+1} +F_{n−m}G_{m} and G_{n} = F_{n−m}G_{m+1} +F_{n−m−1}G_{m} from Lemma 16, we have g_{n} ≡ g_{m} if and only if

G_{m+1}^{2}F_{n−m} − G_{m}G_{m+1}(F_{n−m+1} − F_{n−m−1}) − G_{m}^{2}F_{n−m} ≡ 0 (mod p).  (2)

By Lemma 17, for the left side of (2), we have

G_{m+1}^{2}F_{n−m} − G_{m}G_{m+1}(F_{n−m+1} − F_{n−m−1}) − G_{m}^{2}F_{n−m}
≡ G_{m+1}^{2}F_{n−m} − G_{m}G_{m+1}F_{n−m} − G_{m}^{2}F_{n−m}
≡ (G_{m+1}^{2} − G_{m}G_{m+1} − G_{m}^{2})F_{n−m}
≡ (−1)^{m−1}(G_{2}^{2} − G_{1}G_{2} − G_{1}^{2})F_{n−m}
≡ (−1)^{m−1}(b^{2} − ab − a^{2})F_{n−m} (mod p).

By the assumption b^{2} − ab − a^{2} ≢ 0 (mod p), we conclude that g_{n} ≡ g_{m} if and only if n ≡ m (mod d(p)).

For a generalized Fibonacci sequence (G_{n}), let (g_{n}) be the sequence defined in Definition 14. Definition 19. Assume (G_{n}) = (G(a, b)) satisfies p ∤ G_{n} for any n ∈ ℤ. We define the second period of (G_{n}) by the period of (g_{n}).

Then we get the following corollary concerning the second period. Corollary 20. Assume that (G_{n}) = (G(a, b)) satisfies p ∤ G_{n} for any n ∈ ℤ.

(1) If b^{2} − ab − a^{2} ≡ 0 (mod p), then the second period of (G_{n}) is equal to 1.

(2) If b^{2} − ab − a^{2} ≢ 0 (mod p), then the second period of (G_{n}) is equal to d(p).

Proof. The assertion (2) follows from Theorem 18. We will prove (1) by showing g_{n} = g_{1} ≡ ba^{−1} (mod p) for any n ∈ ℤ. Due to the periodicity of (G_{n}) mod p, it is sufficient to consider n ∈ ℕ. We use the induction. When n = 1, the result is shown. We assume that it holds for any natural numbers less than n + 1. We then have the following congruences.

g_{n+1} ≡ G_{n+2}G_{n+1}^{−1}
≡ (G_{n+1} + G_{n})(G_{n} + G_{n−1})^{−1}
≡ (G_{n+1}G_{n}^{−1} + 1)(1 + G_{n−1}G_{n}^{−1})^{−1}
≡ (g_{n} + 1)(1 + g_{n−1}^{−1})^{−1}
≡ (ba^{−1} + 1)(1 + b^{−1}a)^{−1}

(by the assumption of the second period 1) ≡ (ba^{−1} + 1) × {b^{−1}a(ba^{−1} + 1)}^{−1}

≡ ba^{−1} ≡ g_{1} (mod p).

By the above congruences and 1 ≤ g_{1}, g_{n+1} ≤ p − 1, we have g_{n+1} = g_{1}.

Lemma 21. Assume that (G_{n}) and (G′_{n}) satisfy p ∤ G_{n}, G′_{n} for any n ∈ ℤ. Let ν be the second period of (G′_{n}). Then we have (G_{n}) ∼^{∗} (G′_{n}) if and only if there exists an integer n (1 ≤ n ≤ ν) such that g′_{n} = g_{1}(≡ G_{2}G_{1}^{−1} (mod p)).

Proof. First, we assume g′_{n} = g_{1} for an integer n (1 ≤ n ≤ ν). Then we obtain G′_{n+1}G′_{n}^{−1} ≡ G_{2}G_{1}^{−1} (mod p) and hence we get (G_{n}) ∼^{∗} (G′_{n}).

Next, we assume (G_{n}) ∼^{∗} (G′_{n}). Then there must exist integers m and n such that G_{m+1}G′_{n} ≡ G′_{n+1}G_{m} (mod p). By Lemma 8 on the forward shift index and the periodicity of (G_{n}) mod p, there exists an integer n such that G_{2}G′_{n} ≡ G′_{n+1}G_{1} (mod p). Therefore we obtain g′_{n} ≡ g_{1} (mod p). We have g_{1} = g′_{n} since 1 ≤ g_{1} ≤ p − 1 and 1 ≤ g_{n} ≤ p − 1. Furthermore, we can choose such an integer n satisfying 1 ≤ n ≤ ν because the period of (g′_{n}) is equal to ν.

Next, we will prove the main theorem in §1.

Proof of Theorem 5. We can prove (3) directly using [1, Corollary 1 (1)]. We will prove (1) and (2). Using [1, Theorem 1 (1)], we obtain

Y_{p} = X′_{p} − \{\overline{(G(1, f_{i}))} | 1 ≤ i ≤ d(p) − 2\}
X′_{p} := {(G_{n}) | p ∤ G_{1} and p ∤ G_{2}}/ ∼
= \{\overline{(G(1, b))} | 1 ≤ b ≤ p − 1\}.

(1) We consider an equivalence class \overline{(G_{n})} ((G_{n}) = (G(1, b))) of Y_{p}. Since p ≡ ±2 (mod 5), we have b^{2} − b − 1 ≢ 0 (mod p) because X^{2} − X − 1 = 0 does not have a solution in 𝔽_{p} from Lemma 13 (2). Therefore, the second period of (G_{n}) is d(p) from Corollary 20 (2), and all of the values g_{1}, g_{2}, …, g_{d(p)} are different from each other from Theorem 18 , where g_{n} is the integer such that g_{n} = G_{n+1}G_{n}^{−1} (mod p) and 1 ≤ g_{n} ≤ p − 1. From the definition of the relation ∼^{∗}, we have (G_{n}) = (G(1, b)) ∼^{∗} (G(1, g_{i})) for any i (1 ≤ i ≤ d(p)). On the other hand, for any equivalence classes \overline{(G′_{n})} ((G′_{n}) = (G(1, b′))) of Y_{p} satisfying b′ ≢ g_{1}, …, g_{d(p)} (mod p), we have (G_{n}) ≁^{∗} (G′_{n}) from Lemma 21. Then for any class \overline{(G(1, b))} in Y_{p}^{∗}, it produces distinct d(p) classes \overline{(G(1, g_{i}))} (1 ≤ i ≤ d(p))

under the equivalence relation ∼. Therefore we obtain |Y_{p}^{∗}| = \frac{|Y_{p}|}{d(p)}. The last equality:

\frac{|Y_{p}|}{d(p)} = \frac{p + 1}{d(p)} − 1 follows from [1, Theorem 1 (2)].

(2) If p ≡ ±1 (mod 5), then X^{2} − X − 1 = 0 has two different solutions α and β in 𝔽_{p} from Lemma 13 (1). We consider the generalized Fibonacci sequence (G(1, α)) = (G_{n}). Since p ∤ G_{n} for any n ∈ ℤ from α^{2} − α − 1 ≡ 0 (mod p), Lemma 7 and Corollary 20 (1), we have \overline{(G(1, α))} ∈ Y_{p}. Similarly, we have \overline{(G(1, β))} ∈ Y_{p}. Let b be an integer satisfying 1 ≤ b ≤ p−1. Since the second periods of (G(1, α)) and (G(1, β)) are 1 from Corollary 20 (1), we obtain (G(1, b)) ∼^{∗} (G(1, α)) if and only if b = α from Lemma 21. By these same arguments, we obtain the same result for (G(1, β)). On the other hand, d(p) classes \overline{(G(1, b))} of Y_{p} satisfying b ≠ α, β become the same class of Y_{p}^{∗}. We

obtain |Y_{p}^{∗}| = 2 + \frac{|Y_{p}| − 2}{d(p)}, and the last equality follows from [1, Theorem 1 (2)].

4 Comparison with a results of Kôzaki and Nakahara

In the section, we will show that our result implies a result given by Kôzaki and Nakahara in 1999.

Definition 22. An integer m is called the type of a non-divisor when there exists a generalized Fibonacci sequence (G_{n}) such that m ∤ G_{n} for any n ∈ ℤ.

Definition 23. For a prime number p, we let k(p) denote the period of (F_{n} mod p).

We can get the following corollary from [1, Theorem 1 and Corollary 1].

Corollary 24 ([1, §1]). A prime number p is the type of non-divisor if and only if one of the following three conditions holds.

(1) p = 5.

(2) p ≡ ±1 (mod 5).

(3) p ≡ ±2 (mod 5) and d(p) < p + 1.

We will prove that Theorem 6 in §1 is equivalent to Corollary 24. More specifically, we will prove (1) or (2) or (3) of Theorem 6 holds if and only if (1) or (2) or (3) of Corollary 24 holds.

Proof. First, we prove that if (1) or (2) or (3) of Theorem 6 holds, then one of (1), (2), or (3) of Corollary 24 holds.

The case in which (1) of Theorem 6 holds already.

We assume that (2) of Theorem 6 holds. If p ≡ 1, 9, 11, 19 (mod 20), then we have p ≡ ±1 (mod 5). If p ≡ 13, 17 (mod 20), then we have p ≡ ±2 (mod 5) and p ≡ 1 (mod 4). Using [1, Lemma 1 (2) and Lemma 4], we have d(p) < p + 1.

We assume (3) of Theorem 6 holds. In this case, we have p ≡ 3 (mod 4) and p ≡ ±2 (mod 5). By p ≡ ±2 (mod 5), we have F_{p} ≡ −1 (mod p) and F_{p+1} ≡ 0 (mod p) (cf. [4, §6]), and hence we obtain k(p) ≠ p + 1. If d(p) = p + 1, then we obtain p + 1 | k(p) since d(p) | k(p). However this is a contradiction, since k(p) ≠ p + 1, κ(p) < 2(p + 1) and k(p) | 2(p + 1) hold (cf. [4, §9]). We conclude that d(p) < p + 1.

Next, we prove that if (1) or (2) or (3) of Corollary 24 holds, then one of (1), (2), or (3) of Theorem 6 holds. When (1) of Corollary 24 holds, it is the same as in (1) of Theorem 6. We assume (2) of Corollary 24 holds. If p ≡ 1 (mod 5), then we have p ≡ 1, 11 (mod 20). If p ≡ −1 (mod 5), then we have p ≡ 9, 19 (mod 20).

We assume (3) of Corollary 24 holds. When p ≡ 2 (mod 5), we have p ≡ 7, 17 (mod 20). When p ≡ −2 (mod 5), we have p ≡ 3, 13 (mod 20). If p ≡ 13, 17 (mod 20), the condition (2) of Theorem 6 holds. We consider the case p ≡ 3, 7 (mod 20). In this case, we have p ≡ 3 (mod 4) and p ≡ ±2 (mod 5), and hence k(p) | 2(p + 1). From the well-known formula F_{n−1}F_{n+1} − F_{n}^{2} = (−1)^{n}, we get F_{d(p)−1}F_{d(p)+1} − F_{d(p)}^{2} ≡ (−1)^{d(p)} (mod p). Therefore we have F_{d(p)−1}^{2} ≡ (−1)^{d(p)} (mod p) since F_{d(p)} ≡ 0 (mod p) and F_{d(p)−1} ≡ F_{d(p)+1} (mod

p). If F_{d(p)−1}^{2} ≡ −1 (mod p), then this contradicts (\frac{−1}{p}) = −1 since p ≡ 3 (mod 4). If

F_{d(p)−1}^{2} ≡ 1 (mod p), then F_{d(p)−1} ≡ ±1 (mod p) holds. In the case of F_{d(p)−1} ≡ 1 (mod p), we have k(p) = d(p), and hence k(p) < p + 1. In the case of F_{d(p)−1} ≡ −1 (mod p), we have k(p) ≤ 2d(p) < 2(p + 1) since F_{2d(p)−1} ≡ 1 (mod p).

5 Examples

p d(p)  Y_{p}  Y_{p}^{∗}
3  4  ∅  ∅
5  5  \overline{(G(1, 3))}  \overline{(G(1, 3))}
7  8  ∅  ∅
11 10  \overline{(G(1, 4))}, \overline{(G(1, 8))}  \overline{(G(1, 4))}, \overline{(G(1, 8))}
\overline{(G(1, 3))}, \overline{(G(1, 4))}, \overline{(G(1, 5))}, \overline{(G(1, 7))},
13  7  \overline{(G(1, 9))}, \overline{(G(1, 10))}, \overline{(G(1, 11))}  \overline{(G(1, 3))}
\overline{(G(1, 3))}, \overline{(G(1, 4))}, \overline{(G(1, 6))}, \overline{(G(1, 7))}, \overline{(G(1, 9))},
17  9  \overline{(G(1, 11))}, \overline{(G(1, 12))}, \overline{(G(1, 14))}, \overline{(G(1, 15))}  \overline{(G(1, 3))}
19 18  \overline{(G(1, 5))}, \overline{(G(1, 15))}  \overline{(G(1, 5))}, \overline{(G(1, 15))}

Table 1: Examples

6 Acknowledgments

We thank the editor and the referee for reading carefully. We also express our gratitude to Toru Nakahara for valuable suggestions.

References

[1] M. Aoki and Y. Sakai, On divisibility of generalized Fibonacci numbers, Integers 15 (2015), Paper No. A31.

[2] T. Koshy, Fibonacci and Lucas Numbers with Applications, Pure and Applied Mathematics, 2001.

[3] M. Kôzaki and T. Nakahara, On arithmetic properties of generalized Fibonacci sequences, Reports of the Faculty of Science and Engineering, Saga University, Mathematics 28 (1999), 1–18.

[4] S. Nakamura, Fibonacci Sū no Micro Cosmos (Japanese), Nippon Hyoronsha, 2002.

2010 Mathematics Subject Classification: Primary 11B39. Keywords: Fibonacci number, Lucas number, generalized Fibonacci sequence.

Received November 7 2015; revised versions received January 18 2016; January 20 2016; January 25 2016. Published in Journal of Integer Sequences, February 5 2016.

Return to Journal of Integer Sequences home page.