The Generalized Bi-Periodic Fibonacci Sequence Modulo m

Hacène Belbachir and Celia Salhi^{1} USTHB Faculty of Mathematics RECITS Laboratory 16111 Bab Ezzouar, Algiers Algeria

               hacenebelbachir@gmail.com
                 salhicelia2@gmail.com
                    csalhi@usthb.dz

Abstract

For given positive integers a, b, c, and d, we consider the generalized bi-periodic Fibonacci sequence (F_{n})_{n≥0} defined by the recurrence relation F_{n} = aF_{n−1} + cF_{n−2} for n even and F_{n} = bF_{n−1} + dF_{n−2} for n odd, with initial conditions F_{0} = 0, F_{1} = 1. In the present paper, we study the periodicity of (F_{n})_{n≥0} modulo a given integer m ≥ 2 relatively prime to c and d. We extend some well-known results on the period and the rank of the classical Fibonacci sequence to the bi-periodic case.

1 Introduction

The Fibonacci sequence and its various generalizations have interested mathematicians for many years. Edson and Yayenie [4] introduced the generalized Fibonacci sequence, also known as the bi-periodic Fibonacci sequence, by considering the following piecewise linear recurrence relation with two non-zero real parameters a and b:

q_{0} = 0, q_{1} = 1, q_{n} = \begin{cases}aq_{n−1} + q_{n−2}, & for n even; \\ bq_{n−1} + q_{n−2}, & for n odd, \end{cases} (n ≥ 2).  (1)

1Corresponding author.

Many sequences in the literature are special cases of this sequence. The case a = b = 1 corresponds to the classical Fibonacci sequence \underline{A000045}, and the case a = b = 2 gives the Pell sequence \underline{A000129}, while for a = b = k for some positive integer k, we obtain the k-Fibonacci sequence [5]. A further generalization has been defined in [10, 17] by preserving the initial conditions and modifying the recurrence relation (1) in such a way that the resulting sequence (2) depends on four real parameters a, b, c, and d. Let (F_{n})_{n≥0} be the generalized bi-periodic Fibonacci sequence defined as follows:

F_{0} = 0, F_{1} = 1, F_{n} = \begin{cases}aF_{n−1} + cF_{n−2}, & for n even; \\ bF_{n−1} + dF_{n−2}, & for n odd, \end{cases} (n ≥ 2).  (2)

Notice that for c = d = 1, (F_{n})_{n≥0} reduces to the sequence (1). For the case a = b and c = d, we have the (a, c)−Fibonacci sequence.

The periodicity of linear recurrence sequences reduced modulo an integer m has been studied by several authors. The interest in this topic is the diversity of the fields of application such that cryptography (the generation of pseudo-random numbers), coding theory and electrical engineering. Wall [16] studied the periodicity of the Fibonacci sequence modulo an arbitrary integer m and established many interesting results. Vinson [15] extended the work of Wall and studied the rank of apparition of m in the Fibonacci sequence. Recently, the periodicity of various generalizations of the Fibonacci sequence has been investigated in several papers; see [1, 2, 3, 6, 7, 8, 9, 14].

In the present paper, we investigate the periodicity of the generalized bi-periodic Fibonacci sequence (F_{n})_{n≥0} modulo m ≥ 2, where a, b, c, and d are given positive integers. Assuming that m is chosen such that m is relatively prime to c and d, we prove that (F_{n})_{n≥0} reduced modulo m is periodic, i.e., there exists a positive integer r such that

F_{n+r} = F_{n},  for all n ≥ 0.  (3)

We extend some well-known results on the period and the rank of the classical Fibonacci sequences to the bi-periodic case.

Since we are dealing with the generalized bi-periodic Fibonacci sequences, reduced modulo m, the condition a ≢ b (mod m) or c ≢ d (mod m) ensures that the considered sequences are actually bi-periodic. For the case where a ≡ b (mod m) and c ≡ d (mod m) (F_{n} mod m) coincides with the (a, c)-Fibonacci sequence; see [7, 9].

