검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

Kyungpook Mathematical Journal 2017; 57(1): 1-84

Published online March 23, 2017

Copyright © Kyungpook Mathematical Journal.

Some Properties of Fibonacci Numbers, Generalized Fibonacci Numbers and Generalized Fibonacci Polynomial Sequences

Alexandre Laugier1
Manjil P. Saikia2

Lycée professionnel Tristan Corbiére, 16 rue de Kerveguen - BP 17149, 29671 Morlaix cedex, France1
Department of Mathematical Sciences, Tezpur University, Napaam - 784028, Assam, India2
Current Address: Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, Vienna 1090, Austria 2

Received: March 26, 2014; Accepted: May 13, 2015

In this paper we study the Fibonacci numbers and derive some interesting properties and recurrence relations. We prove some charecterizations for Fp, where p is a prime of a certain type. We also define period of a Fibonacci sequence modulo an integer, m and derive certain interesting properties related to them. Afterwards, we derive some new properties of a class of generalized Fibonacci numbers. In the last part of the paper we introduce some generalized Fibonacci polynomial sequences and we derive some results related to them.

Keywords: Fibonacci numbers, congruences, period of Fibonacci sequence

This paper is divided into six sections. This section is devoted to stating few results that will be used in the remainder of the paper. We also set the notations to be used and derive few simple results that will come in handy in our treatment. In Section 2, we charecterize numbers 5k+2, which are primes with k being an odd natural number. In Section 3, we prove more general results than given in Section 2. In Section 4, we define the period of a Fibonacci sequence modulo some number and derive many properties of this concept. In Section 5, we devote to the study of a class of generalized Fibonacci numbers and derive some interesting results related to them. Finally, in Section 6, we define some generalized Fibonacci polynomial sequences and we obtain some results related to them.

We begin with the following famous results without proof except for some related properties.

Lemma 1.1.(Euclid)

If ab ≡ 0 (mod p) with a, b two integers and p a prime, then either p|a or p|b.

Remark 1.2

In particular, if gcd(a, b) = 1, p divides only one of the numbers a, b.

Property 1.3

Let a, b two positive integers, m, n two integers such that (|m|, |n|) = 1 and p a natural number. Then

manb         (mod p)

if and only if there exists c ∈ ℤ such that

anc         (mod p)

and

bmc         (mod p).
Proof

Let a, b two positive integers, m, n two integers such that (|m|, |n|) = 1 and p a natural number.

If there exists an integer c such that a nc (mod p) and b mc (mod p), then ma mnc (mod p) and nb mnc (mod p). So, we have ma nb (mod p).

Conversely, if ma nb (mod p) with (|m|, |n|) = 1, then from Bezout’s identity, there exist three integers u, v, k such that

um+vn=1

and

ma-nb=kp.

So, we have

ukpm+vkpm=ma-nb

and

m(a-ukp)=n(b+vkp).

Since |m|, |n| are relatively prime, from Lemma 1.1, it implies that there exist two integers c, d such that

a-ukp=nc,

and

b+vkp=md.

It results that mnc = mnd and so c = d. Therefore, we obtain

a=nc+ukpnc         (mod p),

and

b=mc-vkpmc         (mod p)

Remark 1.4

Using the notations given in the proof of Property 1.3, we can see that if there exists an integer c such that a nc (mod p) and b mc (mod p) with (|m|, |n|) = 1 and p a natural number, then we have

ub+va(um+vn)cc         (mod p)

Moreover, denoting by g the gcd of a and b, if a = gn and b = gm, then ub + va = (um + vn)g = g, then g c (mod p).

Theorem 1.5.(Fermat’s Little Theorem)

If p is a prime and n ∈ ℕ relatively prime to p, then np1 ≡ 1 (mod p).

Theorem 1.6

If x2 ≡ 1 (mod p) with p a prime, then either x ≡ 1 (mod p) or x p − 1 (mod p).

Proof

If x2 ≡ 1 (mod p) with p a prime, then we have

x2-10         (mod p)(x-1)(x+1)0         (mod p)

x−1 ≡ 0 (mod p) or x+1 ≡ 0 (mod p). It is equivalent to say that x ≡ 1 (mod p) or x ≡ −1 ≡ p − 1 (mod p).

Definition 1.7

Let p be an odd prime and gcd(a, p) = 1. If the congruence x2a (mod p) has a solution, then a is said to be a quadratic residue of p. Otherwise, a is called a quadratic nonresidue of p.

Theorem 1.8.(Euler)

Let p be an odd prime and gcd(a, p) = 1. Then a is a quadratic nonresidue of p if and only if ap-12-1(mod p).

Definition 1.9

Let p be an odd prime and let gcd(a, p) = 1. The Legendre symbol (a/p) is defined to be equal to 1 if a is a quadratic residue of p and is equal to −1 is a is a quadratic non residue of p.

Property 1.10

Let p an odd prime and a and b be integers which are relatively prime to p. Then the Legendre symbol has the following properties:

  • If a b (mod p), then (a/p) = (b/p).

  • (a/p) ≡ a(p1)/2 (mod p)

  • (ab/p) = (a/p)(b/p)

Remark 1.11

Taking a = b in (3) of Property 1.10, we have

(a2/p)=(a/p)2=1.

Lemma 1.12.(Gauss)

Let p be an odd prime and let gcd(a, p) = 1. If n denotes the number of integers in the set S={a,2a,3a,,(p-12)a}, whose remainders upon division by p exceed p/2, then

(a/p)=(-1)n.

Corollary 1.13

If p is an odd prime, then

