From: colin@nyx10.nyx.net (Colin Plumb)
Newsgroups: sci.math
Subject: Re: Fermat's Little theorem
Date: 25 Sep 1997 05:21:46 -0600
Organization: University of Denver, Dept. of Math & Comp. Sci.

>> I have just made the acquaintance of Fermat's Little theorem
>>
>> If p is prime and does not divide another integer a.
>>
>>              Then a^(p-1) = 1 mod(p)
>>
>>
>> Unlike Fermat's last theorem this theorem is supposed to be provable
>> in a few lines.
>>
>> I am wondering if the proof requires advanced maths or whether it is
>> accessible to a novice like myself?

Here's a *really* elementary proof.

Mathematicians like to imagine things and give them names and then prove
things about them.  Often, it turns out that an example of the thing
that they imagined appears somewhere and thus the proofs are useful.

Anyway, one of these things is a group.  A group is a set of elements,
which I'll call G, and a binary operation, *, that combines members of
the set, which obey certain properties.  Also, the size of G is called
the order of the group.  If this is finite, the group is called a
finite group.

Now, if the set is *closed* under the binary operation, that
is for all a and b in G, a*b is also in G, the result is called
a module, although this isn't a very widely used term.

There's a really important property, which I forget where it's introduced
(modules, monoids or groups), of associativity.  Anyway, the operation
must obey the rule that for all a, b and c in G, (a*b)*c = a*(b*c).
At the risk of messing up my terminology, I'll say that a module
must also have this property.

This is a very useful property, as it means that I can just write
a*b*c, and not worry about the order in which the multiplies get done.
I can even write a*b*c*d*e, or a*a*a*a*a.  The latter will be useful in
a bit.

If a module also contains an identity element, which I'll write as 1,
such that for all a in G, 1*a = a*1 = 1, then we have a monoid.

If every element of a monoid has an *inverse*, that is for all a in G
there exists b in G such that a*b = b*a = 1, then we have a group.

A group is a very important structure, because it's simple enough to be
common, but has enough rules that you can prove lots of very
interesting things sbout groups.  Modules and monoids are very dull
in comparison.

If the order of the operations doesn't matter, that is, for all a and b
in G, a*b = b*a, then the group is called commutative, or abelian.  The
you're looking at above are an abelian group, although that is not used
much in the proofs.

Now, multiplying non-zero numbers modulo a prime p is a group.
How do we know it's a group?  By verifying that it obeys all
the identities.  G is the set {1, 2, 3, ..., p-1}, and * is the
operation of multiplication modulo p.  (Purists will tell me
that G is the set of non-zero equivalence classes modulo p,
which is more correct, but takes longer to explain.)

a*b is in G unless the result is a multiple of p (in which case it's
zero, modulo p, and that is excluded from G).  Since p is prime, this
can only happen if either a or b is already a multiple of p.  But
multiples of p aren't in G, so this can't happen.  Thus, the operation
is closed.

Associativity comes trivially from the associativity of multiplication
that you learned about in elementary school (I hope).

The existence of an identity is hopefully obvious.  It's 1.

As for inverses, consider any a in G, i.e. any 1 <= a <= p-1.  Now
consider 1*a, 2*a, ... (p-1)*a.  Suppose that two of these were equal,
i.e. c*a = d*a (mod p), where 1 <= c < d <= p-1.  then (d-c)*a = 0 (mod
p), but 1 <= d-c <= p-1, and 1 <= a <= p-1, which is impossible if p is
prime.  So 1*a, 2*1, ... (p-1)*a must all be different, and since you
have p-1 products which each have a distinct value from a set of p-1,
all posible values in the set must be used (the pigeonhole principle),
and one of theose values must be 1.  Thus, somewhere in that list is a
b (and exactly one possible b) such that b*a = 1.  (Since this is an
abelian group, checking that b*a = a*b is trivial.)

This pigeonhole principle of multiplication by some constant a is very
important.  We'll use it again in just a second.

But first, let me define the order of an element.  Consider the series
a, a*a, a*a*a, etc., which can be written a^1,a^2, a^3, etc.  (Note
that the exponent is an integer, *NOT* an element of the group!)
Define the least k>0 such that a^k = 1 as the *order* of a.  If there is
no such k, the order is defined as zero.  (It's convenient to define
a^0 as 1 for all a.  a can't be sero, so the question of 0^0 doesn't
come up.)

Now, members of finite groups (groups with a finite set of members G)
always have non-zero order.  In the series a^1, a^2, a^3, etc., since
there are only finitely many possible values, there must come a repetition,
a^m = a^n, for m < n.  But a^n = (a^m)*(a^(n-m)), so a^(n-m) = 1, for
some n-m >= 1.  Once you've hit 1, then clearly the series just repeats
as you get a^(n-m), a^(n-m+1), ... = 1, a^1, a^2, etc.

Also, hopefully it is clear that until the first 1 in the series, there
are no repetitions.  If there were, then an earlier 1 in the series
would have to exist.

Now comes the biggest result, of which Fermat's little theorem is a corollary.
# In a finite group, the order of an element divides the order of the group.

The proof of this does as follows:

For any element a of G, consider the cyclic series a, a^2, a^3, ... 1.
This has some length k until it becomes 1 and repeats which is the order of a.

Now, if k is the same as the order of the group, then the series
contains every element of G, and clearly the order divides.

But if k is less than g, then there is some element b in G which is not
in the series.  Thus, b*a, b*a^2, b*a^3, ..., b*1 are all distinct
elements of G, none of which are in the series so far.  If they were,
then b would have been seen.

If there are any elements of G which still have not been seen, choose
some c and list c*a, c*a^2, ... c.  Again, none of these values has
appeared in any of the previous series.  (Is there a plural of series?)

Repeat as often as necessary until you run out of group members.  Since
G is finite, you will eventually.  You will have divided all of the
elements of G up into series of length k, with no overlaps between the
series and no elements missing.  Thus, the number of elements is
divisible by k.  Thus, k divides the order of the group.


Given this, it should be easy to see where Fermat's little theorem
comes from.   Your number a, since it's not divisible by p (i.e. not
zero, modulo p) is in the group, and has some order, a value k such
that a^k = 1 (mod p).  This value k divides the order of the group,
p-1.  Thus, a^(p-1) = (a^k)^((p-1)/k) = 1^((p-1)/k) = 1 (mod p).

QED.

Now, that was a bit long-winded, but used, as far as I know, only
very elementary mathematics.  The most sophisticated things used
were associativity and the pigeonhole principle.

(Now all the real mathematicians will hopefully tell me where my
explanation is flawed.  I just like this because it's very concrete and
easy to visualize, lining up all of the elements of G in rows and
columns.)
-- 
	-Colin