Tascı and Kızılırmak [13] studied the period of the generalized bi-periodic Fibonacci sequences F_{n} for the case c = d = 1. The authors defined the period of F_{n} modulo m to be the least positive integer r such that F_{r} ≡ 0 (mod m) and F_{r+1} ≡ 1 (mod m). However, unlike the case where a = b, the integer r does not necessarily satisfy Property (3); see Example 2. Furthermore, we mention that [13, Theorem 4] is true only if we add the condition ab is also a quadratic residue modulo p (see Example 9 for p = 11).

2 The periodicity of the generalized bi-periodic Fibonacci sequences modulo m

Let a, b, c, d, and m be positive integers, and assume m is chosen such that gcd(c, m) = gcd(d, m) = 1. In this section, we investigate the period of (F_{n})_{n≥0} reduced modulo m. Flacon and Plaza [6] determined the length of the period of the k-Fibonacci sequences reduced modulo an integer m. Notice that for a = b = k and c = d = 1, (F_{n})_{n≥0} corresponds to the k-Fibonacci sequences.

Following the proof of [6, Theorem 2], we show in the next theorem that the sequence (F_{n} mod m)_{n} is periodic.

Theorem 1. The sequence (F_{n})_{n≥0} is periodic modulo m.

Proof. Since there are only m^{2} pairs of integers modulo m, at least one repetition of a pair must occur within the following m^{2} + 1 pairs of the sequence:

(F_{0}, F_{1}), (F_{2}, F_{3}), …, (F_{2m^{2}}, F_{2m^{2}+1}).

Let i and j be integers such that 0 ≤ i < j ≤ m^{2}. Let (F_{2i}, F_{2i+1}) ≡ (F_{2j}, F_{2j+1}) (mod m), with r = 2j − 2i. It follows by induction that

F_{n+r} = F_{n} for all n ≥ 2i.

Now, since c and d are invertible modulo m, by backward induction we see that the sequence F_{n} is periodic. Indeed, from the recurrence relation (2) we have

F_{2i−1} ≡ F_{2j−1}, F_{2i−2} ≡ F_{2j−2}, …, F_{1} ≡ F_{2j−2i+1} = F_{r+1}, and F_{0} ≡ F_{2j−2i} = F_{r}.

Let k(m) denote the period of the sequence (F_{n} mod m), i.e., the least positive integer r, for which (3) is satisfied.

Example 2. We consider the generalized bi-periodic Fibonacci sequence generated by a = 2 and b = c = d = 1 that we find in [11] as \underline{A048788}. The first few terms of this sequence reduced modulo p = 3 are

0, 1, 2, 0, 2, 2, 0, 2, 1, 0, 1, 1 ….

Then we only have repetitions of these terms, so k(3) = 12.

Theorem 3. Let r be a positive integer. If a ≢ b (mod m) or c ≢ d (mod m), the following assertions are equivalent:

(i) F_{n+r} ≡ F_{n} (mod m) for all n ≥ 0;

(ii) (F_{r}, F_{r+1}, F_{r+2}, F_{r+3}) ≡ (F_{0}, F_{1}, F_{2}, F_{3}) (mod m);

(iii) (F_{r}, F_{r+1}) ≡ (F_{0}, F_{1}) (mod m), and the integer r is even.

In particular, the period k(m) is an even number.

Proof. Let r be a positive integer such that (F_{r}, F_{r+1}, F_{r+2}, F_{r+3}) ≡ (F_{0}, F_{1}, F_{2}, F_{3}) (mod m). If r is an odd number, we have modulo m

a = F_{2} ≡ F_{r+2} = bF_{r+1} + dF_{r} ≡ bF_{1} + dF_{0} = b,

and

bF_{2} + dF_{1} = F_{3} ≡ F_{r+3} = aF_{r+2} + cF_{r+1} ≡ aF_{2} + cF_{1}.

Contradiction.

