Exercise 4.4.22* (Congruences in the Fibonacci sequence)

Proof.

We treat separately the case $p=2$. If $p=2$, then $F_2=1$ and $\left(\frac{2}{5}\right)=-1$, so $F_2\equiv \left(\frac{2}{5}\right)(\mathit{mod}2)$. We prove by induction that

• $F_0=0\equiv 0(\mathit{mod}2)$ and $F_1=F_2=1\equiv 1(\mathit{mod}3)$.

• Suppose now that $𝒫(k)$ is true. Then

  $$\begin{array}{lll}\hfill F_{3k+3}=F_{3k+2}+F_{3k+1}\equiv 1+1\equiv 0(\mathit{mod}2),& & \hfill \\ \hfill F_{3k+4}=F_{3k+3}+F_{3k+2}\equiv 0+1\equiv 1(\mathit{mod}2),& & \hfill \\ \hfill F_{3k+5}=F_{3k+4}+F_{3k+3}\equiv 1+0\equiv 1(\mathit{mod}2).& & \hfill \end{array}$$

  Thus $𝒫(k+1)$ is true, and the induction is done.

In conclusion

Therefore the results of the problem are true for $p=2$, in the case $p\equiv 2(\mathit{mod}5)$. In particular $6=2p+2$ is a period, but not the least period.

In the rest of the problem we suppose that $p$ is an odd prime.

(a)

We note that $F_p=U_p(1,1)$. The associate discriminant $D$ of $x^2-x-1$ is $D=5$. Then Problem 20 gives

$$F_p\equiv \left(\frac{5}{p}\right)(\mathit{mod}5).$$

(b)

By the law of quadratic reciprocity, $$\left(\frac{5}{p}\right)=\left(\frac{p}{5}\right).$$

Therefore,

$$\begin{array}{llll}\hfill & \left(\frac{5}{p}\right)=1⟺\left(\frac{p}{5}\right)=1⟺p\equiv \pm 1(\mathit{mod}5),& \hfill & \\ \hfill & \left(\frac{5}{p}\right)=-1⟺\left(\frac{p}{5}\right)=-1⟺p\equiv \pm 2(\mathit{mod}5).& \hfill & \end{array}$$

• If $p\equiv \pm 1(\mathit{mod}5)$, then $\left(\frac{5}{p}\right)=\left(\frac{D}{p}\right)=1$. By Problem 19,

  $$F_{p+1}\equiv 1(\mathit{mod}p).$$

• If $p\equiv \pm 2(\mathit{mod}5)$, then $\left(\frac{5}{p}\right)=\left(\frac{D}{p}\right)=-1$. We proved in the solution of Problem 19 that

  $$2U_{p+1}(a,b)\equiv a\left(1+\left(\frac{D}{p}\right)\right)(\mathit{mod}p).$$

  Therefore

  $$2F_{p+1}\equiv \left(1+\left(\frac{D}{p}\right)\right)\equiv 0(\mathit{mod}p).$$

  Since $p$ is odd,

  $$F_{p+1}\equiv 0(\mathit{mod}p).$$

In conclusion,

$$\begin{array}{lll}\hfill F_{p+1}\equiv 1(\mathit{mod}p)& \text{ if }p\equiv \pm 1(\mathit{mod}5),& \hfill \text{(1)}\\ \hfill F_{p+1}\equiv 0(\mathit{mod}p)& \text{ if }p\equiv \pm 2(\mathit{mod}5),& \hfill \text{(2)}\end{array}$$

(c)

• If $p\equiv \pm 1(\mathit{mod}5)$, then $\left(\frac{D}{p}\right)=\left(\frac{5}{p}\right)=1$. By Problem 21, since $b=1$

  $$F_{p-1}=U_{p-1}(1,1)=b{U}_{p-1}(1,1)\equiv 0(\mathit{mod}p).$$

• If $p\equiv \pm 2(\mathit{mod}5)$, then $\left(\frac{D}{p}\right)=\left(\frac{5}{p}\right)=-1$. By the congruence (9) in the solution of Problem 21, using $a=b=1$

  $$F_{p-1}=b{U}_{p-1}(a,b)\equiv a=1(\mathit{mod}p).$$

  In conclusion,

  $$\begin{array}{lll}\hfill F_{p-1}\equiv 0(\mathit{mod}p)& \text{ if }p\equiv \pm 1(\mathit{mod}5),& \hfill \text{(3)}\\ \hfill F_{p-1}\equiv 1(\mathit{mod}p)& \text{ if }p\equiv \pm 2(\mathit{mod}5),& \hfill \text{(4)}\end{array}$$

(d)

