10
$\begingroup$

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?

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

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.

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

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...

$\endgroup$
  • $\begingroup$ 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)$? $\endgroup$ – Hyperbolic Marraquetoid Jan 28 '17 at 0:28
  • $\begingroup$ @Stefan: sure it is. The determinant is $-4 \equiv -1 \bmod 3$. $\endgroup$ – Qiaochu Yuan Jan 28 '17 at 0:31
  • 1
    $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Jan 28 '17 at 0:32
  • $\begingroup$ @QiaochuYuan Then I have misunderstood the problem, I thought that the determinant is $\pm 1$, not $\pm 1$ modulo $p$. $\endgroup$ – Stefan4024 Jan 28 '17 at 0:32
  • 2
    $\begingroup$ @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. $\endgroup$ – Qiaochu Yuan Jan 28 '17 at 1:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.