So when a ≢ b (mod m) or c ≢ d (mod m), the period k(m) is the smallest integer r satisfying one of the three properties of Theorem 3. Since any positive integer r that satisfies (3) is a multiple of the period k(m) by Theorem 3, we have

\begin{cases}F_{r} ≡ 0 (mod m) \\ F_{r+1} ≡ 1 (mod m) \end{cases} ⟺ k(m) | r,  (4)

for any r ∈ 2ℕ.

The following theorem shows that we can reduce the computation of k(m) to that of k(p^{e}) for all prime power factor p^{e} of m.

Theorem 4. Let m = p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{s}^{e_{s}} be the prime decomposition of m. Then

k(m) = lcm(k(p_{1}^{e_{1}}), k(p_{2}^{e_{2}}), …, k(p_{s}^{e_{s}})).

Proof. The proof is similar to the proof of [16, Theorem 2].

Theorem 5. If m | a, then we have k(m) = 2 ord_{m}(d), where ord_{m}(d) is the multiplicative order of d modulo m.

Proof. Assume that a ≡ 0 (mod m). Using Relation (2), and following a straightforward induction we get

F_{n} mod m = \begin{cases}0, & if n = 2k; \\ d^{k}, & if n = 2k + 1. \end{cases}

Since n = 2 ord_{m}(d) is the least integer satisfying the congruences F_{2n} ≡ 0 (mod m) and F_{2n+1} ≡ 1 (mod m), it follows from (4) that k(m) = 2 ord_{m}(d).

2.1 The generalized bi-periodic Fibonacci sequences over a finite field

Sahin [10] provided the Binet formula for even and odd indices as follows:

\begin{cases}F_{2n} & = a\frac{α^{n} − β^{n}}{α − β}; \\ F_{2n+1} & = \frac{α^{n+1} − β^{n+1}}{α − β} − c\frac{α^{n} − β^{n}}{α − β} , \end{cases}  (5)

where α, β = ^{\frac{(A±\sqrt{Δ})}{2}} are the roots of the quadratic equation f(x) = x^{2} − Ax + B = 0 with A = ab + c + d, B = cd, and Δ the discriminant of f(x).

Let 𝔽_{q} denote the finite field of order q = p^{e} with e ≥ 1, and let p be an odd prime. In this subsection, we investigate the period of (F_{n})_{n≥0} over the finite field 𝔽_{q} using as a main tool the Binet formula (5) and Statement (4).

We assume that gcd(c, p) = gcd(d, p) = 1 to guarantee that (F_{n})_{n≥0} is periodic over the field 𝔽_{p^{e}}. We begin by investigating the period modulo a prime p, then we generalize to a power of p. We deal only with the cases where a ≢ b (mod p) or c ≢ d (mod p). For analogous results in the case a ≡ b (mod p) and c ≡ d (mod p); see [7, 8, 9]. We establish a divisibility relation for k(p) according to the nature of the discriminant Δ in 𝔽_{p}^{∗}. When Δ ≡ 0 (mod p), we obtain an equality statement for k(p) in terms of the order of the zero of the polynomial f(x) in 𝔽_{p}^{∗}.

Notice that if p | a, then we get k(p) = 2 ord_{p}(d) using Theorem 5, where ord_{p}(d) is the order of d in 𝔽_{p}^{∗}. So in the sequel, we may assume that gcd(a, p) = 1. We also use the Legendre symbol:

(\frac{q}{p}) = \begin{cases}1, & for r a nonzero quadratic residue modulo p; \\ −1, & for r a quadratic residue modulo p. \end{cases}

Theorem 6. Let p be an odd prime. If Δ is a nonzero quadratic residue modulo p, then k(p) | 2(p − 1). Furthermore, if (\frac{α}{p}) = (\frac{β}{p} ) = 1, then k(p) | (p − 1).

Proof. Suppose that Δ is a nonzero quadratic residue modulo p. Then we have α, β ∈ 𝔽_{p}^{∗}, and by the Fermat little theorem we get

α^{p−1} ≡ 1 (mod p) and β^{p−1} ≡ 1 (mod p).