• If $p\equiv \pm 1(\mathit{mod}5)$, then by (3), $F_{p-1}\equiv 0(\mathit{mod}p)$. We will prove that $p-1$ is a period modulo $p$, i.e. $F_{i+p-1}\equiv F_i$ for all $i\in \mathbb{N}$.

  • First proof, with my methods.

    Here we write $\bar{a}$ the class of $a\in \mathbb{Z}$ in $\mathbb{Z}∕\mathit{p\mathbb{Z}}$.

    As in the second solution of Problem 19, consider the sequence ${(f_n)}_{n\in \mathbb{N}}$ defined for all $n$ by $f_n=\overline{F_n}\in \mathbb{Z}∕\mathit{p\mathbb{Z}}$, so that

    $$\begin{array}{lll}\hfill \begin{array}{cc}{f}_{n+2}\hfill & =f_{n+1}+f_n,\hfill \\ \hfill \end{array}\begin{array}{c}{f}_0=\bar{0},f_1=\bar{1},\hfill \\ \hfill \end{array}& & \hfill \text{(5)}\end{array}$$

    Here $\left(\frac{5}{p}\right)=1$, thus there exists $\delta \in {𝔽}_p^{\text{∗}}$ such that ${\delta }^2=\bar{D}=\bar{5}$, so there are two distinct roots $\alpha ,\beta \in {𝔽}_p$ of $x^2-x-1\in {𝔽}_p[x]$.

    By induction, we obtain for all $n\in \mathbb{N}$,

    $$\begin{array}{lll}\hfill f_n=\frac{{\alpha }^n-{\beta }^n}{\alpha -\beta }.& & \hfill \text{(6)}\end{array}$$

    Here $\mathit{\alpha \beta }=\bar{1}$, thus $\alpha \ne \bar{0},\beta \ne \bar{0}$. By Fermat’s theorem, ${\alpha }^{p-1}={\beta }^{p-1}=\bar{1}$. Therefore

    $$f_{i+p-1}=\frac{{\alpha }^{i+p-1}-{\beta }^{i+p-1}}{\alpha -\beta }=\frac{{\alpha }^i-{\beta }^i}{\alpha -\beta }=f_i.$$

    This shows that for all $i\in \mathbb{N}$,

    $$F_{i+p-1}\equiv F_i(\mathit{mod}p).$$

  • Second proof, with the methods of Lucas (for which I have great respect and admiration).

    If $\lambda ,\mu$ are the complex roots of $x^2-x-1$, then $F_n=({\lambda }^n-{\mu }^n)(\lambda -\mu )$. We define

    $$\begin{array}{llll}\hfill U_n& =U_n(1,1)=\frac{{\lambda }^n-{\mu }^n}{\lambda -\mu }=F_n,& \hfill & \\ \hfill V_n& =V_n(1,1)={\lambda }^n+{\mu }^n.& \hfill & \end{array}$$

    We need an addition formula: for all $n,m\in \mathbb{N}$,

    $$\begin{array}{lll}\hfill 2U_{n+m}=U_n{V}_m+V_n{U}_m.& & \hfill \text{(7)}\end{array}$$

    Indeed,

    $$\begin{array}{llll}\hfill U_n{V}_m+V_n{U}_m& =\frac{{\lambda }^n-{\mu }^n}{\lambda -\mu }({\lambda }^m+{\mu }^m)+({\lambda }^n+{\mu }^n)\frac{{\lambda }^m-{\mu }^m}{\lambda -\mu }& \hfill & \\ \hfill & =\frac{{\lambda }^{n+m}-{\mu }^{n+m}}{\lambda -\mu }& \hfill & \\ \hfill & =2U_{n+m}.& \hfill & \end{array}$$

    By (3), $U_{p-1}=F_{p-1}\equiv 0(\mathit{mod}p)$. By the formula (5) in the solution of Problem 21, since $\left(\frac{D}{p}\right)=1$, we know that $V_{p-1}\equiv 2(\mathit{mod}p)$. Then, using (7),

    $$\begin{array}{llll}\hfill 2U_{i+p-1}& =U_i{V}_{p-1}+V_i{U}_{p-1}& \hfill & \\ \hfill & \equiv 2U_i(\mathit{mod}p)& \hfill & \end{array}$$

    Since $p$ is an odd prime, $U_{i+p-1}\equiv U_i(\mathit{mod}p)$, so for all $i\in \mathbb{N}$.

    $$F_{i+p-1}\equiv F_i(\mathit{mod}p).$$

• If $p\equiv \pm 2(\mathit{mod}5)$, by (2), $F_{p+1}\equiv 0(\mathit{mod}p)$. We will prove that $2p+2$ is a period modulo $p$, i.e. $F_{i+2p+2}\equiv F_i$ for all $i\in \mathbb{N}$.

  Here $\left(\frac{D}{p}\right)=-1$, then as in Problem 20, $\bar{D}=\bar{5}$ has a square root $\delta$ in some quadratic extension $K$ of ${𝔽}_p$ with $p^2$ elements. Let $\alpha$ and $\beta$ be the distinct roots of $p(x)$ in $K$. Then formulas (5) and (6) remain true and by the second proof of Problem 20,

  $${\alpha }^p=\beta ={\beta }^p=\alpha .$$

  Therefore, for all $i\in \mathbb{N}$,

  $$\begin{array}{llll}\hfill f_{i+p+1}& =\frac{{\alpha }^{i+p+1}-{\beta }^{i+p+1}}{\alpha -\beta }& \hfill & \\ \hfill & =\frac{\beta {\alpha }^{i+1}-\alpha {\beta }^{i+1}}{\alpha -\beta }& \hfill & \\ \hfill & =\mathit{\alpha \beta }\frac{{\alpha }^i-{\beta }^i}{\alpha -\beta }& \hfill & \\ \hfill & =-f_i,& \hfill & \end{array}$$

  so $f_{i+p+1}=-f_i$ for all $i$, thus $f_{i+2p+2}=-f_{i+p+1}=f_i$. Therefore

  $$F_{i+2p+2}\equiv F_i(\mathit{mod}p).$$

  So $2p+2$ is a period modulo $p$ of the sequence ${(F_n)}_{n\in \mathbb{N}}$ (note that $p+1$ is an anti-period, if this word exists).

  (We leave the proof with Lucas’s methods to the patient reader.)