# Periodicity of power Fibonacci sequences
modulus a Fibonacci number

Josep M. Brunat and Joan-C. Lario

(April 1, 2022)

###### Abstract

Let ${\mathcal{F}}=(F_{i}:i\geq 0)$ be the sequence of Fibonacci numbers, and
$j$ and $e$ be non negative integers. We study the periodicity of the power
Fibonacci sequences ${\mathcal{F}}^{e}(F_{j})=(F_{i}^{e}\pmod{F_{j}}:i\geq
0)$. It is shown that for every $j,e\geq 1$ the sequence
${\mathcal{F}}^{e}(F_{j})$ is periodic and its periodicity is computed. The
result was previously known for ${\mathcal{F}}(F_{j})$; that is, for $e=1$.
For $e\in\\{1,2\\}$, the values of the normalized residues $\rho_{i}\equiv
F_{i}^{e}\pmod{F_{j}}$ with $0\leq\rho_{i}<F_{j}-1$ are obtained.

MSC2020: 11B39 · 11B50 · 11A15

##  1 Introduction

The Fibonacci sequence $\mathcal{F}=(F_{i}:i\geq 0)$ is defined by recursion:
$F_{0}=0$, $F_{1}=1$ and $F_{i+1}=F_{i}+F_{i-1}$ for all $i\geq 1$. Let $m\geq
3$ be an integer. The periodicity of the sequence
${\mathcal{F}}(m)=(F_{i}\pmod{m}:i\geq 0)$ has attracted a lot of attention,
see for example M. Renault [6, 7] and the references cited therein. In
particular, if $m=F_{j}$ is a Fibonacci number with $j\geq 4$, A. Ehrlich [4]
proves that the sequence $\mathcal{F}(F_{j})$ has periodicity either $2j$ if
$j$ is even or periodicity $4j$ if $j$ is odd. Our aim in the present paper is
to study the periodicity of the power Fibonacci sequences

${\mathcal{F}}^{e}(F_{j})=(F_{i}^{e}\\!\\!\\!\\!\pmod{F_{j}}:i\geq 0),$

for integers $j\geq 0$ and $e\geq 1$.

Throughout, we fix representatives of the classes modulo $F_{j}$. We set
$\rho_{i}(F_{j},e)$ defined by $\rho_{i}(F_{j},e)\equiv F_{i}^{e}\pmod{F_{j}}$
with $0\leq\rho_{i}(F_{j},e)\leq F_{j}-1$. If $F_{j}$ and $e$ are clear from
the context, we shall write simply $\rho_{i}$ instead of $\rho_{i}(F_{j},e)$.

The product of two sequences ${\mathcal{F}}^{e_{1}}(F_{j})$ and
${\mathcal{F}}^{e_{2}}(F_{j})$ is the product term to term modulus $F_{j}$,
that is,
${\mathcal{F}}^{e_{1}}(F_{j})\cdot{\mathcal{F}}^{e_{2}}(F_{j})={\mathcal{F}}^{e_{1}+e_{2}}(F_{j})$.
A sequence $S=(a_{i}:i\geq 0)$ is _periodic_ if it exists an integer $p\geq
1$, called a _period_ , such that $a_{i+p}=a_{i}$ for all $i\geq 0$. In this
case, the sequence $S$ is denoted by $S=[a_{0},a_{1},\ldots,a_{p-1}]$. It is
clear that if $p$ is a period of a sequence $S$, then $qp$ is also a period of
$S$ for all integers $q\geq 1$. If ${\mathcal{F}}^{e}(F_{j})$ is periodic, the
minimum period is called its _periodicity_ and will be denoted by
$\pi(F_{j},e)$. In this case, it is clear that $\pi(F_{j},qe)\mid\pi(F_{j},e)$
for all integers $q\geq 1$, and that $\pi(F_{j},e)$ is a divisor of all
periods of ${\mathcal{F}}^{e}(F_{j})$.

If $j=0$, we have $F_{j}=0$ and the sequence ${\mathcal{F}}^{e}(F_{j})$ is the
sequence $(F_{i}^{e}:i\geq 0)$. Since $F_{i}^{e}<F_{i+1}^{e}$ for all $i\geq
2$, the sequence ${\mathcal{F}}^{e}(F_{0})$ is not periodic.

If $j=1$ or $j=2$, we have $F_{j}=1$. Then,
${\mathcal{F}}^{e}(F_{1})={\mathcal{F}}^{e}(F_{2})=[0]$ and
$\pi(F_{1},e)=\pi(F_{2},e)=1$.

If $j=3$, we have $F_{j}=2$. Then ${\mathcal{F}}(F_{3})=[0,1,1]$ and
${\mathcal{F}}^{e}(F_{3})=[0,1,1]$ for all $e\geq 1$. Thus, $\pi(F_{3},e)=3$.

From now on, we assume that $j\geq 4$.

In Sections 2 and 3 we give the exact values of $\rho_{i}(F_{j},1)$ and
$\rho_{i}(F_{j},2)$, respectively, and the periods $\pi(F_{j},1)$ and
$\pi(F_{j},2)$. In Section 4 we obtain the periodicity of
${\mathcal{F}}^{e}(F_{j})$ for any $e>2$.

