# Proving property of Fibonacci sequence with group theory

I stumbled upon this problem on a chapter about group theory, and I can't seem to get a grasp on it:

Let $p$ be a prime and $F_1 = F _2 = 1, F_{n +2} = F_{n +1} + F_n$ be the Fibonacci sequence. Show that $F_{2p(p^2−1)}$ is divisible by $p$.

The book gives the following hint:

Look at the group of $2×2$ matrices mod $p$ with determinant $± 1$

I know I have to use lagrange theorem at some point, but how do I stablish the link between the fibonacci sequence and the matrices? I mean, I know that there's a special $2×2$ matrix such that it yields the $n^{th}$ fibonacci number when taking the $n^{th}$ power, I even used it to obtain a general formula for the numbers during my linear algebra course, but how can I use that to prove this?

• Do you mean $F_{2p(p^2−1)}$ is divisible by $p$? – Rutger Moody Jan 27 '17 at 23:40
• @RutgerMoody yes, my bad – Hyperbolic Marraquetoid Jan 27 '17 at 23:41
• Also this i suppose:$F_1 = F _2 = 1, F_{n +2} = F_{n +1} + F_n$ – Rutger Moody Jan 27 '17 at 23:48
• @RutgerMoody yes, thank you – Hyperbolic Marraquetoid Jan 27 '17 at 23:49

Call the group $G = \left\{A \in (\mathbb{Z}/p\mathbb{Z})^{2\times 2} \ \middle\vert\ \det A = \pm 1\right\}$.

First, we count the order of $G$. We have elements $\left(\array{a & b \\ c & d}\right)$, with $a,b,c,d \in \mathbb{Z}/p\mathbb{Z}$ and $ad - bc \equiv \pm 1$ ($\equiv$ means congruent modulo $p$). Let us first count the elements with determinant one. $\mathbb{Z}/p\mathbb{Z}$ is a field, which means that every element except $0$ has a multiplicative inverse. Therefore, $ad - bc \equiv 1$ is equivalent to $(d \equiv 0\ \land\ c \equiv -b^{-1})\ \lor\ (a \not\equiv 0 \land d \equiv a^{-1}(1 + bc))$. Counting the possibilities gives $$\underbrace{(d \equiv 0\ \land\ c \equiv -b^{-1})}_{\text{a: p choices, b: p - 1 choices}}\ \lor\ \underbrace{(a \not\equiv 0 \land d \equiv a^{-1}(1 + bc))}_{\text{a: p - 1 choices, b,c: p choices}}$$ for a total of $p(p-1) + (p-1)p^2 = p(p+1)(p-1) = p(p^2 - 1)$ elements with determinant $1$. By symmetry (swapping $a$ with $b$ and $d$ with $c$) there has to be an equal number of elements with determinant $-1$. So the order of $G$ is $|G| = 2p(p^2 - 1)$.

Now, let $M = \left(\array{1 & 1 \\ 1 & 0}\right)$. You already know that $M^n = \left(\array{F_{n+1} & F_{n} \\ F_{n} & F_{n-1}}\right)$. For $M$, as for any element in a finite group, we know that $M^{|G|} = I$ (consider the cyclic subgroup $\left<M\right>$ generated by $M$ and use Lagrange's theorem). This fact translates to $$\left(\array{F_{2p(p^2 - 1) + 1} & F_{2p(p^2 - 1)} \\ F_{2p(p^2 - 1)} & F_{2p(p^2 - 1) - 1}}\right) \equiv \left(\array{1 & 0 \\ 0 & 1}\right) \mod{p}.$$ The off-diagonal components of this equation are what you wanted to show.

• I made some off-by-one errors which I have now corrected. Most notably, $M^{|G|}$ is the identity element $I$ and not $M$! – Elias Riedel Gårding Jan 28 '17 at 1:28

The matrix $\left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right]$ has the property that its powers encode Fibonacci numbers. It lives in the group of $2 \times 2$ matrices $\bmod p$ with determinant $\pm 1$ (a certain subgroup of $GL_2(\mathbb{F}_p)$). If you count the size of this group...

• I see, if the size of the group is $2p(p^2-1)$ then the matriz to that power will yield the identity matrix by lagrange's theorem, and then I will be done. But, how do I deduce that the size of the group is actually $2p(p^2-1)$? – Hyperbolic Marraquetoid Jan 28 '17 at 0:28
• @Stefan: sure it is. The determinant is $-4 \equiv -1 \bmod 3$. – Qiaochu Yuan Jan 28 '17 at 0:31
• @Hyperbolic: do you know how to compute the size of $GL_2(\mathbb{F}_p)$? One way to do it is by first picking the first column of a matrix in the group, then the second. From there, you can compute the size of $SL_2(\mathbb{F}_p)$, and then I claim this group is exactly twice as big. – Qiaochu Yuan Jan 28 '17 at 0:32
• @QiaochuYuan Then I have misunderstood the problem, I thought that the determinant is $\pm 1$, not $\pm 1$ modulo $p$. – Stefan4024 Jan 28 '17 at 0:32
• @Stefan: when I say the matrices have entries $\bmod p$ I mean that any arithmetic operations I perform on the entries of the matrices should be performed $\bmod p$, including computing their determinant. – Qiaochu Yuan Jan 28 '17 at 1:03