(2/p)={1ifp1(mod 8)orp7(mod 8),-1ifp3(mod 8)orp5(mod 8).

Theorem 1.14.(Gauss’ Quadratic Reciprocity Law)

If p and q are distinct odd primes, then

(p/q)(q/p)=(-1)p-12·q-12.

Corollary 1.15

If p and q are distinct odd primes, then

(p/q)={(q/p)ifp1(mod 4)         or         q1         (mod 4),-(q/p)ifpq3(mod 4).

Throughout this paper, we assume k ∈ ℕ, unless otherwise stated.

From (1) of Property 1.10, Theorem 1.14, Corollary 1.13 and Corollary 1.15, we deduce the following result.

Theorem 1.16

(5/5k + 2) = −1.

Proof

Clearly (5/5k+2) = (5k+2/5) since 5 ≡ 1 (mod 4). Again (5k+2/5) = (2/5) since 5k + 2 ≡ 2 (mod 5). Also it is a well known fact that (2/5) = −1 since 5 ≡ 5 (mod 8).

For proofs of the above theorems the reader is suggested to see [2] or [6].

Let p a prime number such that p = 5k + 2 with k an odd positive integer. From Property 1.10 and Theorem 1.16 we have

(55k+12)21         (mod 5k+2).

From Theorem 1.6, we have either

55k+12-1         (mod 5k+2)

or

55k+125k+1         (mod 5k+2).

Moreover, we can observe that

5(2k+1)1         (mod 5k+2).

Theorem 1.17

55k+125k+1(mod 5k+2) where 5k + 2 is a prime.

The proof of Theorem 1.17 follows very easily from Theorems 1.8, 1.16 and Property 1.10.

Theorem 1.18

Let r be an integer in the set {1, 2, 3, 4}. Then, we have

(5/5k+r)={1ifr=1orr=4,-1ifr=2orr=3.
Proof

We have (5/5k + r) = (5k + r/5) since 5 ≡ 1 (mod 4).

Moreover, (5k + r/5) = (r/5) since 5k + r r (mod 5).

Or, we have

  • If r = 1, then using Theorem 1.14, (r/5) = 1.

  • If r = 2, then using Corollary 1.13, (r/5) = −1.

  • If r = 3, then using Theorem 1.14, (r/5) = −1.

  • If r = 4, then since (4/5) = (22/5) = 1 (see also Remark 1.11), (r/5) = 1.

Theorem 1.19

Let r be an integer in the set {1, 2, 3, 4}. Then, if 5k + r is a prime, we have

55k+r-12{1         (mod 5k+r)ifr=1orr=4,-1         (mod 5k+r)ifr=2orr=3.

The proof of Theorem 1.19 follows very easily from Theorems 1.8, 1.18 and Property 1.10.

We fix the notation [[1, n]] = {1, 2, …, n} throughout the rest of the paper. We now have the following properties.

Remark 1.20

Let 5k + r with r ∈ [[1,4]] be a prime number. Then

k{0(mod 2)ifr=1orr=3,1(mod 2)ifr=2orr=4,

or equivalently

kr+1         (mod 2).

Property 1.21

(5k+12l+1)5k+1(mod 5k+2), with l[[0,5k2]] and 5k + 2 is a prime.

Proof

Notice that for l = 0 the property is obviously true. We also have

(5k+12l+1)=(5k+1)5k(5k-1)(5k-2l+1)(2l+1)!.

Or,

5k-2         (mod 5k+2),5k-1-3         (mod 5k+2),5k-2l+1-(2l+1)         (mod 5k+2).

Multiplying these congruences we get

5k(5k-1)(5k-2l+1)(2l+1)!         (mod 5k+2).

Therefore

(2l+1)!(5k+12l+1)(5k+1)(2l+1)!         (mod 5k+2).

Since (2l + 1)! and 5k + 2 are relatively prime, we obtain

(5k+12l+1)5k+1         (mod 5k+2).

We have now the following generalization.

Property 1.22

(5k+r-12l+1)-1(mod 5k+r), with l[[0,5k+r-22]] and 5k + r is a prime such that r ∈ [[1, 4]] and k r + 1 (mod 2).

The proof of Property 1.22 is very similar to the proof of Property 1.21.

Property 1.23

(5k2l+1)5k-2l-2(l+1)(mod 5k+2)with l[[0,5k2]] and 5k + 2 is a prime.

Proof

Notice that for l = 0 the property is obviously true. We have

(5k2l+1)=5k(5k-1)(5k-2l+1)(5k-2l)(2l+1)!.

Or

5k-2(mod 5k+2),5k-1-3(mod 5k+2),5k-2l+1-(2l+1)(mod 5k+2).

Multiplying these congruences we get

5k(5k-1)(5k-2l+1)(2l+1)!         (mod 5k+2).

Therfore

(2l+1)!(5k2l+1)(2l+1)!(5k-2l)         (mod 5k+2).

Since (2l + 1)! and 5k + 2 are relatively prime, we obtain

(5k+12l+1)5k-2l5k+2-2-2l-2(l+1)         (mod5k+2).

We can generalize the above as follows.

Property 1.24

(5k+r-22l+1)-2(l+1)(mod 5k+r), with l[[0,5k+r-32]] and 5k + r is a prime such that r ∈ [[1, 4]] and k r + 1 (mod 2)

The proof of Property 1.24 is very similar to the proof of Property 1.23.

In the memainder of this section we derive or state a few results involving the Fibonacci numbers. The Fibonacci sequence (Fn) is defined by F0 = 0, F1 = 1, Fn+2 = Fn + Fn+1 for n ≥ 0.

From the definition of the Fibonacci sequences we can establish the formula for the nth Fibonacci number,

Fn=ϕn-(1-ϕ)n5,

where ϕ=1+52 is the golden ratio.

From binomial theorem, we have for a ≠ 0 and n ∈ ℕ,

(a+b)n-(a-b)n=k=0n(nk)an-kbk(1-(-1)k)=2l=0n-12(n2l+1)an-(2l+1)b2l+1,(a+b)n-(a-b)n=2anl=0n-12(n2l+1)(ba)2l+1.

We set

a+b=ϕ=1+52,a-b=1-ϕ=1-52.

So

a=12,b=2ϕ-12=52.

Thus

ba=5.

We get, from (1.1),

ϕn-(1-ϕ)n=52n-1l=0n-12(n2l+1)5l.

Thus we have

Theorem 1.25

Fn=12n-1l=0n-12(n2l+1)5l.

Property 1.26

Fk+2=1+i=1kFi.

Theorem 1.27

Fk+l = FlFk+1 + Fl1Fk with k ∈ ℕ and l ≥ 2.

The proofs of the above two results can be found in [6].

Property 1.28

Let m be a positive integer which is greater than 2. Then, we have

F3m+2=4F3m-1+F3m-4.

The above can be generalized to the following.

Property 1.29

Let m be a positive integer which is greater than 2. Then, we have

F3m+2=4i=2mF3i-1.

The above three results can be proved in a straighforward way using the recurrence relation of Fibonacci numbers.

We now state below a few congruence satisfied by the Fibonacci numbers.

Property 1.30

Fn ≡ 0 (mod 2) if and only if n ≡ 0 (mod 3).

Corollary 1.31

If p = 5k + 2 is a prime which is strictly greater than 5 (k ∈ ℕ and k odd), then Fp = F5k+2is an odd number.

In order to prove this assertion, it suffices to remark that p is not divisible by 3.

Property 1.32

F5k ≡ 0 (mod 5) with k ∈ ℕ.

Property 1.33

Fnn with n ∈ ℕ and n ≥ 5.

The proofs of the above results follows from the principle of mathematical induction and Theorem 1.27 and Proposition 1.26. For brevity, we omit them here.

In this section, we give some new congruence relations involving Fibonacci numbers modulo a prime. The study in this section and some parts of the subsequent sections are motivated by some similar results obtained by Bicknell-Johnson in [1] and by Hoggatt and Bicknell-Johnson in [5].

Let p = 5k + 2 be a prime number with k a non-zero positive integer which is odd. Notice that in this case, 5k ± 1 is an even number and so

5k±12=5k±12.

We now have the following properties.

Property 2.1

F5k+2 ≡ 5k + 1 (mod 5k + 2) with k ∈ ℕ and k odd such that 5k+2 is prime.

This result is also stated in [5], but we give a different proof of the result below.

Proof

From Theorems 1.17 and 1.25, we have

25k+1F5k+2=l=05k+12(5k+22l+1)5l55k+125k+1         (mod 5k+2)

where we used the fact that (5k+22l+1) is divisible by 5k + 2 for l=0,1,,5k-12.

From Fermat’s Little Theorem, we have

25k+11         (mod 5k+2).

We get F5k+2 ≡ 5k + 1 (mod 5k + 2).

Property 2.2

F5k+1 ≡ 1 (mod 5k + 2) with k ∈ ℕ and k odd such that 5k + 2 is prime.

Proof

From Theorem 1.25 and Property 1.21, we have

25kF5k+1=l=05k2(5k+12l+1)5l(5k+1)l=05k25l         (mod 5k+2).

We have

l=05k25l=55k2+1-14.

We get from the above

25k+2F5k+1(5k+1){55k2+1-1}         (mod 5k+2).

Since k is an odd positive integer, there exists a positive integer m such that k = 2m + 1. It follows that

5k2=5m+2.

Notice that 5k + 2 = 10m + 7 is prime, implies that k ≠ 5 and k ≠ 11 or equivalently m ≠ 2 and m ≠ 5. Other restrictions on k and m can be given.

From Theorem 1.17 we have

55m+310m+6         (mod 10m+7).

We can rewrite l=05k25l=55k2+1-14 as

l=05k25l=55m+3-14.

Moreover, we have (5k+1)   {55k2+1-1}=(10m+6)   {55m+3-1}.

Or,

(10m+6)   {55m+3-1}55m+3{55m+3-1}510m+6-10m-6         (mod   10m+7).

We have

(10m+6)   {55m+3-1}510m+6+1         (mod 10m+7).

From Fermat’s Little Theorem, we have 510m+6 ≡ 1 (mod 10m + 7). Therefore

(10m+6){55m+3-1}2         (mod 10m+7),

or equivalently

(5k+1){55k2+1-1}2         (mod 5k+2).

It follows that

25k+2F5k+12         (mod 5k+2).

Since 2 and 5k + 2 are relatively prime, so

25k+1F5k+11         (mod 5k+2).

From Fermat’s Little Theorem, we have 25k+1 ≡ 1 (mod 5k + 2). Therefore

F5k+11         (mod 5k+2).

Property 2.3

F5k ≡ 5k (mod 5k + 2) with k ∈ ℕ and k odd such that 5k + 2 is prime.

Proof

From Theorem 1.25 and Property 1.23 we have

25k-1F5k=l=05k-12(5k2l+1)5ll=05k-12(5k-2l)5l         (mod 5k+2).

Also

l=05k-12(5k-2l)5l=5[3×55k-12-(2k+1)]8,

where we have used the fact that for x ≠ 1 and n ∈ ℕ we have

l=0nlxl=(n+1)(x-1)xn+1-xn+2+x(x-1)2.

So

25k+2F5k5(3×55k-12-(2k+1))         (mod 5k+2).

Moreover since k = 2m + 1, we have

3×55k-12-(2k+1)=3×55m+2-(4m+3).

Since 55m+3 ≡ 10m + 6 (mod 10m + 7), we have

3×55m+330m+1840m+25         (mod 10m+7).

Consequently

3×55m+28m+5         (mod 10m+7),

which implies

3×55m+2-(4m+3)4m+2         (mod 10m+7),

or equivalently for k = 2m + 1

3×55k-12-(2k+1)2k         (mod 5k+2),25k+2F5k2×5k         (mod5k+2).

Since 2 and 5k + 2 are relatively prime, so

25k+1F5k5k         (mod 5k+2).

From Fermat’s Little Theorem, we have 25k+1 ≡ 1 (mod 5k + 2). Therefore

F5k5k         (mod 5k+2).

Property 2.4

Let 5k + 2 be a prime with k odd and let m be a positive integer which is greater than 2. Then, we have

F3m2(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2).
Proof

We prove the result by induction. We know that F6 = 8. Or, 2(3+F2) = 2(3 + 1) = 2 × 4 = 8. So

F6=F3×2=2(3+F2)2(3+F2)         (mod 5k+2).

Let us assume that F3m2(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2) with m ≥ 2.

For m a positive integer, we have, by Theorem 1.27,

F3(m+1)=F3m+3=F3F3m+1+F2F3m=2F3m+1+F3m=2(F3m+F3m-1)+F3m=2F3m-1+3F3m.

From the assumption above, we get

F3(m+1)2F3m-1+2(3m+i=1m-13m-iF3i-1)         (mod 5k+2)2(3m+i=1m3m-iF3i-1)         (mod 5k+2).

Thus the proof is complete by induction.

Theorem 2.5

Let 5k +2 be a prime with k an odd integer and let m be a positive integer which is greater than 2. Then

F5mk5K(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2)

and

F5mk+1F3m-1         (mod 5k+2).
Proof

We prove the theorem by induction. We have, using Theorem 1.27

F10k=F5k+5k=F5kF5k+1+F5k-1F5k=F5k(F5k+1+F5k-1).

Using Properties 2.1, 2.2 and 2.3, we can see that

F10k20k         (mod 5k+2).

Also

5k(3+i=1131-iF3i-1)=5k(3+F2)=20k20k         (mod 5k+2).

So

F10k=F5×2k5k(3+i=1131-iF3i-1)         (mod 5k+2).

Moreover, we have from Theorem 1.27, Property 2.2 and Property 2.3,

F10k+1=F5k+5k+1=F5k+12+F5k21+25k2         (mod 5k+2).

We have

(5k+2)2=25k2+20k+425k2+10k0         (mod 5k+2).

So

25k2-10k2(5k+2)-10k4         (mod 5k+2).

Therefore

F10k+1F55         (mod 5k+2),

or equivalently

F5×2k+1F3×2-15         (mod 5k+2).

Let us assume that

F5mk5k(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2)

and

F5mk+1F3m-1         (mod 5k+2).

Then, we have

F5(m+1)k=F5mk+5k=F5kF5mk+1+F5k-1F5mk.

Using Property 2.3 and F5k1 ≡ 3 (mod 5k + 2), from the assumptions above, we have

F5(m+1)k5kF3m-1+3×5k(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2).

It gives

F5(m+1)k5k(3m+i=1m3m-iF3i-1)         (mod 5k+2).

Moreover, we have

F5(m+1)k+1=F5mk+5k+1=F5k+1F5mk+1+F5kF5mk.

Using Properties 2.2 and 2.3 and the assumptions above, and since 25k2 ≡ 4 (mod 5k + 2), we have

F5(m+1)k+1F3m-1+25k2(3m-1+i=1m-13m-i-1F3i-1)         (mod 5k+2)F3m-1+4(3m-1+i=1m-13m-i-1F3i-1)         (mod 5k+2)F3m-1+2F3m         (mod 5k+2).

Or,

F3m-1+2F3m=F3m-1+F3m+F3m=F3m+1+F3m=F3m+2.

Therefore

F5(m+1)k+1F3m+2         (mod 5k+2),

or equivalently

F5(m+1)k+1F3(m+1)-1         (mod 5k+2).

This completes the proof.

Corollary 2.6

Let 5k + 2 be a prime with k an odd integer and m be a positive integer which is greater than 2. Then

F5mk+2F3m-1+5k(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2),F5mk+32F3m-1+5k(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2),

and

F5mk+43F3m-1+10k(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2).

Theorem 2.7

Let 5k+2 be a prime with k an odd positive integer, m be a positive integer which is greater than 2 and r ∈ ℕ. Then

Fm(5k+r)FmrF3m-1+5kFmr-1(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2).
Proof

For m, r two non-zero positive integers, we have by Theorem 1.27

Fm(5k+r)=F5mk+mr=FmrF5mk+1+Fmr-1F5mk.

From Theorem 2.5, we have for m ≥ 2 and r ∈ ℕ

Fm(5k+r)FmrF3m-1+5kFmr-1(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2).

This completes the proof.

Remark 2.8

In particular, if r = 3, we know that

Fm(5k+3)0         (mod 5k+2).

This congruence can be deduced from Property 2.4 and Theorem 2.7. Indeed, using Theorem 2.7, we have

Fm(5k+3)F3mF3m-1+5kF3m-1(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2)F3mF3m-1+5kF3m-1(3m-1+i=1m-13m-1-iF3i-1)-(5k+2)F3m-1(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2)F3mF3m-1-2F3m-1(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2).

Using Property 2.4, we get

Fm(5k+3)F3mF3m-1-F3m-1F3m0         (mod 5k+2).

Corollary 2.9

Let 5k +2 be a prime with k an odd positive integer and m, r ∈ ℕ. Then

Fm(5k+r)FmrF3m-1-Fmr-1F3m         (mod 5k+2).

Lemma 2.10

Let 5k + 2 be a prime with k an odd positive integer and r ∈ ℕ. Then

F5k+rFr-2Fr-1         (mod 5k+2).
Proof

We prove this lemma by induction. For r = 1, we have F5k+r = F5k+1 ≡ 1 (mod 5k + 2) and Fr − 2Fr1 = F1 − 2F0 = F1 ≡ 1 (mod 5k + 2).

Let us assume that F5k+sFs −2Fs1 (mod 5k+2) for s ∈ [[2, r]] with r ≥ 2. Using the assumption, we have for r ≥ 2

F5k+r+1F5k+r+F5k+r-1         (mod5k+2)Fr-2Fr-1+Fr-1-2Fr-2         (mod5k+2)Fr+Fr-1-2(Fr-1+Fr-2)         (mod5k+2)Fr+1-2Fr         (mod 5k+2).

Thus the lemma is proved.

We can prove Lemma 2.10 as a consequence of Corollary 2.9 by taking m = 1.

Corollary 2.11

Let 5k + 2 be a prime with k an odd positive integer, let m be a positive integer and r ∈ ℕ. Then

Fm(5k+r)FmrF3m+1-Fmr+1F3m         (mod 5k+2).

The above corollary can be deduced from Corollary 2.9.

Lemma 2.12

Let 5k +2 be a prime with k an odd positive integer and let m be a positive integer. Then

F5mk+F3m0         (mod 5k+2).
Proof

For m = 0, we have F5mk + F3m = 2F0 = 0 ≡ 0 (mod 5k + 2). For m = 1, we have F5mk +F3m = F5k +F3 ≡ 5k+2 ≡ 0 (mod 5k+2). So, it remains to prove that for m ≥ 2, we have F5mk + F3m ≡ 0 (mod 5k + 2).

From Theorem 2.5, we have

F5mk5k(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2)5k(3m-1+i=1m-13m-1-iF3i-1)-(5k+2)(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2)-2(3m-1+i=1m-13m-1-iF3i-1)         (mod 5k+2).

From Property 2.4, we have F5mk ≡ −F3m (mod 5k + 2).

We can prove Corollary 2.11 as a consequence of Lemma 2.12.

Remark 2.13

We can observe that

F1×(5k+r)=F5k+r

and

F1×rF3×1+1-F1×r+1F3×1=FrF4-Fr+1F3=3Fr-2Fr+1.

By Properties 2.1, 2.2 and 2.3, we have

r=1:         F5k+r=F5k+11         (mod 5k+2)3Fr-2Fr+1=3F1-2F2=11         (mod5k+2)r=2:         F5k+r=F5k+25k+1         (mod 5k+2)3Fr-2Fr+1=3F2-2F3=-15k+1         (mod 5k+2)r=3:         F5k+r=F5k+30         (mod 5k+2)3Fr-2Fr+1=3F3-2F4=00         (mod 5k+2)r=4:         F5k+r=F5k+45k+1         (mod 5k+2)3Fr-2Fr+1=3F4-2F5=-15k+1         (mod 5k+2)

So, we have

F5k+r3Fr-2Fr+1         (mod 5k+2)

or equivalently

F1×(5k+r)F1×rF3×1+1-F1×r+1F3×1         (mod 5k+2)

with r ∈ [[1, 4]].

Thus we have the following.

Property 2.14

Let 5k + 2 be a prime with k an odd positive integer, let m be a positive integer and r ∈ ℕ. Then

F5k+r3Fr-2Fr+1         (mod 5k+2).
Proof

We have

F5k+0=F5k5k         (mod 5k+2)

and

3F0-2F1=-25k         (mod 5k+2).

So, F5k ≡ 3F0 − 2F1 (mod 5k + 2).

Moreover, we know that

F5k+13F1-2F21         (mod 5k+2).

Let us assume that

F5k+s3Fs-2Fs+1         (mod 5k+2)

for s ∈ [[1, r]]. We have for r ∈ ℕ,

F5k+r+1=F5k+r+F5k+r-13Fr-2Fr+1+3Fr-1-2Fr         (mod 5k+2)3(Fr+Fr-1)-2(Fr+1+Fr)         (mod 5k+2)3Fr+1-2Fr+2         (mod 5k+2).

Thus the proof is complete by induction.

Property 2.15

Let 5k + 2 be a prime with k odd and let m be a positive integer which is greater than 2. Then, we have

F3m+13m+2i=1m-13m-1-iF3i         (mod 5k+2).
Proof

We prove the result by induction. We have for m = 2, F3m+1 = F3×2+1 = F7 = 13 and 3m+2i=1m-13m-1-iF3i=32+2F3=9+2×2=9+4=13. So, F7 ≡ 32 + 2F3 ≡ 13 (mod 5k + 2).

Let us assume that for m ≥ 2 the result holds. Using this assumption, we have for m ≥ 2

F3(m+1)+1=F3m+4=F4F3m+1+F3F3m=3F3m+1+2F3m3m+1+2i=1m-13m-iF3i+2F3m         (mod5k+2)3m+1+2i=1m3m-iF3i         (mod5k+2).

Thus the induction hypothesis holds.

Corollary 2.16

Let 5k + 2 be a prime with k odd and let m be a positive integer which is greater than 2. Then, we have

F3m+2=3m+2(3m-1+i=1m-13m-1-iF3i+1)         (mod 5k+2).
Proof

It stems from the recurrence relation of the Fibonacci sequence which implies that F3m+2 = F3m + F3m+1 and F3k+1 = F3k + F3k1 and Property 2.4 and Property 2.15.

In this section we state and prove some more results of the type that were proved in the previous section. These results generalizes some of the results in the previous section and in [1] and [5].

Let p = 5k + r with r ∈ [[1,4]] be a prime number with k a non-zero positive integer such that k r +1 (mod 2). Notice that 5k +r ±1 is an even number and so

5k+r±12=5k+r±12.

We have the following properties.

Property 3.1

We have

F5k+r55k+r-12{1         (mod 5k+r)ifr=1orr=4,-1         (mod 5k+r)ifr=2orr=3,

with r ∈ [[1, 4]] k ∈ ℕ and k r + 1 (mod 2) such that 5k + r is prime.

This result is also stated in [5], here we give a different proof below.

Proof

From Theorems 1.17 and 1.25 we have

25k+r-1F5k+r=l=05k+r-12(5k+r2l+1)5l55k+r-12         (mod 5k+r),

where we used the fact that (5k+r2l+1) is divisible by 5k + r for l=0,1,,5k+r-32.

From Theorem 1.5, we have

25k+r-11         (mod 5k+r).

We get F5k+r55k+r-12         (mod 5k+r). The rest of the theorem stems from Theorem 1.19.

Corollary 3.2

Let p be a prime number which is not equal to 5. Then, we have

Fp{1         (mod p)ifp1(mod 5)orp4(mod 5),p-1         (mod p)ifp2(mod 5)orp3(mod 5).
Proof

We can notice that F2 = 1 ≡ 1 (mod 2) and 2 ≡ 2 (mod 5). Moreover, we can notice that F3 = 2 ≡ 2 (mod 3) and 3 ≡ 3 (mod 5). So, Corollary 3.2 is true for p = 2, 3.

We can observe that the result of Corollary 3.2 doesn’t work for p = 5 since F5 = 5 ≡ 0 (mod 5).

The Euclid division of a prime number p > 5 by 5 allows to write p like 5k + r with 0 ≤ r < 5 and k r+1 (mod 2). Then, applying Property 3.1, we verify that the result of Corollary 3.2 is also true for p > 5.

It completes the proof of this corollary.

Property 3.3

We have

F5k+r-1{0         (mod 5k+r)ifr=1orr=4,1         (mod 5k+r)ifr=2orr=3

with r ∈ [[1, 4]] k ∈ ℕ and k r + 1 (mod 2) such that 5k + r is prime.

Some parts of this result is stated in [1] in a different form. We give an alternate proof of the result below.

Proof

From Theorem 1.25 and Property 1.22 we have

25k+rF5k+r-1=4l=05k+r-22(5k+r-12l+1)5l4(5k+r-1)l=05k+r-225l         (mod 5k+r).

It comes that

25k+rF5k+r-1(5k+r-1)(55k+r-22+1-1)         (mod 5k+r).

From Theorem 1.5, we have

25k+r2         (mod 5k+r).

So, since 5k +r −1 is even and since 2 and 5k +r are relatively prime when 5k +r prime, we obtain

F5k+r-15k+r-12(55k+r-12+1-1)         (mod 5k+r).

Since 5k + r − 1 is even and so 5k+r-12 is an integer, we can notice that

5k+r-22+1=5k+r-12-12+1=5k+r-12+-12+1=5k+r-12+1-12=5k+r-12+12=5k+r-12

where we used the property that ⌊n + x⌊ = n + ⌊x⌋ for all n ∈ ℕ and for all x ∈ ℝ.

It follows that

F5k+r-15k+r-12(55k+r-12-1)         (mod 5k+r).

The case r = 2 was done above. We found (see Property 2.2) and we can verify from the congruence above that

F5k+11         (mod 5k+2).

From Theorem 1.19, if r = 1, we have 55k+r-12=55k21         (mod 5k+1). So, using (3.1), we deduce that

F5k0         (mod 5k+1).

From Theorem 1.19, if r = 3, we have 55k+r-12=55k+22-15k+2         (mod 5k+3). So, using (3.1), we deduce that

F5k+2-(5k+2)1         (mod 5k+3).

From Theorem 1.19, if r = 4, we have 55k+r-12=55k+321         (mod 5k+4). So, using (3.1), we deduce that

F5k+30         (mod 5k+4).

The following two results are easy consequences of Properties 3.1 and 3.3.

Property 3.4

We have

F5k+r-2{1         (mod 5k+r)ifr=1orr=4,-2         (mod 5k+r)ifr=2orr=3,

with r ∈ [[1, 4]] k ∈ ℕ and k r + 1 (mod 2) such that 5k + r is prime.

Property 3.5

We have

F5k+r+1{1         (mod 5k+r)ifr=1orr=4,0         (mod 5k+r)ifr=2orr=3,

with r ∈ [[1, 4]] k ∈ ℕ and k r + 1 (mod 2) such that 5k + r is prime.

The following is a consequence of Properties 3.1 and 3.5.

Property 3.6

We have

F5k+r+2{2         (mod 5k+r)ifr=1orr=4,-1         (mod 5k+r)ifr=2orr=3,

with r ∈ [[1, 4]] k ∈ ℕ and k r + 1 (mod 2) such that 5k + r is prime.

Some of the stated properties above are given in [1] and [5] also, but the methods used here are different.

Notice that F1 = F2 ≡ 1 (mod m) with m an integer which is greater than 2.

Definition 4.1

The Fibonacci sequence (Fn) is periodic modulo a positive integer m which is greater than 2 (m ≥ 2), if there exists at least a non-zero integer m such that

F1+mF2+m1         (mod m).

The number m is called a period of the Fibonacci sequence (Fn) modulo m.

Remark 4.2

For m ≥ 2 we have lm ≥ 2. Indeed, m cannot be equal to 1 since F3 = 2.

From Theorem 1.27 we have

F2+m=FmF3+Fm-1F22Fm+Fm-1         (mod m).

Since Fm + Fm−1 = F1+m, we get

F2+m2Fm+Fm-1Fm+F1+mFm+F2+m         (mod m).

Therefore we have the following.

Property 4.3

Fm ≡ 0 (mod m).

Moreover, from Theorem 1.27 we have

F1+mFmF2+Fm-1F1Fm+Fm-1Fm-1         (mod m).

Since F1+m ≡ 1 (mod m), we obtain the following.

Property 4.4

Fm−1 ≡ 1 (mod m).

Besides, using the recurrence relation of the Fibonacci sequence, from Property 4.3 we get

Fm-2+Fm-1=Fm0         (modm).

Using Property 4.4, we obtain

Property 4.5

Fm−2m − 1 (mod m).

Remark 4.6

From Theorem 1.27 we have for m ≥ 2

F2m=Fm+m=FmFm+1+Fm-1Fm=Fm(Fm+1+Fm-1),

and

F2m+1=F(m+1)+m=FmFm+2+Fm-1Fm+1=Fm(Fm+Fm+1)+Fm-1(Fm-1+Fm)=Fm(2Fm+Fm-1)+Fm-1(Fm-1+Fm)=2Fm2+2FmFm-1+Fm-12=Fm2+Fm+12.

From this we get

F2m+2=F2m+1+F2m=Fm2+Fm+12+Fm(Fm+1+Fm-1),F2m+3=F3F2m+1+F2F2m=2(Fm2+Fm+12)+Fm(Fm+1+Fm-1),

and

F2m+4=F2m+3+F2m+2=3(Fm2+Fm+12)+2Fm(Fm+1+Fm-1).

Theorem 4.7

A period of the Fibonacci sequence modulo 5k + 2 with 5k + 2 a prime and k odd is given by

5k+2=2(5k+3).
Proof

Using the recurrence relation of the Fibonacci sequence, and from Properties 2.1, 2.2 and 2.3, we have

F5k+3=F5k+2+F5k+15k+20         (mod 5k+2).

Taking m = 5k + 2 prime (k odd) in the formulas of F2m+3 and F2m+4, we have

F10k+7=2(F5k+22+F5k+32)+F5k+2(F5k+3+F5k+1)2(5k+1)2+5k+1         (mod 5k+2)50k2+20k+2+5k+110k(5k+2)+(5k+2)+1         (mod 5k+2)1+(10k+1)(5k+2)1         (mod 5k+2),

and

F10k+8=3(F5k+22+F5k+32)+2F5k+2(F5k+3+F5k+1)3(5k+1)2+2(5k+1)         (mod 5k+2)75k2+30k+3+10k+2         (mod 5k+2)15k(5k+2)+2(5k+2)+1         (mod 5k+2)1+(15k+2)(5k+2)1         (mod 5k+2).

Thus

F10k+7F10k+81         (mod 5k+2),

or equivalently

F1+2(5k+3)F2+2(5k+3)1         (mod 5k+2).

We deduce that a period of the Fibonacci sequence modulo 5k + 2 with 5k + 2 a prime is 5k+2 = 2(5k + 3).

We can generalize the above result as follows.

Theorem 4.8

A period of the Fibonacci sequence modulo 5k + r with 5k + r a prime such that r = 2, 3 and k r + 1 (mod 2) is given by

5k+r=2(5k+r+1).
Proof

Using the formula for F2m given in Remark 4.6, taking m = 5k + r +1, we have

F2(5k+r+1)=F5k+r+1(F5k+r+F5k+r+2).

From Properties 3.1, 3.5 and 3.6, we obtain

F2(5k+r+1){3         (mod 5k+r)ifr=1orr=4,0         (mod 5k+r)ifr=2orr=3.

Using the formula for F2m+1 given in Remark 4.6, taking m = 5k + r + 1, we have

F2(5k+r+1)+1=F5k+r+12+F5k+r+22.

From Properties 3.1 and 3.5, we obtain

F2(5k+r+1)+1{5         (mod 5k+r)ifr=1orr=4,1         (mod 5k+r)ifr=2orr=3.

Using the recurrence relation of the Fibonacci sequence, we have F2(5k+r+1)+2 = F2(5k+r+1) + F2(5k+r+1)+1. So

F2(5k+r+1)+2{8         (mod 5k+r)ifr=1orr=4,1         (mod 5k+r)ifr=2orr=3.

Therefore, when 5k +r is prime such that r = 2,3 and k r +1 (mod 2), we have F2(5k+r+1) ≡ 0 (mod 5k + r) and F2(5k+r+1)+1F2(5k+r+1)+2 ≡ 1 (mod 5k + r). It results that if 5k + r is prime such that r = 2,3 and k r + 1 (mod 2), then 2(5k + r + 1) is a period of the Fibonacci sequence modulo 5k + r.

Theorem 4.9

A period of the Fibonacci sequence modulo 5k + r with 5k + r a prime such that r = 1, 4 and k r + 1 (mod 2) is given by

5k+r=2(5k+r-1).
Proof

Using the formula for F2m given in Remark 4.6, taking m = 5k + r − 1, we have

F2(5k+r-1)=F5k+r-1(F5k+r+F5k+r-2).

From Properties 3.1, 3.3 and 3.4, we obtain

F2(5k+r-1){0         (mod 5k+r)ifr=1orr=4,-3         (mod 5k+r)ifr=2orr=3.

Using the formula for F2m+1 given in Remark 4.6, taking m = 5k + r − 1, we have

F2(5k+r-1)+1=F5k+r-12+F5k+r2.

From Properties 3.1 and 3.3, we obtain

F2(5k+r-1)+1{1         (mod 5k+r)ifr=1orr=4,2         (mod 5k+r)ifr=2orr=3.

Using the recurrence relation of the Fibonacci sequence, we have F2(5k+r1)+2 = F2(5k+r1) + F2(5k+r1)+1. So

F2(5k+r-1)+2{1         (mod 5k+r)ifr=1orr=4,-1         (mod 5k+r)ifr=2orr=3.

Therefore, when 5k +r is prime such that r = 1,4 and k r +1 (mod 2), we have F2(5k+r1) ≡ 0 (mod 5k + r) and F2(5k+r1)+1F2(5k+r1)+2 ≡ 1 (mod 5k + r). It results that if 5k + r is prime such that r = 1,4 and k r + 1 (mod 2), then 2(5k + r − 1) is a period of the Fibonacci sequence modulo 5k + r.

Corollary 4.10

A period of the Fibonacci sequence modulo 5k + r with 5k + r a prime such that r = 1, 2, 3, 4 and k r + 1 (mod 2) is given by

5k+r={10kifr=1,2(5k+3)ifr=2         or         r=4,2(5k+4)ifr=3,

or more compactly

5k+r=10k+3(1+(-1)r)+2(r-1)(1-(-1)r).

Corollary 4.10 follows from Theorems 4.8 and 4.9.

Corollary 4.11

A period of the Fibonacci sequence modulo p with p a prime which is not equal to 5 is given by

p={2(p-1)ifp1(mod5)orp4(mod5),2(p+1)ifp2(mod5)orp3(mod5).
Proof

The Euclid division of p by 5 is written p = 5k + r with 0 ≤ r < 5 and k r + 1 (mod 2). Then, applying Corollary 4.10, it gives:

r=1p=5k+1p=5k+1=10k=2p-2=2(p-1)r=2p=5k+2p=5k+2=10k+6=2p+2=2(p+1)r=3p=5k+3p=5k+3=10k+8=2p+2=2(p+1)r=4p=5k+4p=5k+4=10k+6=2p-2=2(p-1).

Property 4.12

A period of the Fibonacci sequence modulo 5 is 20.

Proof

From Property 1.32, we know that F5k ≡ 0 (mod 5) with k ∈ ℕ. Using the recurrence relation of the Fibonacci sequence, we have F5k+1F5k+2 (mod 5). So, it is relevant to search a period as an integer multiple of 5. Trying the first non-zero values of k, it gives:

k=1F5k+1=F63         (mod5)F5k+2=F73         (mod5)k=2F5k+1=F114         (mod5)F5k+2=F124         (mod5)k=3F5k+1=F162         (mod5)F5k+2=F172         (mod5)k=4F5k+1=F211         (mod5)F5k+2=F221         (mod5).

Property 4.13

Let k be a positive integer. Then, we have

F5k+1F5k+21(mod 5)ifk0(mod 4),F5k+1F5k+23(mod 5)ifk1(mod 4),F5k+1F5k+24(mod 5)ifk2(mod 4),F5k+1F5k+22(mod 5)ifk3(mod 4),
Proof

Since F5k ≡ 0 (mod 5), using the recurrence relation of the Fibonacci sequence, we have F5k+2 = F5k+1 + F5kF5k+1 (mod 5).

If k ≡ 0 (mod 4) and k ≥ 0, then there exists a positive integer m such that k = 4m. So, if k ≡ 0 (mod 4) and k ≥ 0, since 20 is a period of the Fibonacci sequence modulo 5 (see Property 4.12), then we have F5k+1 = F20m+1F1 ≡ 1 (mod 5).

If k ≡ 1 (mod 4) and k ≥ 0, then there exists a positive integer m such that k = 4m + 1. Using Theorem 1.27, it comes that

F5k+1=F20m+6=F6F20m+1+F5F20m.

So, if k ≡ 1 (mod 4) and k ≥ 0, since F6 = 8 ≡ 3 (mod 5), F5 = 5 ≡ 0 (mod 5) and since 20 is a period of the Fibonacci sequence modulo 5 (see Property 4.12), then we have F5k+1F6F1 ≡ 3 (mod 5).

If k ≡ 2 (mod 4) and k ≥ 0, then there exists a positive integer m such that k = 4m + 2. Using Theorem 1.27, it comes that

F5k+1=F20m+11=F11F20m+1+F10F20m.

So, if k ≡ 2 (mod 4) and k ≥ 0, since F11 = 89 ≡ 4 (mod 5), F10 = 55 ≡ 0 (mod 5) and since 20 is a period of the Fibonacci sequence modulo 5 (see Property 4.12), then we have F5k+1F11F1 ≡ 4 (mod 5).

If k ≡ 3 (mod 4) and k ≥ 0, then there exists a positive integer m such that k = 4m + 3. Using Theorem 1.27, it comes that

F5k+1=F20m+16=F16F20m+1+F15F20m.

So, if k ≡ 3 (mod 4) and k ≥ 0, since F16 = 987 ≡ 2 (mod 5), F15 = 610 ≡ 0 (mod 5) and since 20 is a period of the Fibonacci sequence modulo 5 (see Property 4.12), we have

F5k+1F16F12         (mod 5).

Property 4.14

Let k be a positive integer. Then, we have

F5k+32         (mod 5)F5k+43         (mod 5)ifk0         (mod 4),F5k+31         (mod 5)F5k+44         (mod 5)ifk1         (mod 4),F5k+33         (mod 5)F5k+42         (mod 5)ifk2         (mod 4),F5k+34         (mod 5)F5k+41         (mod 5)ifk3         (mod 4),

Property 4.14 stems from the recurrence relation of the Fibonacci sequence and Property 4.13.

Corollary 4.15

The minimal period of the Fibonacci sequence modulo 5 is 20.

Corollary 4.15 stems from Euclid division, Properties 4.12, 4.13 and 4.14.

Property 4.16

Let 5k + 1 be a prime with k a non-zero even positive integer. Then, we have (m ∈ ℕ)

F5mk0         (mod 5k+1),

and

F5mk+11         (mod 5k+1).
Proof

Let prove the property by induction on the integer m.

We have F0 = 0 ≡ 0 (mod 5k + 1) and F1 = 1 ≡ 1 (mod 5k + 1).

Moreover, from Properties 3.1 and 3.3, we can notice that

F5k0         (mod 5k+1)

and

F5k+11         (mod 5k+1).

Let assume that for a positive integer m, we have

F5mk0         (mod 5k+1)

and

F5mk+11         (mod 5k+1).

Then, using the assumption, Theorem 1.27 and Properties 3.1 and 3.3, we have

F5(m+1)k=F5mk+5k=F5mkF5k+1+F5mk-1F5k0         (mod 5k+1)

and

F5(m+1)k+1=F5mk+1+5k=F5mk+1F5k+1+F5mkF5k1         (mod 5k+1).

This completes the proof by induction on the integer m.

Property 4.17

A period of the Fibonacci sequence modulo 5k + 1 with 5k + 1 prime is 5k.

This is a direct consequence of Property 4.16.

Property 4.18

A period of the Fibonacci sequence modulo 5k + 4 with 5k + 4 prime and k a non-zero odd positive integer is 5k + 3.

Proof

From Properties 3.1, 3.3 and 3.5, we have

F5k+30         (mod 5k+4),

and

F5k+4F5k+51         (mod 5k+4).

So

F1+5k+3F2+5k+31         (mod 5k+4).

It results that 5k + 3 is a period of the Fibonacci sequence modulo 5k + 4.

Corollary 4.19

A period of the Fibonacci sequence modulo p with p a prime which is not equal to 5 is given by

p={p-1ifp1(mod 5)orp4(mod 5),2(p+1)ifp2(mod 5)orp3(mod 5).

Corollary 4.19 stems from Corollary 4.11 and Properties 4.17 and 4.18.

Property 4.20

Let 5k + 1 be a prime with k a non-zero even positive integer. Then, for all m ∈ [[0, 5]]

F5k-m(-1)m+1Fm         (mod 5k+1).
Proof

We prove this result by induction on the integer m.

From Properties 3.3 and 3.4, we have

F5k0         (mod 5k+1),

and

F5k-11         (mod 5k+1).

So, we verify that (4.1) is true when m = 0 and m = 1. Notice that (4.1) is verified when m = 5k since F0 = 0 ≡ F5k (mod 5k + 1).

Let us assume for an integer m ∈ [0, 5k − 1], we have F5ki ≡ (−1)i+1Fi (mod 5k + 1) with i = 0, 1, …, m. Then, using the recurrence relation of the Fibonacci sequence, we have (0 ≤ m ≤ 5k − 1),

F5k-m-1=F5k-m+1-F5k-m(-1)mFm-1-(-1)m+1Fm         (mod5k+1)(-1)m(Fm-1+Fm)(-1)mFm+1         (mod 5k+1)(-1)m+2Fm+1         (mod 5k+1)

since (−1)2 = 1. It achieves the proof of Property 4.20 by induction on the integer m.

Remark 4.21

Property 4.20 implies that we can limit ourself to the integer interval [1, 5k2] (knowing that the case m = 0 is a trivial case) in order to search or to rule out a value for a possible period of the Fibonacci sequence modulo 5k + 1 with 5k+1 prime (such that k is a non-zero even positive integer) which is less than 5k. Notice that 5k is not in general the minimal period of the Fibonacci sequence modulo 5k + 1 with 5k + 1 prime (such that k is a non-zero even positive integer).

Indeed, for instance, if 5k + 1 = 101 (and so for k = 20), then it can be shown by calculating the residue of Fm with m ∈ [1, 50] modulo 5k + 1 = 101, that the minimal period is 5k2=50. Notice that in some cases as for instance k = 56, 84, the number k is the minimal period of the Fibonacci sequence modulo 5k + 1 with 5k + 1 prime.

Theorem 4.22

Let 5k + 1 be a prime with k a non-zero even positive integer. If k ≡ 0 (mod 4), then F5k20         (mod 5k+1).

Proof

If k is a non-zero positive integer such that k ≡ 0 (mod 4), then the integer 5k2 is a non-zero even positive integer. Using Property 4.20 and taking m=5k2, we have F5k2-F5k2         (mod 5k+1),

and

2F5k20         (mod 5k+1).

Since 2 and 5k + 1 with 5k + 1 prime are relatively prime, we get

F5k20         (mod 5k+1).

Remark 4.23

We can observe that

F5k-1=F5k+1-F5k1-5k3F4         (mod 5k+2),F5k-2=F5k-F5k-15k-35k-F4         (mod 5k+2),

and

F5k-3=F5k-1-F5k-26-5k8F6         (mod 5k+2),F5k-4=F5k-2-F5k-35k-115k-(F4+F6)         (mod 5k+2).

Using induction we can show the following two properties.

Property 4.24

Let 5k + 2 be a prime with k odd. Then, we have

F5k-(2l+1)F2(l+2)         (mod 5k+2)

with l a positive integer such that l5k-12.

Property 4.25

Let 5k + 2 be a prime with k odd. Then, we have

F5k-2l5k-i=0l-1F2(i+2)         (mod 5k+2)

with l ≥ 1 such that l5k2.

Remark 4.26

We can notice that

F5k+4=F5k+3+F5k+2F5k+25k+1         (mod 5k+2),F5k+5=F5k+4+F5k+3F5k+45k+1         (mod 5k+2),

and

F5k+6=F5k+5+F5k+410k+25k         (mod 5k+2).

And for l ≥ 1 we have

F5k+3l+2=F3l+2F5k+1+F3l+1F5kF3l+2+5kF3l+1         (mod 5k+2)F3l+(5k+1)F3l+1F3l-F3l+1+(5k+2)F3l+1         (mod 5k+2)F3l-F3l+1-F3l-1         (mod 5k+2).

Furthermore, we have for l ≥ 1

F5k+3l+1=F3l+1F5k+1+F3lF5kF3l+1+5kF3l         (mod 5k+2)F3l-1+(5k+1)F3lF3l-1-F3l+(5k+2)F3l         (mod 5k+2)F3l-1-F3l-F3l-2         (mod 5k+2).

Besides, we have for l ≥ 1

F5k+3l=F3lF5k+1+F3l-1F5kF3l+5kF3l-1         (mod 5k+2)F3l-2+(5k+1)F3l-1F3l-2-F3l-1+(5k+2)F3l-1         (mod 5k+2)F3l-2-F3l-1-F3l-3         (mod 5k+2).

We can state the following property, the proof of which follows from the above remark and by using induction.

Property 4.27

F5k+n ≡ −Fn3 (mod 5k + 2).

Theorem 4.28

Let 5k + 2 be a prime with k an odd positive number and let n a positive integer. Then, we have

Fn(5k+3)0         (mod 5k+2).
Proof

The proof of the theorem will be done by induction. We have F0 ≡ 0 (mod 5k + 2). Moreover, we know that

F5k+30         (mod 5k+2).

Let us assume that

Fn(5k+3)0         (mod 5k+2).

We have

F(n+1)(5k+3)=Fn(5k+3)+5k+3=F5k+3Fn(5k+3)+1+F5k+2Fn(5k+3).

Since F5k+3 ≡ 0 (mod 5k + 2), using (4.2), we deduce that

F(n+1)(5k+3)0         (mod 5k+2).

The following follows very easily from the above theorem.

Corollary 4.28

If 5k + 3|m, then Fm ≡ 0 (mod 5k + 2).

Property 4.30

Let 5k + 2 be a prime with k an odd positive integer. Then, for all m ∈ [[0, 5k]]

F5k-m(-1)m+1Fm+3         (mod 5k+2).
Proof

Let us prove Property 4.30 by induction on the integer m. From Properties 3.1 and 3.3, we have

F5k+2-1         (mod 5k+2),

and

F5k+11         (mod 5k+2).

Using the recurrence relation of the Fibonacci sequence, it comes that

F5k-2         (mod 5k+2),

and

F5k-13         (mod 5k+2).

So, we verify (4.3) is true when m = 0 and m = 1.

Notice that (4.3) is verified when m = 5k since F0 = 0 ≡ 0 (mod 5k + 2) and F5k+3 ≡ 0 (mod 5k + 2).

Let assume for an integer m ∈ [[0, 5k − 1]], we have F5ki ≡ (−1)i+1Fi+3 (mod 5k + 2) with i = 0, 1, …, m. Then, using the recurrence relation of the Fibonacci sequence, we have (0 ≤ m ≤ 5k − 1)

F5k-m-1=F5k-m+1-F5k-m(-1)mFm+2-(-1)m+1Fm+3         (mod 5k+2)(-1)m(Fm+2+Fm+3)(-1)m+2Fm+4         (mod 5k+2)(-1)m+2Fm+4         (mod 5k+2)

since (−1)2 = 1. It achieves the proof of Property 4.30 by induction on the integer m.

Notice that Property 4.30 is also true for m = −2,−1.

Remark 4.31

In general, the number 2(5k + 3) is not the minimal period of the Fibonacci sequence modulo 5k + 2 with 5k + 2 prime such that k an odd positive integer. Indeed, if k ≡ 0 (mod 3), then in some cases as for instance k=9,21,69,111,135,195,219, it can be verified that the numbers 2(5k+3)3 and 4(5k+3)3 are periods of the Fibonacci sequence modulo 5k + 2 with 5k + 2 prime.

Theorem 4.32

Let 5k + 2 be a prime number with k an odd positive number. If k ≡ 3 (mod 4), then F5k+320         (mod 5k+2).

Proof

Since 5k + 2 with k an odd positive number, is prime, the numbers 5k ± 3 are non-zero even positive integers. So, the numbers 5k±32 are non-zero positive integers. Moreover, if k ≡ 3 (mod 4), then 5k − 3 ≡ 12 ≡ 0 (mod 4). So, the integer 5k-32 is even.

Using Property 4.30 and taking m=5k-32, we have

F5k+32-F5k+32         (mod 5k+2),

or,

2F5k+320         (mod 5k+2).

Finally,

F5k+320         (mod 5k+2),

since 2 and 5k + 2 with 5k + 2 prime are relatively prime.

Theorem 4.33

Let 5k + 2 be a prime number with k an odd positive integer. If k ≡ 0 (mod 3) and if the number 2(5k+3)3 is a period of the Fibonacci sequence modulo 5k + 2, then the congruence

F5k+30         (mod 5k+2)

is equivalent to the congruence

F5k+330         (mod 5k+2)

which is equivalent to the congruence

F2(5k+3)30         (mod 5k+2).

Moreover, if k ≡ 0 (mod 3) and if

F5k+330         (mod 5k+2),

the number 2(5k+3)3 is a period of the Fibonacci sequence modulo 5k +2 if and only if

F5k3-1         (mod 5k+2).
Proof

If k ≡ 0 (mod 3) and k an odd positive integer, then there exists a non-zero positive integer m such that k = 3m. Notice that m is odd since k is odd. Since F5k+3 ≡ 0 (mod 5k+2) with 5k+2 prime (k positive odd), we have also F15m+3 ≡ 0 (mod 15m+2) with 15m+2 prime (m positive odd). Using Theorem 1.27, we have

F15m+3=F10m+2+5m+1=F5m+1F10m+3+F5mF10m+2.

Or, from Remark 4.6, we have

F10m+2=F2(5m+1)=F5m+1(F5m+F5m+2)=F5m+22-F5m2,

and

F10m+3=F2(5m+1)+1=F5m+12+F5m+22.

We have also

F10m+1=F5m+5m+1=F5m+12+F5m2.

So

F15m+3=F5m+1(F5m+12+F5m+22)+F5mF5m+1(F5m+F5m+2)=F5m+1(F5m+12+F5m+22+F5m2+F5mF5m+2)=F5m+1(3F5m2+3F5mF5m+1+2F5m+12)=F5m+1(3F5mF5m+2+2F5m+12).

So, the congruence F15m+3 ≡ 0 (mod 15m+2) with m an odd positive integer such that 15m + 2 prime is satisfied if and only if either

F5m+10         (mod 15m+2),

or

3F5mF5m+2-2F5m+12         (mod 15m+2).

If F5m+1 ≡ 0 (mod 15m + 2), then from above, we have necessarily

F10m+20         (mod 15m+2).

Using the recurrence relation of the Fibonacci sequence, it implies also that F5mF5m+2 (mod 15m + 2). Moreover, we have

F10m+3F5m+22F5m2         (mod 15m+2).

Or, we have

F15m+2=F10m+2+5m=F5mF10m+3+F5m-1F10m+2.

Since F5k+2 ≡ 5k + 1 ≡ −1 (mod 5k + 2) with 5k + 2 prime (k positive odd) and so if k = 3m such that m positive odd,

F15m+2-1         (mod 15m+2)

with 15m + 2 prime (m positive odd), since

F10m+3F5m2         (mod 15m+2)

and

F10m+20         (mod 15m+2),

it implies that

F5mF10m+3F5m3-1         (mod 15m+2).

We get

F5m3+10         (mod 15m+2),

and

(F5m+1)(F5m2-F5m+1)0         (mod 15m+2).

So, either

F5m+10         (mod 15m+2)

or

F5m2-F5m+10         (mod 15m+2).

If F5m+1 ≡ 0 (mod 15m + 2) and if F5m + 1 ≡ 0 (mod 15m + 2) and so

F5m-1         (mod 15m+2),

then

F10m+31         (mod 15m+2),

It results that the number 10m + 2 is a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime and m an odd positive integer.

If F5m+1 ≡ 0 (mod 15m+ 2) and if F5m2-F5m+10         (mod 15m+2) and so

F5m2F5m-1         (mod 15m+2),

then since F10m+3F5m2         (mod 15m+2),

F10m+3F5m-1         (mod 15m+2).

Notice that in this case, we cannot have

F5m-1         (mod 15m+2)

since 3 ≢ 0 (mod 15m+2) with m an odd positive integer such that 15m+2 prime (and so 15m + 2 > 3). Then, let assume absurdly that if

F5m2-F5m+10         (mod 15m+2),

then the number 10m + 2 is a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime and m an odd positive integer. In such a case,

F10m+31         (mod 15m+2)

which implies that

F5m2         (mod 15m+2).

Since F5m2F5m-1         (mod 15m+2), it gives

41         (mod 15m+2).

But, since 15m+2 is a prime number such that m is an odd positive integer, we have 15m+2 > 4 and so 4 ≢ 1 (mod 15m+2). So, we reach to a contradiction meaning that if F5m2-F5m+10         (mod 15m+2) and so if F5m ≢ −1 (mod 15m+2), the number 10m + 2 is not a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime and m an odd positive integer.

Moreover, if F5m+1 ≡ 0 (mod 15m+2) and reciprocally if the number 10m+2 is a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime and m an odd positive integer, then

F10m+31         (mod 15m+2)

which implies that

F5m21         (mod 15m+2).

So, either

F5m1         (mod 15m+2)

or

F5m-1         (mod 15m+2).

Since we have (4.4), it remains only one possibility, that is to say

F5m-1         (mod 15m+2).

2(5k+3)3=10m+2 is a period of the Fibonacci sequence, we must have F10m+3F5m21         (mod 15m+2) in addition to the condition

F5m+10         (mod 15m+2).

If 3F5mF5m+2-2F5m+12         (mod 15m+2), then from Property 1.3, we can find an integer c such that

{F5mF5m+2-2c         (mod 15m+2),F5m+123c         (mod 15m+2).

So

cF5m+12+F5mF5m+2         (mod 15m+2),

or equivalently (F5m+2 = F5m+1 + F5m and F10m+1=F5m+12+F5m2)

cF5m+12+F5m+1F5m+F5m2         (mod 15m+2),F10m+1+F5m+1F5m         (mod 15m+2).

So, if the number 10m+2 with m an odd positive integer is a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime, we should have

F10m+20         (mod 15m+2)

and

F10m+1F10m+31         (mod 15m+2).

Since F10m+2=F5m+22-F5m2 and c F10m+1 + F5m+1F5m (mod 15m + 2), it implies that

F5m2F5m+22         (mod 15m+2)

and

c1+F5mF5m+1         (mod 15m+2).

So, either

F5mF5m+2         (mod 15m+2)

or

F5m-F5m+2         (mod 15m+2).

If F5mF5m+2 (mod 15m + 2), then

F5m+10         (mod 15m+2)

and

c10         (mod 15m+2)

where we used the fact that

3cF5m+12         (mod 15m+2)

and (3, 15m+2) = 1 with 15m+2 prime. But, 1 ≢ 0 (mod 15m+2). So, we reach a contradiction meaning that this case is not possible. Otherwise, if

F5m-F5m+2         (mod 15m+2),

then using the recurrence relation of the Fibonacci sequence, we must have

F5m+1-2F5m         (mod 15m+2)

and so

c1-2F5m23F5m2         (mod 15m+2)

where we used the fact that

cF5m+12+F5mF5m+2         (mod 15m+2).

It implies that

5F5m21         (mod 15m+2)

and using Theorem 1.5, it gives

F5m2515m6m+1         (mod 15m+2)

since 515m+1 ≡ 1 ≡ 30m + 5 (mod 15m + 2) which implies that 515m ≡ 6m + 1 (mod 15m + 2) (reccall that 15m + 2 is prime and so (5, 15m + 2) = 1). Since

F5m+1-2F5m         (mod 15m+2),F5m+123c         (mod 15m+2)

and

c3F5m2         (mod 15m+2),

it results that

F5m+124F5m23c9F5m2         (mod 15m+2)

and so 4(6m + 1) ≡ 9(6m + 1) (mod 15m + 2). Since 4(6m + 1) = 24m + 4 ≡ 9m + 2 (mod 15m + 2), it implies that 45m + 7 ≡ 0 (mod 15m + 2) and so 1 ≡ 0 (mod 15m + 2) which is not possible since 1 ≢ 0 (mod 15m + 2). So, we obtain again a contradiction meaning that this latter case is not also possible.

Therefore, when 5k+2 = 15m+2 is prime with k = 3m and m an odd positive integer, if 10m + 2 is a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime, then

F15m+30         (mod 15m+2)

if and only if

F5m+10         (mod 15m+2).

Since F15m+3 = F5k+3 ≡ 0 (mod 5k+2) is true when 5k + 2 is prime, we deduce that

F5k+320         (mod 5k+2)

is also true when k ≡ 0 (mod 3) and 5k + 2 prime.

Thus, if 10m + 2 is a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime, then we have

F15m+30         (mod 15m+2)

if and only if

F5m+10         (mod 15m+2)

if and only if

F5mF5m+2         (mod 15m+2).

Besides,

F5m+10         (mod 15m+2)

implies that

F10m+20         (mod 15m+2).

Reciprocally, if F10m+2 ≡ 0 (mod 15m + 2), then

F5m2F5m+22         (mod 15m+2).

So, either

F5mF5m+2         (mod 15m+2)

or

F5m-F5m+2         (mod 15m+2).

If F5m ≡ −F5m+2 (mod 15m + 2), then

F5m+1-2F5m         (mod 15m+2)

and since F5m+1 ≡ 0 (mod 15m + 2), using the fact that (2, 15m + 2) = 1 with 15m + 2 prime such that m an odd positive integer (15m + 2 > 2),

F5m0         (mod 15m+2).

But, then, if F10m+2 ≡ 0 (mod 15m + 2), we have

F15m+2F10m+3F5m0         (mod 15m+2).

Or,

F15m+2-1         (mod 15m+2).

It leads to a contradiction meaning that

F5m-F5m+2         (mod 15m+2)

is not possible. So, if F10m+2 ≡ 0 (mod 15m+2), there is only one possibility, that is to say

F5mF5m+2         (mod 15m+2)

which implies the congruence

F5m+10         (mod 15m+2)

and so which translates the congruence

F15m+2-1         (mod 15m+2)

into the congruence

F5m3-1         (mod 15m+2)

which has at least one solution. So, if 10m+2 is a period of the Fibonacci sequence modulo 15m + 2 with 15m + 2 prime, then we have

F15m+30         (mod 15m+2)

if and only if

F5m+10         (mod 15m+2)

if and only if

F5mF5m+2         (mod 15m+2).

if and only if

F10m+20         (mod 15m+2).

Since 10m+2=2(5m+1)=2(5k+3)3 with k = 3m and m an odd positive integer, from above, we conclude that the number 2(5k+3)3 is a period of the Fibonacci sequence modulo 5k + 2 if and only if

F5k3-1         (mod 5k+2).

Property 4.34

Let 5k + 3 be a prime with k an even positive integer. Then, for all m ∈ [[0, 5k]]

F5k-m(-1)mFm+4         (mod 5k+3).
Proof

Let us prove Property 4.34 by induction on the integer m.

From Properties 3.1 and 3.3, we have

F5k+3-1         (mod 5k+3),

and

F5k+21         (mod 5k+3).

Using the recurrence relation of the Fibonacci sequence, it comes that

F5k+1-2         (mod 5k+3),F5k3         (mod 5k+3),

and

F5k-1-5         (mod 5k+3).

So, we verify (4.5) is true when m = 0 and m = 1.

Notice that (4.5) is verified when m = 5k since F0 = 0 ≡ 0 (mod 5k + 3) and F5k+4 ≡ 0 (mod 5k + 3).

Let us assume for an integer m ∈ [[0, 5k − 1]], we have F5ki ≡ (−1)iFi+4 (mod 5k + 3) with i = 0, 1, …, m. Then, using the recurrence relation of the Fibonacci sequence, we have (0 ≤ m ≤ 5k − 1)

F5k-m-1=F5k-m+1-F5k-m(-1)m-1Fm+3-(-1)mFm+4         (mod 5k+3)(-1)m-1(Fm+3+Fm+4)(-1)2(-1)m-1Fm+5         (mod 5k+3)(-1)m+1Fm+5         (mod 5k+3)

since (−1)2 = 1. It achieves the proof of Property 4.34 by induction on the integer m.

Notice that Property 4.34 is also true for m = −3,−2,−1.

Remark 4.35

It can be noticed that for k = 0, 5k + 3 = 3 is prime and it can be verified that 2(5k+4) = 8 for k = 0 is the minimal period of the Fibonacci sequence modulo 3. Nevertheless, in general, the number 2(5k+4) is not the minimal period of the Fibonacci sequence modulo 5k + 3 with 5k + 3 prime such that k an even positive integer. Indeed, if k ≡ 1 (mod 3) and k an even positive integer, then in some cases as for instance k = 22, 52, 70, 112, 148, 244, it can be verified that the numbers 2(5k+4)3 and 4(5k+4)3 are periods of the Fibonacci sequence modulo 5k + 3 with 5k + 3 prime.

Theorem 4.36

Let 5k + 3 be a prime number with k a non-zero even positive number. If k ≡ 2 (mod 4), then

F5k+420         (mod 5k+3).
Proof

Since 5k+3 with k a non-zero even positive number, is prime, the numbers 5k ± 4 are non-zero even positive integers. So, the numbers 5k±42 are non-zero positive integers. Moreover, if k ≡ 2 (mod 4), then 5k − 4 ≡ 2 (mod 4). So, the integer 5k-42 is odd.

Using Property 4.34 and taking m=5k-42, it gives

F5k+42-F5k+42         (mod 5k+3),

or,

2F5k+420         (mod 5k+3),

and finally,

F5k+420         (mod 5k+3),

since 2 and 5k + 3 with 5k + 3 prime are relatively prime.

Theorem 4.37

Let 5k + 3 be a prime number with k an even positive integer. If k ≡ 1 (mod 3) and if2(5k+4)3 is a period of the Fibonacci sequence modulo 5k + 3, the congruence

F5k+40         (mod 5k+3)

is equivalent to the congruence

F5k+430         (mod 5k+3)

which is equivalent to the congruence

F2(5k+4)30         (mod 5k+3)

Moreover, if k ≡ 1 (mod 3) and if F5k+430         (mod 5k+3), then the number 2(5k+4)3 is a period of the Fibonacci sequence modulo 5k + 3 if and only if

F5k+13-1         (mod 5k+3).
Proof

If k ≡ 1 (mod 3) and k an even positive integer, then there exists a non-zero positive integer m such that k = 3m+1. Notice that m is odd since k is even. Since

F5k+40         (mod 5k+3)

with 5k + 3 prime (k positive even), we have also

F15m+90         (mod 15m+8)

with 15m + 8 prime (m positive odd). Using Theorem 1.27, we have

F15m+9=F3(5m+3)=F2(5m+3)+5m+3=F5m+3F2(5m+3)+1+F5m+2F2(5m+3)=F5m+3F10m+7+F5m+2F10m+6.

Or, from Remark 4.6, we have

F10m+6=F2(5m+3)=F5m+3(F5m+4+F5m+2)=F5m+42-F5m+22,

and

F10m+7=F2(5m+3)+1=F5m+32+F5m+42.

We have also

F10m+5=F5m+2+5m+3=F5m+32+F5m+22.

So

F15m+9=F5m+3(F5m+32+F5m+42)+F5m+2F5m+3(F5m+4+F5m+2)=F5m+3(F5m+32+F5m+42+F5m+22+F5m+2F5m+4)=F5m+3(3F5m+22+3F5m+2F5m+3+2F5m+32)=F5m+3(3F5m+2F5m+4+2F5m+32).

So, the congruence

F15m+90         (mod 15m+8)

with m an odd positive integer such that 15m + 8 prime is satisfied if and only if either

F5m+30         (mod 15m+8),

or

3F5m+2F5m+4-2F5m+32         (mod 15m+8).

If F5m+3 ≡ 0 (mod 15m + 8), then from above, we have necessarily

F10m+60         (mod 15m+8).

Using the recurrence relation of the Fibonacci sequence, it implies also that

F5m+2F5m+4         (mod 15m+8).

Moreover, we have

F10m+7F5m+42F5m+22         (mod 15m+8).

Or we have,

F15m+8=F10m+6+5m+2=F5m+2F10m+7+F5m+1F10m+6.

Since F5k+3 ≡ 5k + 2 ≡ −1 (mod 5k + 3) with 5k + 3 prime (k positive even) and so if k = 3m + 1 such that m positive odd,

F15m+8-1         (mod 15m+8)

with 15m + 8 prime (m positive odd), since F10m+7F5m+22         (mod 15m+8) and F10m+6 ≡ 0 (mod 15m + 8), it implies that

F5m+2F10m+7F5m+23-1         (mod 15m+8).

It comes that

F5m+23+10         (mod 15m+8),

or,

(F5m+2+1)(F5m+22-F5m+2+1)0         (mod 15m+8).

So, either

F5m+2+10         (mod 15m+8),

or

F5m+22-F5m+2+10         (mod 15m+8).

If F5m+3 ≡ 0 (mod 15m + 8) and if F5m+2 + 1 ≡ 0 (mod 15m + 8) and so

F5m+2-1         (mod 15m+8),

then

F10m+71         (mod 15m+8).

It results that the number 10m + 6 is a period of the Fibonacci sequence modulo 15m + 8 with 15m + 8 prime and m an odd positive integer.

If F5m+3 ≡ 0 (mod 15m+8) and if F5m+22-F5m+2+10         (mod 15m+8) and so

F5m+22F5m+2-1         (mod 15m+8),

then since F10m+7F5m+22         (mod 15m+8),

F10m+7F5m+2-1         (mod 15m+8).

Notice that in this case, we cannot have

F5m+2-1         (mod 15m+8)

since 3 ≢ 0 (mod 15m+8) with m an odd positive integer such that 15m+8 prime (and so 15m+8 > 3). Then, let us assume absurdly that if F5m+22-F5m+2+10         (mod 15m+8), then the number 10m + 6 is a period of the Fibonacci sequence modulo 15m+8 with 15m+8 prime and m an odd positive integer. In such a case,

F10m+71         (mod 15m+8)

which implies that

F5m+22         (mod 15m+8).

Since F5m+22F5m+2-1         (mod 15m+8), it gives 4 ≡ 1 (mod 15m + 8). But, since 15m + 8 is a prime number such that m is an odd positive integer, we have 15m+8 > 4 and so 4 ≢ 1 (mod 15m+8). So, we reach to a contradiction meaning that if F5m+22-F5m+2+10         (mod 15m+8) and so if F5m+2 ≢ −1 (mod 15m+8), the number 10m+6 is not a period of the Fibonacci sequence modulo 15m+8 with 15m + 8 prime and m an odd positive integer.

Moreover, if F5m+3 ≡ 0 (mod 15m+8) and reciprocally if the number 10m+6 is a period of the Fibonacci sequence modulo 15m + 8 with 15m + 8 prime and m an odd positive integer, then

F10m+71         (mod 15m+8)

which implies that F5m+221         (mod 15m+8).

So, either

F5m+21         (mod 15m+8)

or

F5m+2-1         (mod 15m+8).

Since we have also F5m+23-1         (mod 15m+8)

(see above), it remains only one possibility, that is to say

F5m+2-1         (mod 15m+8).

2(5k+4)3=10m+6 is a period of the Fibonacci sequence, we must have

F10m+7F5m+221         (mod 15m+8)

in addition to the condition

F5m+30         (mod 15m+8).

If 3F5m+2F5m+4-2F5m+32         (mod 15m+8), then from Property 1.3, we can find an integer c such that

{F5m+2F5m+4-2c         (mod 15m+8),F5m+323c         (mod 15m+8)

So

cF5m+32+F5m+2F5m+4         (mod 15m+8),

or equivalently (F5m+4 = F5m+3 + F5m+2 and F10m+5=F5m+32+F5m+22)

cF5m+32+F5m+3F5m+2+F5m+22         (mod 15m+8)F10m+5+F5m+3F5m+2         (mod 15m+8).

So, if the number 10m+6 with m an odd positive integer is a period of the Fibonacci sequence modulo 15m + 8 with 15m + 8 prime, we should have

F10m+60         (mod 15m+8)

and

F10m+5F10m+71         (mod 15m+8).

Since F10m+6=F5m+42-F5m+22 and from the relations F10m+6 ≡ 0 (mod 15m+8) and F10m+6=F5m+42-F5m+22, we have

F5m+22F5m+42         (mod 15m+8)

and

c1+F5m+2F5m+3         (mod 15m+8).

So, either

F5m+2F5m+4         (mod 15m+8)

or

F5m+2-F5m+4         (mod 15m+8).

If F5m+2F5m+4 (mod 15m + 8), then

F5m+30         (mod 15m+8)

and

c10         (mod 15m+8)

where we used the fact that

3cF5m+32         (mod 15m+8)

and (3, 15m+8) = 1 with 15m+8 prime. But, 1 ≢ 0 (mod 15m+8). So, we reach a contradiction meaning that this case is not possible. Otherwise, if

F5m+2-F5m+4         (mod 15m+8),

then using the recurrence relation of the Fibonacci sequence, we must have

F5m+3-2F5m+2         (mod 15m+8)

and so

c1-2F5m+223F5m+22         (mod 15m+8)

where we used (4.6). It implies that

5F5m+221         (mod 15m+8)

and using Theorem 1.5, it gives

F5m+22515m+69m+5         (mod 15m+8)

since 515m+7 ≡ 1 ≡ 45m + 25 (mod 15m + 8) which implies that 515m+6 ≡ 9m + 5 (mod 15m + 8) (recall that 15m + 8 is prime and so (5, 15m + 8) = 1). Since F5m+3 ≡ −2F5m+2 (mod 15m + 8), F5m+323c         (mod 15m+8) and c3F5m+22         (mod 15m+8), it results that

F5m+324F5m+223c9F5m+22         (mod 15m+8)

and so 4(9m + 5) ≡ 9(9m + 5) (mod 15m + 8). Since 4(9m + 5) = 36m + 20 ≡ 6m+ 4 (mod 15m+ 8), it implies that 75m+ 41 ≡ 0 (mod 15m+ 8) and so 1 ≡ 0 (mod 15m + 8) which is not possible since 1 ≢ 0 (mod 15m + 2). So, we obtain again a contradiction meaning that this latter case is not also possible.

Therefore, when 5k + 3 = 15m + 8 is prime with k = 3m + 1 and m an odd positive integer, if 10m + 6 is a period of the Fibonacci sequence modulo 15m + 8 with 15m + 8 prime,

F15m+90         (mod 15m+8)

if and only if

F5m+30         (mod 15m+8).

Since F15m+9 = F5k+4 ≡ 0 (mod 5k+3) is true when 5k + 3 is prime, we deduce that

F5k+430         (mod 5k+3)

is also true when k ≡ 1 (mod 3) and 5k + 3 prime.

Thus, if 10m + 6 is a period of the Fibonacci sequence modulo 15m + 8 with 15m + 8 prime, then we have

F15m+90         (mod 15m+8)

if and only if

F5m+30         (mod 15m+8)

if and only if

F5m+2F5m+4         (mod 15m+8).

Besides,

F5m+30         (mod 15m+8)

implies that

F10m+60         (mod 15m+8).

Reciprocally, if F10m+6 ≡ 0 (mod 15m + 8), then

F5m+22F5m+42         (mod 15m+8).

So, either

F5m+2F5m+4         (mod 15m+8)

or

F5m+2-F5m+4         (mod 15m+8).

If F5m+2 ≡ −F5m+4 (mod 15m + 8), then

F5m+3-2F5m+2         (mod 15m+8)

and since F5m+3 ≡ 0 (mod 15m + 8), using the fact that (2, 15m + 8) = 1 with 15m + 8 prime such that m an odd positive integer (15m + 8 > 2),

F5m+20         (mod 15m+8).

But, then, if F10m+6 ≡ 0 (mod 15m + 8), we have

F15m+8F10m+7F5m+20         (mod 15m+8).

Or,

F15m+8-1         (mod 15m+8).

It leads to a contradiction meaning that

F5m+2-F5m+4         (mod 15m+8)

is not possible. So, if F10m+6 ≡ 0 (mod 15m+8), there is only one possibility, that is to say

F5m+2F5m+4         (mod 15m+8)

which implies the congruence

F5m+30         (mod 15m+8)

and so which translates the congruence

F15m+8-1         (mod 15m+8)

into the congruence

F5m+23-1         (mod 15m+8)

which has at least one solution. So, if 10m+6 is a period of the Fibonacci sequence modulo 15m + 8 with 15m + 8 prime, then we have

F15m+90         (mod 15m+8)

if and only if

F5m+30         (mod 15m+8)

if and only if

F5m+2F5m+4         (mod 15m+8)

if and only if

F10m+60         (mod 15m+8).

Since 10m+6=2(5m+3)=2(5k+4)3 with k = 3m + 1 and m an odd positive integer, from above, we conclude that the number 2(5k+4)3 is a period of the Fibonacci sequence modulo 5k + 3 if and only if F5k+13-1      (mod 5k+3).

Property 4.38

Let 5k + 4 be a prime with k an odd positive integer. Then, for all m ∈ [[0, 5k]]

F5k-m(-1)mFm+3         (mod 5k+4).
Proof

From Properties 3.3 and 3.4, we have

F5k+30         (mod 5k+4),

and

F5k+21         (mod 5k+4).

Then, using the recurrence relation of the Fibonacci sequence, it comes that

F5k+1-1         (mod 5k+4),F5k2         (mod 5k+4),

and

F5k-1-3         (mod 5k+4).

So, we verify (4.8) is true when m = 0 and m = 1.

Notice that (4.8) is verified when m = 5k since F0 = 0 ≡ 0 (mod 5k + 4) and F5k+3 ≡ 0 (mod 5k + 4).

Let assume for an integer m ∈ [[0, 5k − 1]], we have F5ki ≡ (−1)iFi+3 (mod 5k + 4) with i = 0, 1, …, m. Then, using the recurrence relation of the Fibonacci sequence, we have (0 ≤ m ≤ 5k − 1),

F5k-m-1=F5k-m+1-F5k-m(-1)m-1Fm+2-(-1)mFm+3         (mod 5k+4)(-1)m-1(Fm+2+Fm+3)(-1)m-1Fm+4         (mod 5k+4)(-1)2(-1)m-1Fm+4(-1)m-1Fm+4         (mod 5k+4)

since (−1)2 = 1. It achieves the proof of Property 4.38 by induction on the integer m.

Notice that Property 4.38 is also true for m = −2,−1.

Remark 4.39

Property 4.38 implies that we can limit ourself to the integer interval [1, 5k+32] (knowing that the case m = 0 is a trivial case) in order to search or to rule out a value for a possible period of the Fibonacci sequence modulo 5k+4 with 5k+4 prime (such that k is an odd positive integer) which is less than 5k+3. Notice that 5k + 3 is not in general the minimal period of the Fibonacci sequence modulo 5k + 4 with 5k + 4 prime (such that k is an odd positive integer). Indeed, for instance, if 5k+4 = 29 (and so for k = 5), then it can be shown by calculating the residue of Fm with m ∈ [1, 14] modulo 5k + 4 = 29, that the minimal period is 5k+32=14.

Theorem 4.40

Let 5k + 4 be a prime number with k an odd positive number. If k ≡ 1 (mod 4), then

F5k+320         (mod 5k+4).
Proof

Since 5k + 4 with k an odd positive number, is prime, the numbers 5k ± 3 are non-zero even positive integers. So, the numbers 5k±32 are non-zero positive integers. Moreover, if k ≡ 1 (mod 4), then 5k − 3 ≡ 2 (mod 4). So, the integer 5k-32 is odd.

Using Property 4.38 and taking m=5k-32, it gives

F5k+32-F5k+32         (mod 5k+2),

or,

2F5k+320         (mod 5k+2),

finally,

F5k+320         (mod 5k+2)

since 2 and 5k + 4 with 5k + 4 prime are relatively prime.

Theorem 4.41

Let 5k + 1 be a prime with k a non-zero positive even integer. If k ≡ 0 (mod 3) and if 10k3is a period of the Fibonacci sequence modulo 5k +1, then the congruence

F5k0         (mod 5k+1)

is equivalent to the congruence

F5k30         (mod 5k+1)

which is equivalent to the congruence

F10k30         (mod 5k+1).

Moreover, if k ≡ 0 (mod 3) and if F5k30         (mod 5k+1), then the number 10k3 is a period of the Fibonacci sequence modulo 5k + 1 if and only if

F5k±331         (mod 5k+1).
Proof

If k ≡ 0 (mod 3) and k a non-zero positive even integer, then there exists a non-zero positive integer m such that k = 3m. Notice that m is even since k is even. Since F5k ≡ 0 (mod 5k+1) with 5k+1 prime (k positive even), we have also F15m ≡ 0 (mod 15m + 1) with 15m + 1 prime (m positive even). Using Theorem 1.27, we have

F15m=F10m+5m=F5mF10m+1+F5m-1F10m,F10m-1=F5m-1+5m=F5m2+F5m-12.

From Remark 4.6, we have

F10m=F2×5m=F5m(F5m+1+F5m-1)=F5m+12-F5m-12,F10m+1=F2×5m+1=F5m+12+F5m2.

So

F15m=F5m(F5m+12+F5m2)+F5m-1F5m(F5m+1+F5m-1)=F5m(F5m+12+F5m2+F5m-1F5m+1+F5m-12)=F5m(3F5m-12+3F5m-1F5m+2F5m2)=F5m(3F5m-1F5m+1+2F5m2).

So, the congruence F15m ≡ 0 (mod 15m + 1) with m an even positive integer such that 15m + 1 prime is satisfied if and only if either

F5m0         (mod 15m+1)

or

3F5m-1F5m+1-2F5m2         (mod 15m+1).

If F5m ≡ 0 (mod 15m + 1), then from above, we have necessarily

F10m0         (mod 15m+1).

Using the recurrence relation of the Fibonacci sequence, it implies also that F5m+1F5m1 (mod 15m + 1). Moreover, we have

F10m+1F5m+12F5m-12         (mod 15m+1).

Or, using Theorem 1.27, we have

F15m+1=F5m+10m+1=F10m+1F5m+1+F10mF5m.

Since F5k+1 ≡ 1 (mod 5k +1) with 5k +1 prime (k non-zero positive even) and so if k = 3m such that m non-zero positive even,

F15m+11         (mod 15m+1)

with 15m + 1 prime (m non-zero positive even), since

F10m+1F5m+12         (mod 15m+1)

and

F10m0         (mod 15m+1)

it implies that

F10m+1F5m+1F5m+131         (mod 15m+1).

We get

F5m+13-10         (mod 15m+1)

and

(F5m+1-1)(F5m+12+F5m+1+1)0         (mod 15m+1).

So, either

F5m+1-10         (mod 15m+1)

or

F5m+12+F5m+1+10         (mod 15m+1).

If F5m ≡ 0 (mod 15m + 1) and if F5m+1 − 1 ≡ 0 (mod 15m + 1) and so

F5m+11         (mod 15m+1),

then

F10m+11         (mod 15m+1).

It results that the number 10m is a period of the Fibonacci sequence modulo 15m+1 with 15m+1 prime and m a non-zero positive even integer. If F5m ≡ 0 (mod 15m+ 1) and if F5m+12+F5m+1+10         (mod 15m+1) and so

F5m+12-F5m+1-1         (mod 15m+1)

then since

F10m+1F5m+12         (mod 15m+1)-F5m+1-1         (mod 15m+1).

Notice that in this case, we cannot have

F5m+11         (mod 15m+1)

since 3 ≢ 0 (mod 15m+2) with m a non-zero positive even integer such that 15m+1 prime (and so 15m+1 > 3). Then, let us assume absurdly that if F5m+12+F5m+1+10         (mod 15m+1) then the number 10m is a period of the Fibonacci sequence modulo 15m + 1 with 15m + 1 prime and m a non-zero positive even integer. In such a case,

F10m+11         (mod 15m+1)

which implies that

F5m+1-2         (mod 15m+1).

Since F5m+12-F5m+1-1         (mod 15m+1) it gives

41         (mod 15m+1).

But, since 15m + 1 is a prime number such that m is a non-zero positive even integer, we have 15m + 1 > 4 and so 4 ≢ 1 (mod 15m + 1). So, we reach a contradiction meaning that if F5m+12+F5m+1+10         (mod 15m+1) and so if F5m+1 ≢ 1 (mod 15m + 1) then the number 10m is not a period of the Fibonacci sequence modulo 15m + 1 with 15m + 1 prime and m a non-zero positive even integer. Moreover, if F5m ≡ 0 (mod 15m + 1) and reciprocally if the number 10m is a period of the Fibonacci sequence modulo 15m + 1 with 15m + 1 prime and m a non-zero positive even integer, then

F10m+11         (mod 15m+1)

which implies that

F5m+121         (mod 15m+1).

So, either

F5m+11         (mod 15m+1)

or

F5m+1-1         (mod 15m+1).

Since we have (4.9), it remains only one possibility, that is to say

F5m+11         (mod 15m+1)

10k3=10m is a period of the Fibonacci sequence modulo 15m + 1, we must have F10m+1F5m+121         (mod 15m+1) in addition to the condition

F5m0         (mod 15m+1).

If 3F5m-1F5m+1-2F5m2         (mod 15m+2) then from Property 1.3, we can find an integer c such that

{F5m-1F5m+1-2c         (mod 15m+1),F5m23c         (mod 15m+1),

or equivalently (F5m+1 = F5m + F5m1 and F10m-1=F5m2+F5m-12)

cF5m2+F5m-1F5m+1         (mod 15m+1)F5m2+F5m-1F5m+F5m-12F10m-1+F5m-1F5m         (mod 15m+1).

So, if the number 10m with m a non-zero positive even integer is a period of the Fibonacci sequence modulo 15m + 1 with 15m + 1 prime, we should have

F10m0         (mod 15m+1)

and

F10m-1F10m+11         (mod 15m+1).

Since F10m=F5m+12-F5m-12 and c F10m1+F5m1F5m (mod 15m+1) it implies that

F5m+12F5m-12         (mod 15m+1)

and

c1+F5m-1F5m         (mod 15m+1).

So, either

F5m+1F5m-1         (mod 15m+1)

or

F5m+1-F5m-1         (mod 15m+1).

If F5m+1F5m1 (mod 15m + 1) then

F5m0         (mod 15m+1)

and

c10         (mod 15m+1)

where we used the fact that

3cF5m2         (mod 15m+1)

and (3, 15m+1) = 1 with 15m+1 prime. But, 1 ≢ 0 (mod 15m+1). So, we reach a contradiction meaning that this case is not possible. Otherwise, if

F5m+1-F5m-1         (mod 15m+1)

then using the recurrence relation of the Fibonacci sequence, we must have

F5m-2F5m-1         (mod 15m+1)

and so

c1-2F5m-123F5m-12         (mod 15m+1)

where we used the fact that

cF5m2+F5m-1F5m+1         (mod 15m+1).

It implies that

5F5m-121         (mod 15m+1)

and using Theorem 1.5, it gives

F5m-12515m-112m+1         (mod 15m+1)

since 515m ≡ 1 ≡ 60m + 5 (mod 15m + 1) which implies that 515m1 ≡ 12m + 1 (mod 15m+1) (recall that 15m+1 is prime and so (5, 15m+1) = 1. Since F5m ≡ −2F5m1 (mod 15m+1), F5m23c         (mod 15m+1) and c3F5m-12         (mod 15m+1), it results that

F5m29F5m-123c4F5m-12         (mod 15m+1)

and so 4(12m + 1) ≡ 9(12m + 1) (mod 15m + 1). Since 4(12m + 1) = 48m + 4 ≡ 3m+ 1 (mod 15m+ 1), it implies that 105m+ 8 ≡ 0 (mod 15m+ 1) and so 1 ≡ 0 (mod 15m + 1) which is not possible since 1 ≢ 0 (mod 15m + 1)0. So, we obtain again a contradiction meaning that this latter case is not also possible.

Therefore, when 5k + 1 = 15m + 1 is prime with k = 3m and m a non-zero positive even integer, if 10m is a period of the Fibonacci sequence modulo 15m+1 with 15m + 1 prime, then

F15m0         (mod 15m+1)

if and only if

F5m0         (mod 15m+1).

Since F15m = F5k ≡ 0 (mod 5k+1) is true when 5k + 1 is prime, we deduce that

F5k30         (mod 5k+1)

is also true when k ≡ 0 (mod 3) and 5k + 1 prime.

Thus, if 10m is a period of the Fibonacci sequence modulo 15m+1 with 15m+1 prime, then we have

F15m0         (mod 15m+1)

if and only if

F5m0         (mod 15m+1)

if and only if

F5m-1F5m+1         (mod 15m+1).

Besides,

F5m0         (mod 15m+1)

implies that

F10m0         (mod 15m+1).

Reciprocally, if F10m ≡ 0 (mod 15m + 1) then

F5m+12F5m-12         (mod 15m+1).

So, either

F5m+1F5m-1         (mod 15m+1)

or

F5m+1-F5m-1         (mod 15m+1).

If F5m+1 ≡ −F5m1 (mod 15m + 1) then

F5m-2F5m-1         (mod 15m+1)

and since F5m ≡ 0 (mod 15m+1) using the fact that (2, 15m+1) = 1 with 15m+1 prime such that m is a non-zero positive even integer (15m + 1 > 2),

F5m-10         (mod 15m+1).

But, then, if F10m ≡ 0 (mod 15m + 1) we have

F15m+1F10m+1F5m+10         (mod 15m+1).

Or,

F15m+11         (mod 15m+1).

It leads to a contradiction meaning that

F5m+1-F5m-1         (mod 15m+1)

is not possible. So, if F10m ≡ 0 (mod 15m+ 1) there is only one possibility, that is to say

F5m+1F5m-1         (mod 15m+1)

which implies the congruence

F5m0         (mod 15m+1)

and so which translates the congruence

F15m+11         (mod 15m+1)

into the congruence

F5m+131         (mod 15m+1)

which has at least one solution. So, if 10m is a period of the Fibonacci sequence modulo 15m + 1 with 15m + 1 prime, then we have

F15m0         (mod 15m+1)

if and only if

F5m0         (mod 15m+1)

if and only if

F5m+1F5m-1         (mod 15m+1)

if and only if

F10m0         (mod 15m+1).

Since 10m=10k3 with k = 3m and m a non-zero positive even integer, from above, we conclude that if F5k30         (mod 5k+1), then 10k3 is a period of the Fibonacci sequence modulo 5k + 1 with 5k + 1 prime if and only if

F5k±331         (mod 5k+1).

Theorem 4.42

Let 5k + 4 be a prime with k an odd positive integer. If k ≡ 0 (mod 3) and if 2(5k+3)3is a period of the Fibonacci sequence modulo 5k + 4, then the congruence

F5k+30         (mod 5k+4)

is equivalent to the congruence

F5k+330         (mod 5k+4)

which is equivalent to the congruence

F2(5k+3)30         (mod 5k+4).

Moreover, if k ≡ 0 (mod 3) and if F5k+330         (mod 5k+4), then the number 2(5k+3)3 is a period of the Fibonacci sequence modulo 5k + 4 if and only if

F5k31         (mod 5k+4)
Proof

The proof is very similar to the proof of Theorem 4.33.

The next theorem below is a generalization of Theorems 4.33, 4.37 and Theorem 4.41 and 4.42 given above. The number 5k+r with 5k+r prime such that r ∈ [[1, 4]] and k r + 1 (mod 2) is a period of the Fibonacci sequence modulo 5k + r. Its expression is given in Corollary 4.10.

Theorem 4.43

Let 5k+r be a prime such that r ∈ [[1, 4]] and k r+1 (mod 2). If k(r-1)(r-2)2         (mod 3) and if 5k+r3 is a period of the Fibonacci sequence modulo 5k + r, then the congruence

F5k+r30         (mod 5k+r)

is equivalent to the congruence

F5k+r60         (mod 5k+r)

which is equivalent to the congruence

F5k+r30         (mod 5k+r).

Moreover, if k(r-1)(r-2)2         (mod 3) and if F5k+r60         (mod 5k+r), then the number 5k+r3 is a period of the Fibonacci sequence modulo 5k + r if and only if

F5k+r6-1{1         (mod 5k+r)ifr=1orr=4,-1         (mod 5k+r)ifr=2orr=3.
Proof

The results stated in Theorem 4.43 can be deduced from Theorems 4.33, 4.37 and Theorems 4.41 and 4.42 given above.

In this section, we deduce some small results related to the generalized fibonacci numbers as defined below.

Definition 5.1

Let a, b, r be three numbers. The sequence (Cn,2(a, b, r)) is defined by

Cn,2(a,b,r)=Cn-1,2(a,b,r)+Cn-2,2(a,b,r)+r,         n2

with

{C0,2(a,b,r)=b-a-r,C1,2(a,b,r)=a.

In particular, we have

Fn=Cn,2(1,1,0),         n0.

Remark 5.2

This sequence can be defined from n = 1 by setting C2,2(a, b, r) = b as in [1].

Proposition 5.3

Let a, b, r be three numbers. The sequences (Cn,2(a, b, r)), (Cn,2(1, 0,−1)), (Fn) satisfies

Cn,2(a,b,r)=aFn-2+bFn-1-rCn+1,2(1,0,-1),         n2.
Proof

Let a, b, r be three numbers. Let us prove Proposition 5.3 by induction on the integer n ≥ 2. We have

C2,2(a,b,r)=b=a×0+b×1+r×0=a×F0+b×F1-r×C3,2(1,0,-1)

Let us assume that this proposition is true up to n ≥ 2. Using the recurrence relations of sequences (Cn,2(a, b, r)), (Cn,2(1, 0,−1)) and (Fn), we have

Cn+1,2(a,b,r)=Cn,2(a,b,r)+Cn-1,2(a,b,r)+r=(aFn-2+bFn-1-rCn+1,2(1,0,-1))+(aFn-3+bFn-2-rCn,2(1,0,-1))+r=a(Fn-2+Fn-3)+b(Fn-1+Fn-2)-r(Cn+1,2(1,0,-1)+Cn,2(1,0,-1)-1)=aFn-1+bFn-rCn+2,2(1,0,-1).

Thus by induction, the proof is complete.

Proposition 5.4

The sequences (Cn,2(1, 0,−1)) and (Fn) satisfies

Cn,2(1,0,-1)=Cn-2,2(1,0,-1)-Fn-2,         n2.Cn,2(1,0,-1)=-k=1n-3Fk,         n4.

From Proposition 5.3, for any numbers a, b, r, it results that

Cn,2(a,b,r)=aFn-2+bFn-1+rk=1n-2Fk,         n2Cn,2(a,b,r)=aFn-2+bFn-1+r(Fn-1),         n2.

This result can be easily verifies using mathematical induction and Theorem 1.26 and Proposition 5.4. We shall omit the details here.

The theorem below appears in any standard linear algebra textbook.

Proposition 5.5. (i)

A linear recurrence sequence (un)n0of order 2 which satisfies a linear recurrence relation as

un=α1un-1+α2un-2,         n2

with α1, α2in a field K (K = ℝ or K = ℂ), is completely and uniquely determined by its first terms u0and u1.

(ii) If (un)n0, (vn)n0are two linear recurrence sequences of order 2 such that

det(u0v0u1v1)=u0v1-u1v00

then any linear recurrence sequence (wn)n0of order 2 is uniquely written as

(wn)n0=λ(un)n0+μ(vn)n0

with λ, μ in a field K (K = ℝ or K = ℂ).

Proof

The statement (i) is proved by induction.

The statement (ii) can be proved from (i) and from the Cramer’s rule for system of linear equations.

Definition 5.6

Let k be an integer which is greater than 2 and let a0, …, ak1 be k numbers. The sequence (Fn,k(a0, …, ak1)) for k ≥ 2 is defined by

Fn,k(a0,,ak-1)=Fn-1,k(a0,,ak-1)+Fn-k,k(a0,,ak-1),         nk

with

Fi,k(a0,,ak-1)=ai,         i{0,,k-1}.

The sequence (Fn,k(a0, …, ak1)) is called the k-Fibonacci sequence with initial conditions a0, …, ak1.

Proposition 5.7

Let a0, a1be two numbers. The 2-Fibonacci numbers sequence (Fn,2(a0, a1)) has general term

Fn,2(a0,a1)=αϕn+β(1-ϕ)n,         n0

where ϕ=1+52 is the golden ratio and

α=a0(ϕ-1)+a15,         β=a0ϕ-a15.

In particular, we have

Fn=Fn,2(0,1),         Ln=Fn,2(2,1).
Proof

Let a0, a1 be two numbers. Using the relation of recurrence of the sequence (Fn,2(a0, a1)) and taking the Ansatz Fn,2(a0, a1) = zn, we have for n ≥ 2

zn=zn-1+zn-2.

For z ≠ 0, it gives (n ≥ 2) z2z − 1 = 0. The discriminant of this polynomial equation of second degree is Δ=5. So, the roots of this equation are:

ϕ=1+52,         1-ϕ=1-52.

We can notice that any linear combination of ϕn, (1 − ϕ)n for n ≥ 0 verifies the equation zn = zn1 + zn2 for n ≥ 0. Since 0 = 0 · ϕn = 0 · (1 − ϕ)n, the sequences which satisfy the recurrence relation of sequence (Fn,2(a0, a1)) form a vector subspace of the set of complex sequences. Given a0, a1, from Theorem 5.5 above, since

det(11ϕ1-ϕ)=1-2ϕ=-50

we deduce that there exist two numbers α, β such that

Fn,2(a0,a1)=αϕn+β(1-ϕ)n.

Since

F0,2(a0,a1)=a0         F1,2(a0,a1)=a1,

the coefficients α, β verify the matrix equation

(11ϕ1-ϕ)   (αβ)=(a0a1)

So:

(αβ)=(11ϕ1-ϕ)-1(a0a1)

where

(11ϕ1-ϕ)-1=15(ϕ-11ϕ-1)

So:

(αβ)=15(a0(ϕ-1)+a1a0ϕ-a1).

Proposition 5.8

Let a0, a1be two numbers. We have

Fn,2(a0,a1)=a0Fn+1+(a1-a0)Fn,         n0.
Proof

From Proposition 5.7, we have

Fn,2(a0,a1)=(a0(ϕ-1)+a1)ϕn+(a0ϕ-a1)(1-ϕ)n5=a0[(ϕ-1)ϕn+ϕ(1-ϕ)n]+a1[ϕn-(1-ϕ)n]5=-a0{(1-ϕ)ϕn-ϕ(1-ϕ)n5}+a1{ϕn-(1-ϕ)n5}=-a0{(1-ϕ)ϕn+(1-ϕ-1)(1-ϕ)n5}+a1Fn=-a0{ϕn-(1-ϕ)n5-(ϕn+1-(1-ϕ)n+15)}+a1Fn=-a0(Fn-Fn+1)+a1Fn=a0Fn+1+(a1-a0)Fn.

Proposition 5.9

Let z be a real complex number such that ϕ|z| < 1. We have

n=0+Fnzn=z(1-ϕz)(1-z+ϕz)=z1-z-z2

This is a standard result and we omit the proof here.

Example 5.10

Applying Proposition 5.9 when z = 1/2, we have

n=0+Fn2n=1/2(1-ϕ2)(12+ϕ2)=22+2ϕ-ϕ-ϕ2=22+ϕ-(ϕ+1)=2.

Thus n=0+Fn2n+1=1.

Proposition 5.11

Let z be a real complex number such that ϕ|z| < 1. Let a0and a1be two numbers. We have the generating function

n=0+Fn,2(a0,a1)zn=a0+(a1-a0)z(1-ϕz)(1-z+ϕz)=a0+(a1-a0)z1-z-z2.
Proof

Let z be a real complex number such that ϕ|z| < 1. When z = 0, we have

(n=0+Fn,2(a0,a1)zn)z=0=F0,2(a0,a1)=a0

and

(a0+(a1-a0)z(1-ϕz)(1-z+ϕz))z=0=a0.

So, the formula of Proposition 5.11 is true for z = 0. In the following, we assume that z ≠ 0. From Proposition 5.8, we know that

Fn,2(a0,a1)=a0Fn+1+(a1-a0)Fn,         n0.

So, using Proposition 5.9, we have (ϕ|z| < 1 and z ≠ 0)

n=0+Fn,2(a0,a1)zn=a0n=0+Fn+1zn+(a1-a0)n=0+Fnzn.

Or (ϕ|z| < 1 and z ≠ 0)

n=0+Fn+1zn=1zn=0+Fn+1zn+1=1zn=1+Fnzn=1zn=0+Fnzn

where we used the fact that F0 = 0.

It follows that (ϕ|z| < 1 and z ≠ 0)

n=0+Fn,2(a0,a1)zn=(a0z+a1-a0)n=0+Fnzn.

From Proposition 5.9, it results that (ϕ|z| < 1 and z ≠ 0)

n=0+Fn,2(a0,a1)zn=(a0+(a1-a0)zz)z(1-ϕz)(1-z+ϕz)=a0+(a1-a0)z(1-ϕz)(1-z+ϕz)=a0+(a1-a0)z1-z-z2.

Since this relation is also true for z = 0 (see above), this relation is true for ϕ|z| < 1.

Example 5.12

Applying Proposition 5.11 when a0 = 2, a1 = 1 and z = 1/3, since Fn,2(2, 1) = Ln for all n ≥ 0, we have

n=0+Ln3n=2-13(1-ϕ3)(1-13+ϕ3)=156+ϕ-ϕ2=156+ϕ-(ϕ+1)=155=3.

Therefore n=0+Ln3n+1=1.

Proposition 5.13

Let z be a real complex number such that ϕ|z| < 1. Let a, b, r be three numbers. We have

n=0+Cn,2(a,b,r)zn=b-a-r+az+z2[(az+b)(1-z)+rz]1-2z+z3

or equivalently

n=0+Cn,2(a,b,r)zn=a(1-z)(2z-1)+b(1-z)2+r(2z-1)1-2z+z3.

This result can be derived routinely using the results we have derived so far. Although the proof is a little involved, but it follows essentially the same pattern as the previous result. So for the sake of brevity we shall omit it here.

Example 5.14

Applying Proposition 5.13 when z = 1/2, we have

n=0+Cn,2(a,b,r)2n=b418=2b.

So, n=0+Cn,2(a,b,r)2n+1=b.

Applying Proposition 5.13 when a = −r = 1, b = 0 and z = 1/3, we have

n=0+Cn,2(1,0,-1)3n=23(-13)-(-13)1-23+127=-29+1313+127=191027=310.

So, n=0+Cn,2(1,0,-1)3n+1=110.

Proposition 5.15

Let a0, a1be two numbers. We have

Fk+l,2(a0,a1)=Fl,2(a0,a1)Fk+1+Fl-1,2(a0,a1)Fk,         k0,         l1,

or equivalently

Fk+l,2(a0,a1)=Fk,2(Fl,2(a0,a1),Fl+1,2(a0,a1)),         k0,         l0.
Proof

Let a0, a1 be two numbers. From Proposition 5.8, we know that for k+l ≥ 0 we have

Fk+l,2(a0,a1)=a0Fk+l+1+(a1-a0)Fk+l.

Using Theorem 1.27, we have

Fk+l,2(a0,a1)=a0(Fl+1Fk+1+FlFk)+(a1-a0)(FlFk+1+Fl-1Fk)=(a0Fl+1+(a1-a0)Fl)Fk+1+(a0Fl+(a1-a0)Fl-1)Fk.

Using Proposition 5.8, we get

Fk+l,2(a0,a1)=Fl,2(a0,a1)Fk+1+Fl-1,2(a0,a1)Fk=Fk,2(Fl,2(a0,a1),Fl+1,2(a0,a1)).

In a similar way we can obtain the following result by using the corresponding results dervide so far.

Proposition 5.16

Let a, b, r be three numbers. We have:

Ck+l,2(a,b,r)=Cl-1,2(a,b,r)Fk+Cl,2(a,b,r)Fk+1+r(Fk+2-1),         k0,         l1,

or equivalently

Ck+l,2(a,b,r)=Ck+2,2(Cl-1,2(a,b,r),Cl,2(a,b,r),r),         k0,         l1.

We now have the following more general results.

Theorem 5.17

Let a0, a1be two numbers. We have

Fk,2(a0Fl-1,2(a0,a1)+a1Fl,2(a0,a1),a0Fl,2(a0,a1)+a1Fl+1,2(a0,a1))=Fl,2(a0,a1)Fk+1,2(a0,a1)+Fl-1,2(a0,a1)Fk,2(a0,a1),         k0,         l1

The proof is an easy application of Proposition 5.9 and we shall omit it here.

Theorem 5.18

Let a, b, r be three numbers. We have

Ck,2(aCl-1,2(a,b,r)+bCl,2(a,b,r),(a+r)Cl,2(a,b,r)+b(Cl+1,2(a,b,r)-r),r(Cl+1,2(a,b,r)-r))=Cl,2(a,b,r)Ck+1,2(a,b,r)+Cl-1,2(a,b,r)Ck,2(a,b,r),         k0,         l1.

Using Proposition 5.5 and the principle of mathematical induction the above result can be verified. We omit the details here.

Remark 5.19

Using Proposition 5.4 and using Proposition 5.8, we can notice that

Cn,2(a,b,0)=Fn,2(b-a,a),         n0

Indeed, we have (n ≥ 0)

Fn,2(b-a,a)=(b-a)Fn+1+(a-b+a)Fn=(b-a)Fn+1+(2a-b)Fn

Using the definition of the Fibonacci sequence, we have for n ≥ 2

Fn,2(b-a,a)=(b-a)(Fn+Fn-1)+(2a-b)(Fn-1+Fn-2)=(b-a)(2Fn-1+Fn-2)+(2a-b)(Fn-1+Fn-2)=(2(b-a)+2a-b)Fn-1+(b-a+2a-b)Fn-2=bFn-1+aFn-2=aFn-2+bFn-1=Cn,2(a,b,0).

Since F0,2(b a, a) = C0,2(a, b, 0) = b a and F1,2(b a, a) = C1,2(a, b, 0) = a, the formula derived above for n ≥ 2 is also true for n = 0 and for n = 1.

Taking r = 0 in Theorem 5.18, it can be shown that Theorem 5.17 is a particular case of Theorem 5.18. Indeed, since (l ≥ 1):

aCl,2(a,b,0)+bCl+1,2(a,b,0)-(aCl-1,2(a,b,0)+bCl,2(a,b,0))=a(Cl,2(a,b,0)-Cl-1,2(a,b,0))+b(Cl+1,2(a,b,0)-Cl,2(a,b,0))

and so (l ≥ 2):

aCl,2(a,b,0)+bCl+1,2(a,b,0)-(aCl-1,2(a,b,0)+bCl,2(a,b,0))=aCl-2,2(a,b,0)+bCl-1,2(a,b,0)

using the relation (5.2), we have (k ≥ 0 and l ≥ 2):

Ck,2(aCl-1,2(a,b,0)+bCl,2(a,b,0),aCl,2(a,b,0)+bCl+1,2(a,b,0),0)=Fk,2(aCl-2,2(a,b,0)+bCl-1,2(a,b,0),aCl-1,2(a,b,0)+bCl,2(a,b,0))=Fk,2((b-a)Cl-1,2(a,b,0)+a(Cl-2,2(a,b,0)+Cl-1,2(a,b,0)),(b-a)Cl,2(a,b,0)+a(Cl-1,2(a,b,0)+Cl,2(a,b,0))).

So (k ≥ 0 and l ≥ 1):

Ck,2(aCl-1,2(a,b,0)+bCl,2(a,b,0),aCl,2(a,b,0)+bCl+1,2(a,b,0),0)=Fk,2((b-a)Cl-1,2(a,b,0)+aCl,2(a,b,0),(b-a)Cl,2(a,b,0)+aCl+1,2(a,b,0))=Fk,2((b-a)Fl-1,2(b-a,a)+aFl,2(b-a,a),(b-a)Fl,2(b-a,a)+aFl+1,2(b-a,a)).

Moreover, from Theorem 5.18, we have (k ≥ 0 and l ≥ 1):

Ck,2(aCl-1,2(a,b,0)+bCl,2(a,b,0),aCl,2(a,b,0)+bCl+1,2(a,b,0),0)=Cl,2(a,b,0)Ck+1,2(a,b,0)+Cl-1,2(a,b,0)Ck,2(a,b,0)=Fl,2(b-a,a)Fk+1,2(b-a,a)+Fl-1,2(b-a,a)Fk,2(b-a,a).

Therefore (k ≥ 0 and l ≥ 1):

Fk,2((b-a)Fl-1,2(b-a,a)+aFl,2(b-a,a),(b-a)Fl,2(b-a,a)+aFl+1,2(b-a,a))=Fl,2(b-a,a)Fk+1,2(b-a,a)+Fl-1,2(b-a,a)Fk+2(b-a,a)

which is equivalent to Theorem 5.17 when a0 is replaced by b a and when a1 is replaced by a. Besides, taking a = b = 1 in the relation (5.3), using Theorem 1.27, since Fn,2(0, 1) = Fn, for all n ≥ 0, we get (l ≥ 0):

Fk,2(Fl,Fl+1)=Fk+l,         k0

Definition 5.20

Let a, b, r be three numbers, let n ≥ 0 be a natural number and let l be a non-zero positive integer. The sequences (xn,l(a, b, r)), (yn,l(a, b, r)) and (zn,l(a, b, r)) are defined by (n ≥ 0 and l ≥ 1):

xn+1,l(a,b,r)=xn,l(a,b,r)Cl-1,2(xn,l(a,b,r),yn,l(a,b,r),zn,l(a,b,r))+yn,l(a,b,r)Cl,2(xn,l(a,b,r),yn,l(a,b,r),zn,l(a,b,r))yn+1,l(a,b,r)=yn,l(a,b,r)Cl-1,2(xn,l(a,b,r),yn,l(a,b,r),zn,l(a,b,r))+(xn,l(a,b,r)+yn,l(a,b,r)+zn,l(a,b,r))Cl,2(xn,l(a,b,r),yn,l(a,b,r),zn,l(a,b,r))rn+1,l(a,b,r)=zn,l(a,b,r)(Cl-1,2(xn,l(a,b,r),yn,l(a,b,r),zn,l(a,b,r))+Cl,2(xn,l(a,b,r),yn,l(a,b,r),zn,l(a,b,r)))

and for l ≥ 1

x0,l(a,b,r)=aCl-1,2(a,b,r)+bCl,2(a,b,r)y0,l(a,b,r)=bCl-1,2(a,b,r)+(a+b+r)Cl,2(a,b,r)z0,l(a,b,r)=r(Cl-1,2(a,b,r)+Cl,2(a,b,r))

In the following, when there is no ambiguity and when it is possible, we will abbreviate the notations used for terms of sequences (xn,l(a, b, r)), (yn,l(a, b, r)) and (zn,l(a, b, r)). More precisely, if a, b, r don’t take particular values, then we will substitute xn,l, yn,l, zn,l for xn,l(a, b, r), yn,l(a, b, r), zn,l(a, b, r) respectively. Thus, the recurrence relations which define the sequences (xn,l(a, b, r)), (yn,l(a, b, r)) and (zn,l(a, b, r)) can be rewritten as (n ≥ 0 and l ≥ 1):

xn+1,l=xn,lCl-1,2(xn,l,yn,l,zn,l)+yn,lCl,2(xn,l,yn,l,zn,l)yn+1,l=yn,lCl-1,2(xn,l,yn,l,zn,l)+(xn,l+yn,l+zn,l)Cl,2(xn,l,yn,l,zn,l)rn+1,l=zn,l(Cl-1,2(xn,l,yn,l,zn,l)+Cl,2(xn,l,yn,l,zn,l)).

Proposition 5.21

Let n ≥ 0 be a natural number and let l be a non-zero positive integer. We have

Ck,2(xn+1,l,yn+1,l,zn+1,l)=Cl,2(xn,l,yn,l,zn,l)Ck+1,2(xn,l,yn,l,zn,l)+Cl-1,2(xn,l,yn,l,zn,l)Ck,2(xn,l,yn,l,zn,l).
Proof

This proposition is a direct consequence of Definition 5.1, Definition 5.20 and Theorem 5.18.

Proposition 5.22

Let n ≥ 0 be a natural number and let l be a non-zero positive integer. We have (n ≥ 0 and l ≥ 1)

(yn,l-xn,l)(zn,lyn+1,l-yn,lzn+1,l)=(xn,l+zn,l)(zn,lxn+1,l-xn,lzn+1,l).

or equivalently (n ≥ 0 and l ≥ 1)

zn,l(xn,l+zn,l)xn+1,l+zn,l(xn,l-yn,l)yn+1,l-(xn,l(xn,l+yn,l+zn,l)-yn,l2)zn+1,l=0.
Proof

In the following, n denotes a natural number (n ≥ 0) and l denotes a non-zero positive integer (l ≥ 1). From Definition 5.20, we have (n ≥ 0 and l ≥ 1)

zn,lxn+1,l-xn,lzn+1,l=xn,lzn,lCl-1,2(xn,l,yn,l,zn,l)+yn,lzn,lCl,2(xn,l,yn,l,zn,l)-xn,lzn,lCl-1,2(xn,l,yn,l,zn,l)-xn,lzn,lCl,2(xn,l,yn,l,zn,l).

So

zn,lxn+1,l-xn,lzn+1,l=zn,l(yn,l-xn,l)Cl,2(xn,l,yn,l,zn,l),         n0,         l1

Moreover, we have (n ≥ 0 and l ≥ 1):

zn,lyn+1,l-yn,lzn+1,l=yn,lzn,lCl-1,2(xn,l,yn,l,zn,l)+zn,l(xn,l+yn,l+zn,l)Cl,2(xn,l,yn,l,zn,l)-yn,lzn,lCl-1,2(xn,l,yn,l,zn,l)-yn,lzn,lCl,2(xn,l,yn,l,zn,l).

So

zn,lyn+1,l-yn,lzn+1,l=zn,l(xn,l+zn,l)Cl,2(xn,l,yn,l,zn,l),         n0,         l1

Taking (xn,l + zn,l) (5.4) − (yn,lxn,l) (5.5) side by side, we get

(xn,l+zn,l)(zn,lxn+1,l-xn,lzn+1,l)-(yn,l-xn,l)(zn,lyn+1,l-yn,lzn+1,l)=0

and so

(xn,l+zn,l)(zn,lxn+1,l-xn,lzn+1,l)=(yn,l-xn,l)(zn,lyn+1,l-yn,lzn+1,l).

It proves the first part of Proposition 5.22. The second part of Proposition 5.22 follows from its first part. Indeed, from the first part of Proposition 5.22, we have (n ≥ 0 and l ≥ 1)

(xn,l+zn,l)zn,lxn+1,l-(xn,l+zn,l)xn,lzn+1,l=(yn,l-xn,l)zn,lyn+1,l-(yn,l-xn,l)yn,lzn+1,lzn,l(xn,l+zn,l)xn+1,l+zn,l(xn,l-yn,l)yn+1,l-((xn,l+zn,l)xn,l+(xn,l-yn,l)yn,l)zn+1,l=0zn,l(xn,l+zn,l)xn+1,l+zn,l(xn,l-yn,l)yn+1,l-(xn,l2+zn,lxn,l+xn,lyn,l-yn,l2)zn+1,l=0zn,l(xn,l+zn,l)xn+1,l+zn,l(xn,l-yn,l)yn+1,l-(xn,l(xn,l+zn,l+yn,l)-yn,l2)zn+1,l=0

It proves the second part of Proposition 5.22.

Definition 5.23

Let be a field. Let l be a non-zero positive integer (l ≥ 1). The function Fl is defined on by (l ≥ 1 and (x, y, z) ∈ )

Fl(x,y,z)=(xCl-1,2(x,y,z)+yCl,2(x,y,z),yCl-1,2(x,y,z)+(x+y+z)Cl,2(x,y,z),z(Cl-1,2(x,y,z)+Cl,2(x,y,z))).

Remark 5.24

From Definition 5.20 and from Definition 5.23, we have (n ≥ 0 and l ≥ 1)

Fl(xn,l,yn,l,zn,l)=(xn+1,l,yn+1,l,zn+1,l)

So, from Proposition 5.21, we have

Ck,2(Fl(xn,l,yn,l,zn,l))=Cl,2(xn,l,yn,l,zn,l)Ck+1,2(xn,l,yn,l,zn,l)+Cl-1,2(xn,l,yn,l,zn,l)Ck,2(xn,l,yn,l,zn,l).

Proposition 5.25

Let n ≥ 0 be a natural number and let l be a non-zero positive integer. We have (n ≥ 0 and l ≥ 1)

xn,l(1/2,1/2,-1/2)=yn,l(1/2,1/2,-1/2)=1/2zn,l(1/2,1/2,-1/2)=-1/2.

In other words, (1/2, 1/2,−1/2) is a fixed point of the function Fl for all l ≥ 1.

Proof

Let n ≥ 0 be a natural number and let l be a non-zero positive integer. Let us prove Proposition 5.25 by induction on the integer n ≥ 0 for all l ≥ 1. Using Definition 5.1, we have

C0,2(1/2,1/2,-1/2)=12-12-(-12)=12.

Moreover, from Proposition 5.4, using the definition of the Fibonacci sequence, we have (n ≥ 2)

Cn,2(1/2,1/2,-1/2)=Fn-22+Fn-12-12(Fn-1)=Fn-2+Fn-1-Fn2+12=12.

So

Cn,2(1/2,1/2,-1/2)=12,         n0.

Using Definition 5.20 and using Equation (5.6), it gives (l ≥ 1)

x0,l(1/2,1/2,-1/2)=12×12+