Now, using the Binet formula for even and odd indices (5), we obtain

F_{2(p−1)} = a\frac{α^{p−1} − β^{p−1}}{α − β} ≡ 0 (mod p)

and

F_{2(p−1)+1} = \frac{α^{p} − β^{p}}{α − β} − c\frac{α^{p−1} − β^{p−1}}{α − β} ≡ 1 (mod p).

Thus, by (4), k(p) | 2(p − 1).

For the second part, suppose that (\frac{α}{p}) = (\frac{β}{p} ) = 1. Then we have

α^{\frac{p−1}{2}} = β^{\frac{p−1}{2}} ≡ 1 (mod p).

Therefore,

F_{p−1} = a\frac{α^{\frac{p−1}{2}} − β^{\frac{p−1}{2}}}{α − β} ≡ 0 (mod p)

and

F_{p} = \frac{α^{\frac{p+1}{2}} − β^{\frac{p+1}{2}}}{α − β} − c\frac{α^{\frac{p−1}{2}} − β^{\frac{p−1}{2}}}{α − β} ≡ 1 (mod p).

Thus, by (4), we get k(p) | (p − 1).

Remark 7. If c = d, then we have αβ = c^{2}. Using the properties of Legendre symbol, we get

(\frac{α}{p}) = (\frac{β}{p} )

Moreover, since α ∈ 𝔽_{p}^{∗}, we have ab = α^{−1}(α − c)^{2}, where α^{−1} is the inverse of α modulo p. Thus,

(\frac{α}{p}) = (\frac{ab}{p}) .

Now, if Δ is a quadratic nonresidue modulo p, then the polynomial f(x) is irreducible in 𝔽_{p}. Therefore, we work in 𝔽_{p^{2}} = 𝔽_{p}[\sqrt{Δ}], the splitting field of the polynomial f(x) over 𝔽_{p}.

Since the Frobenius automorphism of 𝔽_{p^{2}} fixes 𝔽_{p}, it must permute the zeros of any irreducible quadratic polynomial of 𝔽_{p}[x]. Therefore, by applying the Frobenius automorphism to α, a root of the equation f(x) = 0, we obtain the other root β = α^{p}. Hence,

α^{p+1} = β^{p+1} = αβ.  (6)

Theorem 8. Let p be an odd prime. If Δ is a quadratic nonresidue modulo p, then k(p) | 2 ord_{p}(cd)(p + 1).

Proof. Suppose that Δ is a quadratic nonresidue modulo p. Then we have α^{p+1} = β^{p+1} = cd. Using the Binet formula (5), we get

F_{2 ord_{p}(cd)(p+1)} = a\frac{(α^{p+1})^{ord_{p}(cd)} − (β^{p+1})^{ord_{p}(cd)}}{α − β} ≡ 0 (mod p)

and

F_{2 ord_{p}(cd)(p+1)+1} = \frac{α(α^{p+1})^{ord_{p}(cd)} − β(β^{p+1})^{ord_{p}(cd)}}{α − β} −c\frac{(α^{p+1})^{ord_{p}(cd)} − (β^{p+1})^{ord_{p}(cd)}}{α − β}
≡ 1 (mod p).

Therefore, (4) implies that k(p) | 2 ord_{p}(cd)(p + 1).

Example 9. We take a = c = d = 1 and b = 2. So F_{n} corresponds to \underline{A002530} in [11], and we have Δ = 12.

Let p = 11; notice that Δ is a nonzero quadratic residue and ab is a quadratic nonresidue. From Theorem 6, we have k(p) | 2(p − 1) and k(p) ∤ (p − 1). So by giving the first few terms up to n = 5 (0, 1, 1, 3, 4, 0) we get k(11) = 20.

We take p = 7. Since Δ is a quadratic nonresidue modulo p from Theorem 8, we obtain k(p) | 16. So we only have to calculate 10 terms of this sequence modulo 7

0, 1, 1, 3, 4, 4, 1, 6, 0, 6.