Along the paper we use the following well known properties of Fibonacci
numbers (the proofs can be found in D. M. Burton [1], T. Koshly [5], or N. N.
Vorob’ev [8]):

$\displaystyle\gcd(F_{n},F_{m})=F_{\gcd(n,m)}\quad\mbox{for all $m,n\geq 0$,
$(m,n)\neq(0,0)$};$ (1) $\displaystyle
F_{n+m}=F_{n-1}F_{m}+F_{n}F_{m+1}\quad\mbox{for all $m\geq 0$ and $n\geq 1$};$
(2) $\displaystyle F_{n}^{2}-F_{n-r}F_{n+r}=(-1)^{n-r}F_{r}^{2}\quad\mbox{for
all $n\geq r\geq 0$}\quad\mbox{(Catalan identity)};$ (3) $\displaystyle
F_{n}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}\quad\mbox{for all $n\geq
1$}\quad\mbox{(Cassini identity)}.$ (4)

Let $\phi=(1+\sqrt{5})/2$ and $\psi=(1-\sqrt{5})/2$. In the application of
Carmichael’s Theorem in Section 4 we also need the well known fact that for
all integers $n\geq 0$, it holds

$F_{n}=(\phi^{n}-\psi^{n})/\sqrt{5}=(\phi^{n}-\psi^{n})/(\phi-\psi).$

Finally, a remark about notation. Throughout, if the modulus is not explicitly
indicated, in all congruences it is understood that this is the Fibonacci
number $F_{j}$ from the context.

##  2 The sequences ${\mathcal{F}}(F_{j})$

A. Ehrlich [4] proved that if $j\geq 4$ then $\pi(F_{j},1)=2j$ if $j$ is even
and $\pi(F_{j},1)=4j$ if $j$ is odd. In this section, we calculate explicitly
the terms of ${\mathcal{F}}(F_{j})$ and obtain the same result.

The cases $j\in\\{4,5,6,7\\}$ are easily obtained:

$\begin{array}[]{lr@{\hskip 2pt}l}F_{4}=3,&{\mathcal{F}}(F_{4})=\hskip
2.0&(0,1,1,2,0,2,2,1,0,1,\ldots)\\\ &=\hskip 2.0&[0,1,1,2,0,2,2,1].\\\
F_{5}=5,&{\mathcal{F}}(F_{5})=\hskip
2.0&(0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,1,\ldots)\\\ &=\hskip
2.0&[0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1].\\\
F_{6}=8,&{\mathcal{F}}(F_{6})=\hskip
2.0&(0,1,1,2,3,5,0,5,5,2,7,1,0,1,\ldots)\\\ &=\hskip
2.0&[0,1,1,2,3,5,0,5,5,2,7,1].\\\ F_{7}=13,&{\mathcal{F}}(F_{7})=\hskip
2.0&(0,1,1,2,3,5,8,0,8,8,3,11,1,12,0,12,12,11,10,8,5,0,5,5,10,2,12,1,0,1,\ldots)\\\
&=\hskip
2.0&[0,1,1,2,3,5,8,0,8,8,3,11,1,12,0,12,12,11,10,8,5,0,5,5,10,2,12,1].\end{array}$
(5)

Then,

$\pi(F_{4},1)=8,\quad\pi(F_{5},1)=20,\quad\pi(F_{6},1)=12,\quad\pi(F_{7},1)=28.$
(6)

###### Theorem 1

Let $j\geq 4$ be an integer.

  1. (i)

If $j$ is even, then $\pi(F_{j},1)=2j$ and the values of
$\rho_{i}=\rho_{i}(F_{j},1)$ for $i\in\\{0,\ldots,2j-1\\}$ are

    1. (i.1)

$\rho_{i}=F_{i}$ if $i<j$;

    2. (i.2)

$\rho_{i}=0$ if $i=j$;

    3. (i.3)

$\rho_{i}=F_{2j-i}$ if $j<i<2j$ and $i$ is odd;

    4. (i.4)

$\rho_{i}=F_{j}-F_{2j-i}$ if $j<i<2j$ and $i$ is even.

  2. (ii)

If $j$ is odd, then $\pi(F_{j},1)=4j$ and the values of
$\rho_{i}=\rho_{i}(F_{j},1)$ for $i\in\\{0,\ldots,4j-1\\}$ are

    1. (ii.1)

$\rho_{i}=F_{i}$ if $i<j$;

    2. (ii.2)

$\rho_{i}=0$ if $i=j$;

    3. (ii.3)

$\rho_{i}=F_{2j-i}$ if $j<i<2j$ and $i$ is even;

    4. (ii.4)

$\rho_{i}=F_{j}-F_{2j-i}$ if $j<i<2j$ and $i$ is odd;

    5. (ii.5)

$\rho_{i}=0$ if $i=2j$;

    6. (ii.6)

$\rho_{i}=F_{j}-F_{i-2j}$ if $2j<i<3j$;

    7. (ii.7)

$\rho_{i}=0$ if $i=3j$;

    8. (ii.8)

$\rho_{i}=F_{j}-F_{4j-i}$ if $3j<i<4j$ and $i$ is even;

    9. (ii.9)

