Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

closed as off-topic by Jonas Meyer, Tunk-Fey, 5xum, gekkostate, William Aug 5 at 8:26

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Jonas Meyer, Tunk-Fey, 5xum, gekkostate, William
If this question can be reworded to fit the rules in the help center, please edit the question.

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

1 Answer 1

up vote 3 down vote accepted

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})$.

share|improve this answer
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. –  J. M. 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

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