Thus, we have k(7) = 16.

Example 10. Take a = 3, b = d = 1, and c = 4. For p = 11 both Δ and ab are nonzero quadratic residues modulo p, and from Theorem 6 we have k(p)|(p − 1). Moreover, k(p) is an even integer and F_{2} mod 11 = 3. So the only possible value is k(11) = 10.

In the following, we consider the case where Δ ≡ 0 (mod p). We begin by giving the Binet formula of F_{n} for even and odd indices as follows:

\begin{cases}F_{2n} & = a ∑_{i=1}^{n} α^{n−i}β^{i−1}; \\ F_{2n+1} & = α^{n} + ∑_{i=1}^{n} α^{n−(i+1)}β^{i}(α − c). \end{cases}

Since Δ ≡ 0 (mod p), the equation f(x) = 0 has a repeated root α in 𝔽_{p}^{∗}. So modulo p, we get the following congruences:

\begin{cases}F_{2n} & ≡ anα^{n−1}; \\ F_{2n+1} & ≡ (n + 1)α^{n} − cnα^{n−1}. \end{cases}  (7)

We give in the next theorem an explicit equality statement for k(p) in terms of the order of α in 𝔽_{p}^{∗}.

Theorem 11. Let p be an odd prime. If Δ ≡ 0 (mod p), then we have k(p) = 2p · ord_{p}(α).

Proof. Assume that Δ ≡ 0 (mod p) and gcd(a, p) = 1. By using (7) we obtain the following:

F_{2n} ≡ 0 and F_{2n+1} ≡ 1 ⟺ n(α)^{n−1} ≡ 0 and (α)^{n} ≡ 1
⟺ p | n and ord_{p}(α) | n
⟺ lcm(p, ord_{p}(α))| n
⟺ p · ord_{p}(α) | n.

Therefore, k(p) = 2p · ord_{p}(α).

Theorem 4 shows that it is easy to compute k(m) once we know k(p^{e}) for all prime power factors p^{e} of m. The corollary of the following theorem is crucial to the investigation of the period modulo p^{e}.

Theorem 12. Let p be a prime number and n be a positive integer. If a ≡ 1 (mod p), then a^{p^{n}} ≡ 1 (mod p^{n+1}).

Proof. Let P (n) be the proposition a^{p^{n}} ≡ 1 (mod p^{n+1}). We have

a ≡ 1 (mod p) ⟹ ∃s ∈ ℤ such as a = sp + 1.

For n = 1, a^{p} = (sp + 1)^{p} = ∑_{i=0}^{p} \binom{p}{i}(sp)^{i} = 1 + sp^{2} + ∑_{i=2}^{p} \binom{p}{i}(sp)^{i} ≡ 1 (mod p^{2}).

Thus, P (1) is true. Assume that P (n) is true up to some n and consider P (n + 1)

a^{p^{n+1}} = (a^{p^{n})^{p}} = (sp^{n+1} + 1)^{p} = ∑_{i=0}^{p} \binom{p}{i}(sp^{n+1})^{i} = 1 + sp^{n+2} + ∑_{i=2}^{p} \binom{p}{i}(sp^{n+1})^{i}.

Since p^{n+2} | (sp^{n+1})^{i} for 2 ≤ i ≤ p, we obtain a^{p^{n+1}} ≡ 1 (mod p^{n+2}).

Thus, P (n) holds by induction.

Corollary 13. Let p be an odd prime such that gcd(a, p) = 1, and let e be a positive integer. Then

α^{\frac{k(p)}{2} p^{e−1}} ≡ β^{\frac{k(p)}{2} p^{e−1}} ≡ 1 (mod p^{e}).

Proof. If we assume p | Δ, then α ≡ β (mod p). From Theorem 11, we get k(p) = 2p·ord_{p}(α). Thus,

α^{\frac{k(p)}{2}} ≡ β^{\frac{k(p)}{2}} ≡ 1 (mod p).