$\rho_{i}=F_{4j-i}$ if $3j<i<4j$ and $i$ is odd.

Proof. By (5) and (6), the result is true for $j\in\\{4,5,6,7\\}$. Now, let
$j\geq 8$ and assume the properties are true for values $<j$. First we check
that the values of $\rho_{i}$ for $i\in\\{0,\ldots,2j-1\\}$ when $j$ is even
and for $i\in\\{0,\ldots,4j-1\\}$ when $j$ is odd are those given in the
respective list of items.

(i) Assume that $j$ is even. Then,

(i.1) and (i.2), are obvious.

(i.3) and (i.4). By induction on $i\in\\{j+1,\ldots,2j-1\\}$. For $i=j+1$ we
have $i$ odd, $2j-i=2j-(j+1)=j-1$, and

$\rho_{j+1}\equiv F_{j+1}=F_{j}+F_{j-1}\equiv F_{j-1}=F_{2j-i}.$

For $i=j+2$, we have $i$ even, $2j-i=2j-(j+2)=j-2$, and

$\rho_{j+2}\equiv F_{j+2}=F_{j+1}+F_{j}=F_{j}+F_{j-1}+F_{j}\equiv
F_{j-1}=F_{j}-F_{j-2}=F_{j}-F_{2j-i}.$

If $i\geq j+3$ and $i$ is odd,

$\rho_{i}\equiv
F_{i}=F_{i-1}+F_{i-2}\equiv\rho_{i-1}+\rho_{i-2}=F_{j}-F_{2j-i+1}+F_{2j-i+2}\equiv
F_{2j-i+2}-F_{2j-i+1}=F_{2j-i}.$

If $i\geq j+4$ and $i$ is even,

$\rho_{i}\equiv
F_{i}=F_{i-1}+F_{i-2}\equiv\rho_{i-1}+\rho_{i-2}=F_{2j-i+1}+F_{j}-F_{2j-i+2}=F_{j}-(F_{2j-i+2}-F_{2j-i+1})=F_{j}-F_{2j-i}.$

For $1\leq i\leq 2j-1$, the unique value $i$ such that $\rho_{i}=0$ is $i=j$,
but $\rho_{j+1}=F_{j-1}\neq 1$. Hence, ${\mathcal{F}}(F_{j})$ has not a period
$\leq 2j-1$. Now, $\rho_{2j-2}=F_{j}-F_{2}=F_{j}-1\equiv-1$ and
$\rho_{2j-1}=F_{1}=1$. Hence, $\rho_{2j}=0$ and $\rho_{2j+1}=1$. Thus,
$\pi(F_{j},1)=2j$.

(ii) Now, assume that $j$ is odd. Then,

(ii.1) and (ii.2) are obvious.

(ii.3) and (ii.4) By induction on $i$. If $i=j+1$, then $i$ is even,
$2j-i=j-1$, and

$\rho_{j+1}\equiv F_{j+1}=F_{j}+F_{j-1}\equiv F_{j-1}=F_{2j-i}.$

If $i=j+2$, then $i$ is odd , $2j-i=j-2$, and

$\rho_{j+2}\equiv F_{j+2}=F_{j+1}+F_{j}\equiv
F_{j+1}\equiv\rho_{j+1}=F_{j-1}=F_{j}-F_{j-2}=F_{j}-F_{2j-i}.$

If $j+3\leq i<2j-1$ and is $i$ even, then

$\rho_{i}\equiv
F_{i}=F_{i-1}+F_{i-2}\equiv\rho_{i-1}+\rho_{i-2}=F_{j}-F_{2j-i+1}+F_{2j-i+2}\equiv
F_{2j-i}.$

If $j+3\leq i<2j-1$ and is $i$ is odd, then

$\rho_{i}\equiv F_{i}=F_{i-1}+F_{i-2}\equiv
F_{2j-i+1}+F_{j}-F_{2j-i+2}=F_{j}-(F_{2j-i+2}-F_{2j-i+1})=F_{j}-F_{2j-i}.$

(ii.5) Since $\rho_{2j-2}=F_{2}=1$ and $\rho_{2j-1}=F_{j}-F_{1}=F_{j}-1$, we
have $\rho_{2j}\equiv F_{j}\equiv 0$.

(ii.6) By induction on $i$. If $i=2j+1$, we have $i-2j=1$ and

$\rho_{2j+1}\equiv
F_{2j+1}=F_{2j}+F_{2j-1}\equiv\rho_{2j}+\rho_{2j-1}=\rho_{2j-1}=F_{j}-F_{1}=F_{j}-F_{i-2j}.$

If $i=2j+2$, we have $i-2j=2$ and

$\rho_{2j+2}\equiv F_{2j+2}=F_{2j+1}+F_{2j}\equiv
F_{j}-F_{1}=F_{j}-F_{2}=F_{j}-F_{i-2j}.$

If $2j+2<i<3j$, then

$\rho_{i}\equiv F_{i}=F_{i-1}+F_{i-2}\equiv
F_{j}-F_{i-1-2j}+F_{j}-F_{i-2-2j}\equiv
F_{j}-(F_{i-1-2j}+F_{i-2-2j})=F_{j}-F_{i-2j}.$

