Date: Sun, 1 Oct 95 23:13:32 CDT
From: rusin (Dave Rusin)
To: sivak-d@cs.buffalo.edu
Subject: Re: Analogue of Fermat for Matrix Groups?
Newsgroups: sci.math
[Was: can you generalize Fermat's little theorem to matrix groups]

Sure. Fermat's little theorem is nothing but Lagrange's theorem
specialized to the group  Z_p^*. So what you want to do is ignore
Fermat and listen to Lagrange: every element of  GL_n(F_p) has
order dividing the order of  GL_n(F_p). At the level of your question
I would say the order of this group would be considered hard or
messy, but when  n=2  it's not so bad; the conclusion is that for
every 2 x 2 invertible matrix  M  over  F_p,  we have  M^k = I  if
k=(p^2-1)*(p^2-p).

Actually you can do a bit better with some matrix theory behind you:
if the eigenvalues of  M  are distinct, then  M  is conjugate to
(and thus has the same order as) a diagonal matrix. If  D=diag(a,b)
is a diagonal 2x2 matrix, its order is the lcm of the orders of
a and b. By Fermat, this is at worst  (p-1)  if  a and  b  lie in
F_p. If they lie in an extension field, they'll have the same order and
it will divide  p^2-1. (Elements with precisely this order exist).

If the eigenvalues of  M   are not distinct,  M  might still be diagonalizable,
so this discussion applies. If not, it has some element  b  actually from F_p
on its diagonal and a  1  above the diagonal (not  M, I mean a conjugate
matrix.). To get the diagonal elements equal to  1, you need to raise
to the  (p-1)  power (at least for the worst  b's you do); then to get rid
of what's above the diagonal you will in general have to raise to the  p-th
power, giving elements of order dividing and including  p^2-p.

So the smallest exponent you could use for your theorem would be the lcm
of these two numbers  p^2-1=(p-1)(p+1) and (p^2-p)=p*(p-1), which is 
clearly  p(p-1)(p+1).

Naturally the situation gets even more cumbersome with matrices larger
than  2 x 2.

dave