Now, assume that p ∤ Δ. Since p ∤ a by the Binet formula (5), we have

F_{k(p)} = a\frac{α^{\frac{k(p)}{2}} − β^{\frac{k(p)}{2}}}{α − β} ≡ 0 (mod p) ⟺ α^{\frac{k(p)}{2}} ≡ β^{\frac{k(p)}{2}} (mod p)

and

F_{k(p)+1} = \frac{αα^{\frac{k(p)}{2}} − ββ^{\frac{k(p)}{2}}}{α − β} − c\frac{α^{\frac{k(p)}{2}} − β^{\frac{k(p)}{2}}}{α − β}
≡ α^{\frac{k(p)}{2}}
≡ 1 (mod p).

Hence, by applying Theorem 12 to α^{\frac{k(p)}{2}} and β^{\frac{k(p)}{2}} we obtain the desired result.

Now that we have results helping in the calculation of k(p), we connect k(p) to k(p^{e}) in Theorem 14.

Theorem 14. Let p be an odd prime such that gcd(a, p) = 1, and let e be a positive integer. Then k(p^{e}) | p^{e−1}k(p).

Proof. Since gcd(a, p) = 1 from Corollary 13, we have

α^{\frac{k(p)}{2} p^{e−1}} ≡ β^{\frac{k(p)}{2} p^{e−1}} ≡ 1 (mod p^{e}).

• If we assume p ∤ Δ, then we have

F_{k(p)p^{e−1}} = a\frac{α^{\frac{k(p)p^{e−1}}{2}} − β^{\frac{k(p)p^{e−1}}{2}}}{α − β} ≡ 0 (mod p^{e})

and

\begin{aligned}F_{k(p)p^{e−1}+1} & = \frac{αα^{\frac{k(p)p^{e−1}}{2}} − ββ^{\frac{k(p)p^{e−1}}{2}}}{α − β} − c\frac{α^{\frac{k(p)p^{e−1}}{2}} − β^{\frac{k(p)p^{e−1}}{2}}}{α − β} \\ & ≡ 1 (mod p^{e}). \end{aligned}

• If we assume p | Δ, then using (7) we obtain

F_{k(p)p^{e−1}}= a\frac{k(p)p^{e−1}}{2} α^{\frac{k(p)p^{e−1}}{2} −1}

and

\begin{aligned}F_{k(p)p^{e−1}+1} & = (\frac{β^{k(p)p^{e−1}}}{2} + 1)α^{\frac{k(p)p^{e−1}}{2}} − c\frac{β^{k(p)p^{e−1}}}{2} α^{\frac{k(p)p^{e−1}}{2} −1} \\ & ≡ α^{\frac{k(p)}{2} p^{e−1}} (mod p^{e}). \end{aligned}

Now, since we have k(p) = 2p · ord_{p}(α), the following congruences holds

\begin{cases}F_{k(p)p^{e−1}} ≡ 0 (mod p^{e}); \\ F_{k(p)p^{e−1}+1} ≡ 1 (mod p^{e}). \end{cases}

Therefore, by (4), k(p^{e}) | p^{e−1}k(p).

3 The rank of the generalized bi-periodic Fibonacci sequences modulo m

The rank of (F_{n})_{n≥0} modulo m is the least positive integer r such that F_{r} ≡ 0 (mod m). Let d(m) denote the rank of (F_{n} mod m). It is obvious that if m | a, we have d(m) = 2.

In the rest, we assume that c = d and gcd(a, m) = 1.

Lemma 15. ([12]) Let ζ(n) be the parity function, and assume that c = d. The sequences (F_{n})_{n≥0} satisfies the following identities:

(i) (b/a)^{ζ(ng+n)}F_{g}F_{n+1} + (b/a)^{ζ(ng+g)}cF_{n}F_{g−1} = F_{g+n} (g ≥ 1, n ≥ 0).

(ii) (b/a)^{ζ(ng+n)}F_{n}F_{g+1} + (b/a)^{ζ(ng+g)}F_{n+1}F_{g} = (−c)^{g}F_{n−g} (g ≥ 0, n ≥ 0).