(ii.7) Since $\rho_{3j-2}=F_{j}-F_{j-2}$ and $\rho_{3j-1}=F_{j}-F_{j-1}$, we
have $\rho_{3j}\equiv-F_{j-1}-F_{j-2}=-F_{j}\equiv 0$.

(ii.8) and (ii.9) By induction on $i$. If $i=3j+1$, then $i$ is even,
$4j-i=j-1$, and

$\rho_{3j+1}\equiv F_{3j+1}=F_{3j}+F_{3j-1}\equiv
F_{3j-1}\equiv\rho_{3j-1}=F_{j}-F_{j-1}=F_{j}-F_{4j-i}.$

If $i=3j+2$, then $i$ is odd, $4j-i=j-2$ and

$\rho_{3j+2}\equiv F_{3j+1}+F_{3j}\equiv
F_{j}-F_{j-1}+F_{3j}=F_{j}-F_{j-1}=F_{j-2}=F_{4j-i}.$

If $3j+2<i<4j$ and $i$ is even, then

$\rho_{i}\equiv
F_{i}=F_{i-1}+F_{i-2}=F_{4j-i+1}+F_{j}-F_{4j-i+2}=F_{j}-(F_{4j-i+2}-F_{4j-i+1})=F_{j}-F_{4j-i}.$

If $3j+2<i<4j$ and $i$ is odd, then

$\rho_{i}\equiv F_{i}=F_{i-1}+F_{i-2}=F_{j}-F_{4j-i+1}+F_{4j-i+2}\equiv
F_{4j-i+2}-F_{4j-i+1}=F_{4j-i}.$

The unique values of $i\in\\{1,\ldots,4j-1\\}$ such that $\rho_{i}=0$ are
$i=j$, $i=2j$ and $i=3j$. But $\rho_{j+1}=F_{j-1}\neq 1$,
$\rho_{2j+1}=F_{j}-F_{1}\neq 1$ and $\rho_{3j+1}=F_{j}-F_{j-1}=F_{j-2}\neq 1$.
Therefore, ${\mathcal{F}}(F_{j})$ has no period $<4j$.

Now,

$\rho_{4j}\equiv F_{4j}=F_{4j-1}+F_{4j-2}\equiv F_{1}+F_{j}-F_{2}\equiv 0,$

and

$\rho_{4j+1}\equiv F_{4j+1}=F_{4j}+F_{4j-1}\equiv F_{4j-1}\equiv F_{1}=1.$

Hence $\pi(F_{j},1)=4j$. $\Box$

##  3 The square sequences ${\mathcal{F}}^{2}(F_{j})$

In this section we calculate the terms of ${\mathcal{F}}^{2}(F_{j})$ and prove
that $\pi(F_{j},2)=j$ if $j$ is even and $\pi(F_{j},2)=2j$ if $j$ is odd.

###### Lemma 2

Let $k\geq 2$ be an integer, and $\alpha\in\\{0,1,\ldots,k\\}$. It holds

  1. (i)

$F_{k}^{2}<F_{2k}$;

  2. (ii)

$F^{2}_{k+\alpha}\equiv F^{2}_{k-\alpha}\pmod{F_{2k}}$;

  3. (iii)

$F_{k+1}^{2}<F_{2k+1}$;

  4. (iv)

$F^{2}_{k+1+\alpha}\equiv-F_{k-\alpha}^{2}\pmod{F_{2k+1}}$.

Proof. (i) Take $m=n=k$ in (2). Then,
$F_{2k}=F_{k-1}F_{k}+F_{k}F_{k+1}>F_{k}F_{k+1}>F_{k}^{2}$.

(ii) Take $n=k+\alpha$ and $r=k-\alpha$ in (3). Then, $n-r=2\alpha$, $n+r=2k$,
and

$F_{k+\alpha}^{2}-F_{2\alpha}F_{2k}=(-1)^{2\alpha}F_{k-\alpha}^{2}=F_{k-\alpha}^{2}.$

By taking modulus $F_{2k}$ we get $F_{k+\alpha}^{2}\equiv
F^{2}_{k-\alpha}\pmod{F_{2k}}$.

(iii) Take $m=k$ and $n=k+1$ in (2). Then, one has

$F_{2k+1}=F_{k+(k+1)}=F_{k-1}F_{k+1}+F_{k}F_{k+2}>F_{k-1}F_{k+1}+F_{k}F_{k+1}=(F_{k-1}+F_{k})F_{k+1}=F_{k+1}^{2}.$

(iv) Take $n=k+1+\alpha$ and $r=k-\alpha$ in (3). We have $n-r=2\alpha+1$,
$n+r=2k+1$, and

$F_{k+\alpha+1}^{2}-F_{2\alpha+1}F_{2k+1}=(-1)^{2\alpha+1}F_{k-\alpha}^{2}=-F_{k-\alpha}^{2}.$

Thus, $F_{k+\alpha+1}^{2}\equiv-F_{k-\alpha}^{2}\pmod{F_{2k+1}}$. $\Box$

###### Theorem 3

Let $j\geq 4$ be an integer and $\rho_{i}=\rho_{i}(F_{j},2)$.

  1. (i)

