# Fibonacci numbers application

I need to find how many non-singular 2*2 matrices there are (mod n). These form a group G, under multiplication. Then the Fibonacci matrix generates a subgroup whose order is a factor of the order of G. The order of the subgroup is the period of divisibility by n. I am looking for a proper solution of the above statement.

-
(-1) "This question does not show any research effort." –  The Chaz 2.0 Sep 2 '11 at 17:48

I am a little puzzled by what Fibonacci matrices have to do with the problem of computing the order of the group $G_n = \operatorname{GL}_2(\mathbb{Z}/n\mathbb{Z})$. (Added: To be honest I am not quite sure what "the Fibonacci matrix is", though I have in my time seen some $2 \times 2$ matrices with Fibonacci numbers as entries. Anyway, if it's just one matrix, it generates a cyclic subgroup of $G_n$, which is therefore a very small subgroup of the non-abelian group $G_n$.) As you say, your special matrices will generate some subgroup $F_n$ of $G_n$, so if you can compute the order of $F_n$ you know that the order of $G_n$ will be a multiple of the order of $F_n$. But how does that help?

Anyway, here are some hints for how to compute the order of $G_n$.

Step 1: Do the case $n = p$ is prime. Then you are just counting the number of ordered bases of a $2$-dimensional vector space over the finite field $\mathbb{F}_p$, so your first vector can be any nonzero vector and your second vector can be any vector which is not a multiple of the first vector.

Step 2: Do the case $n = p^k$ is a prime power. Here you can use the fact that an element of $\operatorname{GL}_2(\mathbb{Z}/p^k)$ is invertible iff its determinant is a unit in $\mathbb{Z}/p^k$ iff its determinant is nonzero modulo $p$. So you just need to compute how many elements of $\operatorname{GL}_2(\mathbb{Z}/p^k)$ reduce mod $p$ to any given element of $\operatorname{GL}_2(\mathbb{Z}/p\mathbb{Z})$, and this is easier than it may sound.

Step 3: If $m$ and $n$ are coprime, then it follows from the Chinese Remainder Theorem that $\operatorname{GL}_2(\mathbb{Z}/mn\mathbb{Z}) \cong \operatorname{GL}_2(\mathbb{Z}/m\mathbb{Z}) \times \operatorname{GL}_2(\mathbb{Z}/n \mathbb{Z})$.

-
I thought the Fibonacci matrix was $\begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix}$, the n-th power of which has $F(n+1)$ in the top left and $F(n)$ in the top right and lower left entries. –  The Chaz 2.0 Sep 2 '11 at 17:47
(and $F(n-1)$ is in the lower right...) –  The Chaz 2.0 Sep 2 '11 at 17:52
The usage of "Fibonacci matrix" I've seen both corresponds to the one in Chaz's comment and also the matrix with Fibonacci number entries. I haven't seen both senses simultaneously used in an article however. –  Ｊ. Ｍ. Sep 2 '11 at 17:56
@The Chaz: thanks, I agree that's probably the matrix the OP means. But...can you tell whether I've answered his question or not? I'm not so sure myself. –  Pete L. Clark Sep 2 '11 at 18:08
Pete: I suspect what is going on here is that the original poster has tried to rewrite a homework problem (good!) and made it much less clear (bad!). In particular, here is a problem that I have seen assigned in the past: Introduce the Fibonnaci matrix, as in The Chaz's first comment. Prove that its powers are Fibonacci numbers. Compute the order of $GL_2(Z/p)$. Using Lagrange's theorem, deduce that the Fibonacci's mod $p$ repeat with period dividing $|GL_2(Z/p)|$. Extra credit: show that the period always divides either $p-1$ or $p+1$, and give a rule for when which of these occurs. –  David Speyer Sep 2 '11 at 18:23