Wall [16, Theorem 3] proved that the indices of the Fibonacci sequence terms that are zero modulo m form an arithmetic progression. In the following theorem we give an analogous result for the bi-periodic case.

Theorem 16. The terms for which F_{n} ≡ 0 (mod m) have subscripts that form a simple arithmetic progression, i.e., n = xl; for x = 0, 1, 2, . . .. Moreover, l = d(m) gives all n with F_{n} ≡ 0 (mod m).

Proof. Assume that gcd(a, m) = 1, F_{i} ≡ 0 (mod m), and F_{j} ≡ 0 (mod m). By setting g = i and n = j in the identities (i) and (ii) of Lemma 15, we obtain

F_{i+j} ≡ 0 (mod m).  (8)

And with (i ≥ j)

F_{i−j} ≡ 0 (mod m).  (9)

Let

S = {k ∈ ℤ^{∗} | F_{k} ≡ 0 (mod m)} .

Since F_{k(m)} ≡ 0 (mod m) the set S is not empty. Let d be the smallest integer in S. By using induction and congruence (8), we get F_{ld} ≡ 0 (mod m) for l ∈ ℤ^{∗}. Now let α ∈ S, and suppose that d | α. Then there are two nonnegative integers θ and γ such that α = dθ + γ with 0 < γ < d. From (9), we have F_{α−θd} = F_{γ} ≡ 0 (mod m). This is a contradiction, since d is the smallest integer in S. Thus, α is a multiple of d.

From Theorem 16, we have

F_{n} ≡ 0 (mod m) ⟺ d(m) | n.  (10)

In particular, since F_{k(m)} ≡ F_{0} ≡ (mod m) then d(m) | k(m).

Let c = 1 and a, b ∈ 𝔽_{2}. Table 1 gives the rank of (F_{n} mod 2).

\begin{matrix}a & b & c & d(p) \\ 0 & 1 & 1 & 2 \\ 1 & 0 & 1 & 4 \end{matrix} ; Table 1: p = 2

We are now ready to state our theorem containing some fundamental results about the rank of (F_{n} mod m).

Theorem 17. Let m ≥ 2, and p be an odd prime such that gcd(a, p) = gcd(c, p) = 1. Then (a) If Δ is a nonzero quadratic residue modulo p, then d(p) | (p − 1).

(b) If Δ is a quadratic nonresidue modulo p, then d(p) | 2(p + 1).

(c) If Δ ≡ 0 (mod p), then if p | b we have d(p) = 2p otherwise, d(p) = p.

(d) If n | m, then d(n) | d(m).

(e) Let m = p_{1}^{e_{1}}p_{2}^{e_{2}} ⋯ p_{n}^{e_{n}} be the prime decomposition of m. Then d(m) = lcm(d(p_{1}^{e_{1}}), d(p_{2}^{e_{2}}), …, d(p_{n}^{e_{n}})).

Proof. Let p be an odd prime, and let gcd(a, p) = 1.

(a) Suppose that Δ is a nonzero quadratic residue modulo p. Then α, β ∈ 𝔽_{p}^{∗} and (\frac{α}{p}) = (\frac{β}{p} ). Hence, we have

F_{p−1} = a\frac{α^{\frac{p−1}{2}} − β^{\frac{p−1}{2}}}{α − β} ≡ 0 (mod p).

Thus, by (10), d(p) | (p − 1).

(b) Suppose that Δ is a quadratic nonresidue modulo p. Then by (6), we have

F_{2(p+1)}=a\frac{α^{p+1} − β^{p+1}}{α − β} ≡ 0 (mod p).

Thus, from (10), we get d(p) | 2 (p + 1).

(c) Suppose that Δ ≡ 0 (mod p).

If we assume that p | b, then we have α = c. Using (7), we obtain

F_{2n} ≡ an(c)^{n−1} and F_{2n+1} ≡ (c)^{n}.