If $j=2t$ is even, then ${\mathcal{F}}^{2}(F_{j})$ has periodicity $j$ and the
values of $\rho_{i}$ for $i\in\\{0,\ldots,j-1\\}$ are

    1. (i.1)

$\rho_{i}=F_{i}^{2}$ if $i\in\\{0,\ldots,t\\}$;

    2. (i.2)

$\rho_{i}=F_{j-i}^{2}$ if $i\in\\{t+1,\ldots,j-1\\}$.

  2. (ii)

If $j=2t+1$ is odd, then ${\mathcal{F}}^{2}(j)$ has periodicity $2j$ and the
values of $\rho_{i}$ for $i\in\\{0,\ldots,2j-1\\}$ are

    1. (ii.1)

$\rho_{i}=F_{i}^{2}$ if $i\in\\{0,\ldots,t+1\\}$;

    2. (ii.2)

$\rho_{i}=F_{j}-F_{j-i}^{2}$ if $i\in\\{t+2,\ldots,j-1\\}$;

    3. (ii.3)

$\rho_{i}=0$ if $i=j$;

    4. (ii.4)

$\rho_{i}=\rho_{2j-i}$ if if $i\in\\{j+1,\ldots,2j-1\\}$.

Proof. The proof is very similar to that of Theorem 1. As for (i.1), if
$i\in\\{0,\ldots,t\\}$, by Lemma 2(i), we have $\rho_{i}\equiv
F_{i}^{2}<F_{2i}\leq F_{2t}=F_{j}$. Hence, $\rho_{i}=F_{i}^{2}$.

(i.2) For $i\in\\{t+1,\ldots,j-1\\}$, set $\alpha=i-t$. Then,
$j-i=2t-(t+\alpha)=t-\alpha$. By Lemma 2(ii), we have $F_{t+\alpha}^{2}\equiv
F_{t-\alpha}^{2}\pmod{F_{2t}}$. Thus,

$\rho_{i}\equiv F_{i}^{2}=F_{t+\alpha}^{2}\equiv
F_{t-\alpha}^{2}=F_{j-i}^{2}.$

Since $j-i\leq t$, we have $F^{2}_{j-i}<F_{j}$. Hence, $\rho_{i}=F_{j-i}^{2}$.

Now, we prove that $\pi(F_{j},2)=j$. Indeed, from (4), we have
$F_{j+1}^{2}-F_{j}F_{j+2}=(-1)^{j}=1$. Hence, $F_{j+1}^{2}\equiv 1$. Then, by
(2),

$F_{i+j}^{2}=(F_{i-1}F_{j}+F_{i}F_{j+1})^{2}\equiv F_{i}^{2}F_{j+1}^{2}\equiv
F_{i}^{2}.$

This implies that $\pi(F_{j},2)\mid j$. But, for $i\in\\{1,\ldots,j-1\\}$, we
have $\rho_{i}\neq 0$. Hence, $\pi(F_{j},2)=j$.

(ii.1) For $i\in\\{0,1,\ldots,t+1\\}$, by Lemma 2(iii), we have $0\leq
F_{i}^{2}\leq F_{t+1}^{2}<F_{2t+1}=F_{j}$. Hence, $\rho_{i}=F_{i}^{2}$.

(ii.2) For $i\in\\{t+2,\ldots,j-1\\}$, define $\alpha$ by $i=t+1+\alpha$.
Then, $j-i=2t+1-(t+1+\alpha)=t-\alpha$ and, by Lemma 2(iv), we have

$F_{i}^{2}=F_{t+\alpha+1}^{2}\equiv-F_{t-\alpha}^{2}=-F_{j-i}^{2}\equiv
F_{j}-F_{j-i}^{2}.$

Since $F_{j-i}^{2}<F_{j}$ due to $j-i\leq t+1$, we conclude
$\rho_{i}=F_{j}-F_{j-i}^{2}$.

(ii.3) Obviously, $\rho_{j}=0$.

(ii.4) For $i\in\\{j+1,\ldots,2j\\}$, define $\alpha$ by $i=j+\alpha$. Again,
by Catalan’s identity (3) with $r=\alpha$, we have

$F_{j+\alpha}^{2}-F_{j}F_{j+2\alpha}=(-1)^{j}F_{\alpha}^{2}=-F_{\alpha}^{2}$

so that $F_{j+\alpha}^{2}\equiv-F_{\alpha}^{2}$. Thus, for
$\alpha\in\\{1,\ldots,t+1\\}$, one has

$\rho_{i}=\rho_{j+\alpha}\equiv-F_{\alpha}^{2}\equiv
F_{j}-F_{\alpha}^{2}=\rho_{j-\alpha}=\rho_{2j-i}.$

Finally, we prove that $\pi(F_{j},2)=2j$. By (4) we have

$F_{2j+1}^{2}-F_{2j}F_{2j+2}=(-1)^{2j}=1.$

Since $F_{2j}\equiv 0$, we have $F_{2j+1}^{2}\equiv 1$. By (2), it holds

$F_{i+2j}^{2}=(F_{i-1}F_{2j}+F_{i}F_{2j+1})^{2}\equiv
F_{i}^{2}F_{2j+1}^{2}\equiv F_{i}^{2}.$

Thus, the periodicity of ${\mathcal{F}}^{2}(F_{j})$ is at most, $2j$. Now, for
$i\in\\{1,\ldots,2j-1\\}$, the unique $i$ with $\rho_{i}=0$ is $i=j$. Since
$\rho_{j+1}=F_{j}-F_{1}^{2}=F_{j}-1\neq 1$, we have $\pi(F_{j},2)>j$. We
conclude $\pi(F_{j},2)=2j$. $\Box$

As examples of this, take $j=6$ so that $F_{6}=8$, $t=4$, and

$\begin{array}[]{ll}{\mathcal{F}}(F_{6})&=[0,1,1,2,3,5,0,5,5,2,7,1],\\\\[4.0pt]
{\mathcal{F}}^{2}(F_{6})&=[0,1,1,4,1,1].\end{array}$

For $j=7$ we have $F_{7}=13$, $t=6$, and

$\begin{array}[]{ll}{\mathcal{F}}(F_{7})&=[0,1,1,2,3,\phantom{1}5,\phantom{1}8,0,\phantom{1}8,\phantom{1}8,3,11,1,12,0,12,12,11,10,8,5,0,5,5,10,2,12,1],\\\\[3.0pt]
{\mathcal{F}}^{2}(F_{7})&=[0,1,1,4,9,12,12,0,12,12,9,\phantom{1}4,1,\phantom{1}1].\end{array}$

##  4 The power sequences ${\mathcal{F}}^{e}(F_{j})$

Consider first the special case $j=6$.

###### Proposition 4

  1. (i)

If $e\geq 1$ is odd, then $\pi(F_{6},e)=12$;

  2. (ii)

$\pi(F_{6},2)=6$, and if $e\geq 4$ is even, then $\pi(F_{6},e)=3$.

Proof. (i) Since $F_{6}=8$, a direct calculation gives

$\displaystyle{\mathcal{F}}(F_{6})$ $\displaystyle=[0,1,1,2,3,5,0,5,5,2,7,1],$
$\displaystyle{\mathcal{F}}^{2}(F_{6})$ $\displaystyle=[0,1,1,4,1,1],$
$\displaystyle{\mathcal{F}}^{3}(F_{6})$
$\displaystyle=[0,1,1,0,3,5,0,5,5,0,7,1],$
$\displaystyle{\mathcal{F}}^{4}(F_{6})$
$\displaystyle=[0,1,1,0,1,1,0,1,1,0,1,1]$ $\displaystyle=[0,1,1].$

It is clear that ${\mathcal{F}}^{4\alpha}(F_{6})=[0,1,1]$ for all integers
$\alpha\geq 1$. Note that $F_{i}^{4}\equiv 0$ if and only if $i\equiv
0\pmod{3}$, and if $F_{i}\not\equiv F_{i}^{3}$ then $i\equiv 0\pmod{3}$. Thus,

${\mathcal{F}}^{4\alpha+1}(F_{6})={\mathcal{F}}^{4\alpha}(F_{6}){\mathcal{F}}(F_{6})={\mathcal{F}}^{4\alpha}(F_{6}){\mathcal{F}}^{3}(F_{6})={\mathcal{F}}^{4\alpha+3}(F_{6}).$

If $e$ is odd, then $e=4\alpha+1$ or $e=4\alpha+3$ for some $\alpha\geq 1$ and
we have

$\displaystyle{\mathcal{F}}^{4\alpha+1}(F_{6})={\mathcal{F}}^{4\alpha+3}(F_{6})$
$\displaystyle=[0,1,1]\cdot[0,1,1,0,3,5,0,5,5,0,7,1]$
$\displaystyle=[0,1,1,0,3,5,0,5,5,0,7,1].$

Hence, for $e$ odd, we get $\pi(F_{6},e)=12$.

(ii) It is clear that $\pi(F_{6},2)=6$. If $e\geq 4$ is even, then $e=4\alpha$
or $e=4\alpha+2$ for some $\alpha\geq 1$. Since
${\mathcal{F}}^{4\alpha}(F_{6})=[0,1,1]$, we have

${\mathcal{F}}^{4\alpha+2}(F_{6})={\mathcal{F}}^{4\alpha}(F_{6})\cdot{\mathcal{F}}^{2}(F_{6})=[0,1,1]\cdot[0,1,1,4,1,1]=[0,1,1].$

Hence $\pi(F_{6},e)=3$ for all $e\geq 4$ even. $\Box$

Now we discuss the positions of $0$ in the sequence
${\mathcal{F}}^{e}(F_{j})$. To this end, we use the Carmicheal Theorem (see
[2] and [3], or [9]) applied to Fibonacci numbers:

######  Theorem 5 (Carmichael)

Let $j$ be an integer with $j\geq 3$ and $j\neq 12$. Then, there exists a
prime $p$ such that $p\mid F_{j}$ but $p\nmid F_{i}$ for all
$i\in\\{1,\ldots,j-1\\}$.

###### Proposition 6

Let $j$ and $e$ be integers such that $e\geq 1$ and $4\leq j\neq 6$. Then
$F_{i}^{e}\equiv 0\pmod{F_{j}}$ if and only if $i\equiv 0\pmod{j}$.