Then we have F_{2n+1} ≢ 0 (mod p) since gcd(c, p) = 1, and d(p) must be even. Note that we have F_{2n} ≡ 0 (mod p) if and only if p | n. Therefore, we obtain d(p) = 2p. Now, if p ∤ b then α = −c, and we have

F_{2n} ≡ an(−c)^{n−1} ≡ 0 (mod m) ⟺ p | n

and

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

Since d(p) is the smallest positive integer n for which F_{n} ≡ 0 (mod p), we obtain d(p) = p.

(d) Since F_{d(m)} ≡ 0 (mod m) and n | m, then we have F_{d(m)} ≡ 0 (mod n). Thus, by (10), d(n) | d(m).

For the proof of (e), see [15, Lemma 2].

4 Acknowledgments

The authors would like to thank the referee for his/her careful reading and helpful comments which have improved the quality of this paper. We would also like to thank Professor Ait Amrane Yacine for her contribution in the realization of this work. We are grateful for the partial support of DGRSDT under grant number C0656701.

References

[1] L. Ait-Amrane and H. Belbachir, Periods of tribonacci sequences and elliptic curves, Algebra Discrete Math. 25 (2018), 1–17.

[2] L. Ait-Amrane, H. Belbachir, and K. Betina, Periods of Morgan-Voyce sequences and elliptic curves Math. Slovaca 6 (2016), 1267–1284.

[3] L. Ait-Amrane and H. Belbachir, The three different forms of the periods of the Morgan-Voyce sequence modulo odd primes, Les annales RECITS 3 (2016), 27–33.

[4] M. Edson and O. Yayenie, A new generalization of Fibonacci sequences and extended Binet’s formula, Integers 9 (2009), 639–654.

[5] S. Falcon and Á. Plaza, On the Fibonacci k-numbers, Chaos Solitons Fractals 32 (2007), 1615–1624.

[6] S. Falcon and Á. Plaza, k-Fibonacci sequences modulo m, Chaos Solitons Fractals 41 (2009), 497–504.

[7] H. C. Li, On second-order linear recurrence sequences, Fibonacci Quart. 37 (1999), 342–349.

[8] S. Gupta, P. Rockstroh, and F. E. Su, Splitting fields and periods of Fibonacci sequences modulo primes, Math. Mag. 85 (2012), 130–135.

[9] M. Renault, The period, rank and order of the (a, b)-Fibonacci sequence mod m, Math. Mag. 86 (2013), 372–380.

[10] M. Sahin, The Gelin-Cesàro identity in some conditional sequences, Hacet. J. Math. Stat. 40 (2011), 855–861.

[11] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2021.

[12] E. Tan and H. Leung, Some basic properties of the generalized bi-periodic Fibonacci and Lucas sequences, Adv. Difference Equ. 26 (2020), 1–11.

[13] D. Tascı and G. Ozkan Kızılırmak, On the periods of biperiodic Fibonacci and biperiodic Lucas numbers, Discrete Dyn. Nat. Soc. (2016), 1–5.

[14] D. Vella and A. Vella, Cycles in the generalized Fibonacci sequence modulo a prime, Math. Mag. 75 (2002), 294–299.

[15] J. Vinson, The relation of the period modulo m to the rank of apparition of m in the Fibonacci sequence, Fibonacci Quart. 1 (1963), 37–45.

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

[17] O. Yayenie, A note on generalized Fibonacci sequences, Appl. Math. Comput. 217 (2011), 5603–5611.

2010 Mathematics Subject Classification: Primary 11B39; Secondary 11B50, 11A07. Keywords: generalized bi-periodic Fibonacci sequence, period, rank, finite field.

(Concerned with sequences \underline{A000045}, \underline{A000129}, \underline{A002530}, and \underline{A048788}.)

Received July 3 2021; revised versions received July 9 2021; September 20 2021; September 21 2021; September 24 2021. Published in Journal of Integer Sequences, October 1 2021.

Return to Journal of Integer Sequences home page.