Proof. If $i\equiv 0\pmod{j}$, then $\gcd(i,j)=j$, which implies
$\gcd(F_{i},F_{j})=F_{j}$. Hence $F_{i}\equiv 0$ and $F_{i}^{e}\equiv 0$ for
all $e\geq 1$.

Conversely, assume $i\not\equiv 0\pmod{j}$. Consider first the special case
$F_{12}=144=2^{4}\cdot 3^{2}$. The prime factorizations of $F_{i}$ for
$i\in\\{1,\ldots,11\\}$ are the following:

$\begin{array}[]{r|lllllllllll}i&1&2&3&4&5&6&7&8&9&10&11\\\ \hline\cr
F_{i}&1&1&2&3&5&8=2^{3}&13&21=3\cdot 7&34=2\cdot 17&55=5\cdot
11&89\end{array}$

No $F_{i}$ in the table has both factors $2$ and $3$. Thus, $F_{i}^{e}$ has
not both factors $2$ and $3$. Hence $F_{i}^{e}\not\equiv 0\pmod{F_{12}}$.

Suppose $j\neq 12$. By Carmichael’s Theorem there exists a prime factor $p$ of
$F_{j}$ which is not a prime factor of $F_{i}$ for $i\in\\{1,\ldots,j-1\\}$.
Then $p$ is not a prime factor of $F_{i}^{e}$, and $F_{i}^{e}\not\equiv 0$.

If $i=qj+r$ with $q\geq 1$ and $1\leq r\leq j-1$, we have
$\gcd(F_{j},F_{qj})=F_{j}$. Then, $F_{qj}\equiv 0$ and, by (2),

$F_{i}=F_{qj+r}=F_{qj-1}F_{r}+F_{qj}F_{r+1}\equiv F_{qj-1}F_{r}.$

Since $\gcd(qj-1,j)=1$, it follows that $F_{qj-1}$ is a unit modulo $F_{j}$
and thus $F_{qj-1}^{e}$ is a unit too. Since $1\leq r<j-1$, by the previous
paragraph we have $F_{r}^{e}\not\equiv 0$. Thus,

$F_{i}^{e}\equiv F_{qj-1}^{e}F_{r}^{e}\not\equiv 0.\hskip 20.00003pt\Box$

###### Theorem 7

Let $j$ and $e$ be integers such that $j\geq 4$, $j\neq 6$, and $e\geq 1$.

  1. (i)

Assume that $j$ is even.

    1. (i.1)

If $e$ is even, then $\pi(F_{j},e)=j$;

    2. (i.2)

if $e$ is odd, then $\pi(F_{j},e)=2j$.

  2. (ii)

Assume that $j$ is odd.

    1. (ii.1)

If $e\equiv 0\pmod{4}$, then $\pi(F_{j},e)=j$.

    2. (ii.2)

if $e\equiv 2\pmod{4}$, then $\pi(F_{j},e)=2j$.

    3. (ii.3)

if $e$ is odd, then $\pi(F_{j},e)=4j$.

Proof. Due to Proposition 6, we know that $\pi(F_{j},e)$ is a multiple of $j$.

(i.1) Define $\alpha$ by $e=2\alpha$. We shall see that
$F_{i+j}^{2\alpha}\equiv F_{i}^{2\alpha}$ by induction on $\alpha$. For
$\alpha=1$, the result is true by Theorem 3. If $\alpha\geq 2$ and it is true
for $\alpha-1$, then

$F_{i+j}^{e}\equiv F_{i+j}^{2\alpha}=F_{i+j}^{2(\alpha-1)}F_{i+j}^{2}\equiv
F_{i}^{2(\alpha-1)}F_{i}^{2}=F_{i}^{2\alpha}=F_{i}^{e}.$

(i.2) Define $\alpha$ by $e=2\alpha+1$. To see that $\pi(F_{j},e)\geq 2j$ it
is sufficient to show that $F_{j+1}^{e}\not\equiv 1$. By Theorem 3, we have

$F_{j-1}^{2\alpha}=(F_{j-1}^{2})^{\alpha}=F_{1}^{\alpha}=1,$

and

$F_{j+1}^{e}=F_{j+1}^{2\alpha+1}=(F_{j}+F_{j-1})^{2\alpha+1}\equiv
F_{j-1}^{2\alpha+1}\equiv F_{j-1}^{2\alpha}F_{j-1}\equiv F_{j-1}\not\equiv 1.$

Thus, $\pi(F_{j},e)\geq 2j$. We shall see that $F_{i+2j}^{2\alpha+1}\equiv
F_{i}^{2\alpha+1}$ by induction on $\alpha$. For $\alpha=0$ the result is true
by Theorem 1. Assume $\alpha\geq 1$ and the result true for $\alpha-1$. By
(i.1) we have $F_{i+2j}^{2\alpha}\equiv F_{i}^{2\alpha}$. By Theorem 1, we
have $F_{i+2j}\equiv F_{i}$. Then,

$F_{i+2j}^{2\alpha+1}=F_{i+2j}^{2\alpha}F_{i+2j}\equiv
F_{i}^{2\alpha}F_{i}=F_{i}^{2\alpha+1}.$

(ii) Let $j=2t+1$.

(ii.1) Let $e=4\alpha$. It is enough to prove that $j$ is a period of
${\mathcal{F}}^{e}(F_{j})$.

Consider first the case $\alpha=1$; that is, $e=4$. By the identity (2), we
have

$0\equiv F_{j}=F_{2t+1}=F_{(t+1)+t}=F_{t}^{2}+F_{t+1}^{2}.$

Thus, $F_{t}^{4}\equiv F_{t+1}^{4}$. Then,
$\rho_{t}(F_{j},4)=\rho_{t+1}(F_{j},4)$. By Theorem 3, for
$i\in\\{t+2,\ldots,j-1\\}$, we have
$F_{i}^{4}\equiv(F_{j}-F_{j-i}^{2})^{2}\equiv F_{j-i}^{4}$. Thus, the first
$j$ terms of the sequence ${\mathcal{F}}^{4}(F_{j})$ are

$F_{0}^{4},F_{1}^{4},\ldots,F_{t-1}^{4},F_{t}^{4},F_{t}^{4},F_{t-1}^{4},\ldots,F_{1}^{4}.$

Since for $i\in\\{j+1,$…$,2j-1\\}$ we have
$\rho_{i}(F_{j},4)\equiv\rho_{i}(F_{j},2)^{2}=\rho_{2j-i}(F_{j},2)^{2}=\rho_{2j-i}(F_{j},4)$,
we see that $j$ is a period of $\mathcal{F}^{4}(F_{j})$. Hence
$\pi(F_{j},4)=j$. This implies $\pi(F_{j},4\alpha)=j$.

(ii.2) Let $e=4\alpha+2$. It is enough to prove that $j$ is not a period. We
shall see that $F_{j+1}^{e}\not\equiv F_{1}$. By Theorem 3, one has

$F_{j+1}^{2}\equiv\rho_{j-1}(F_{j},2)=F_{j}-F_{1}^{2}=F_{j}-1\equiv-1.$

By (ii.1), it follows $F_{j+1}^{4\alpha}\equiv F_{1}^{4\alpha}\equiv 1$. Then,

$F_{j+1}^{4\alpha+2}=F_{j+1}^{4\alpha}F_{j+1}^{2}\equiv-1\not\equiv F_{1}.$

Hence $j$ is not a period of ${\mathcal{F}}^{e}(F_{j})$. Therefore, we get
$\pi(F_{j},e)=2j$.

(ii.3) Let $e=2\alpha+1$. Since $\pi(F_{j},1)=4j$, we have
$\pi(F_{j},e)\in\\{j,2j,3j,4j\\}$. By (ii.1), it follows that
$F_{j+1}^{4\alpha}\equiv F_{1}^{4\alpha}=1$ and, by Theorem 1, we get
$F_{j+1}=F_{j-1}\not\equiv 1$. Then,

$F_{j+1}^{4\alpha+1}=F_{j+1}^{4\alpha}F_{j+1}\equiv
F_{j+1}=F_{2j-(j+1)}=F_{j-1}\not\equiv 1\,,$

and hence $\pi(F_{j},e)\neq j$.

Analogously, we find

$F_{2j+1}^{4\alpha+1}=F_{2j+1}^{4\alpha}F_{2j+1}\equiv F_{2j+1}\equiv
F_{j}-F_{2j+1-2j}=F_{j}-1\not\equiv 1.$

so that $\pi(F_{j},e)\neq 2j$.

Finally, from

$F_{3j+1}^{4\alpha+1}=F_{3j+1}^{4\alpha}F_{3j+1}\equiv F_{3j+1}\equiv
F_{4j-(3j+1)}=F_{j-1}\not\equiv 1\,,$

we can conclude that $\pi(F_{j},e)=4j$. $\Box$

## References

  * [1] D. M. Burton. _Elementary Number Theory_. Sixth Edition. McGraw Hill (2007).
  * [2] R. D. Carmichael. _On the Numerical Factors of the Arithmetical Form $\alpha^{n}\pm\beta^{n}$._ Annals of Mathematics. Second Series Vol 15 No. 1/4 (1913-1914) 30–48. https://www.jstor.org/stable/1967797
  * [3] R. D. Carmichael. _On the Numerical Factors of the Arithmetical Form $\alpha^{n}\pm\beta^{n}$._ Annals of Mathematics. Second Series Vol 15 No. 1/4 (1913-1914) 49–70. https://www.jstor.org/stable/1967798
  * [4] A. Ehrlich. _On the periods of the Fibonacci sequence modulo $m$._ The Fibonacci Quarterly 27 (1) (1989), 11–13.
  * [5] T. Koshy. _Fibonacci and Lucas Numbers with Applications, Vol. 1._ Second Edition. Wiley & Sons (2018).
  * [6] M. Renault. _The Fibonacci Sequence Under Various Moduli._ Master’s Thesis, Wake Forest University, (1996).
  * [7] M. Renault. _The Fibonacci Sequence Modulo $m$_.
https://webspace.ship.edu/msrenault/fibonacci/fib.htm

  * [8] N. N. Vorob’ev. _Fibonacci Numbers_. Pergamon Press (1961).
  * [9] M. Yabuta. _A Simple Proof of Carmichael Theorem on Primitive Divisors_. The Fibonacci Quarterly 39 (5) (2001), 439–443.