How Fermat discovered his theorem.

I refer my reader to André Weil (Section 4, Chapter 2, of his Number Theory) or Harold Edwards (Section 1, Chapter 1, of his Fermat's Last Theorem).

Fermat's discovery of his little theorem was a direct outcome of his investigations concerning Euclid's theorem on perfect numbers. More specifically it originated from his investigations into the question of the primality or otherwise of ( ).

On occasion we say things to our students like : I'm not sure how such-and-such first happened, was discovered, but I think it happened like this... For example, I find myself telling my students how I think Euclid could have discovered his famous theorem on perfect numbers. Also, many years ago, I used to (wrongly) tell how I thought Fermat had discovered his 'little' theorem... ; I thought he had found it by thinking about the decimal expansions of rational numbers. In Section 2 I consider decimal and other expansions, and there you will see how anyone could have formulated Fermat's little theorem had he/she simply asked the right questions having investigated decimal expansions of certain rational numbers.

Fermat was led to formulate his theorem via Euclid's theorem on perfect numbers:

if ( ) is prime then is perfect

One of my Maple delivered public lectures - The recently discovered record Mersenne prime (from 1995, and available at my web site) - treats the subject of abundant, deficient and perfect numbers, the Euclid theorem, etc - but here suffice it to say that before the mid 1450's it was believed that ( ) is prime if and only if n itself is prime, a result blown away by the observation that:

= 23*89 ... ( i )

Of course it is trivial that ( ) is composite if n is composite, and so the real interest is in the Mersenne numbers { }, where , p prime. is prime for , ... , and is composite for , ... Before Fermat (1640) nothing had been investigated beyond those p 's just shown, and it was Fermat who noted that:

= *178481 ... ( ii )

One would need to be incredibly numerically insensitive not to notice that '47' is so obviously related to '23':

*

Ones eye gets pulled back to the earlier ( i ) and notices exactly the same phenomenon :

*

But a great mistake for anyone to make, looking at this ab initio , would be to rush in and wonder/declare:

whenever is composite, its least prime divisor q satisfies

For see what happens with the next prime after 23:

> restart;

> p := 29;

> M[p] := 2^p - 1;

> ifactor(M[p]);

>

and so what did Fermat notice? Simply that not only is (returning to (i)) * , but also

*

and, with (ii), not only is (returning to (i)) * , but also

*

In short, one might say that Fermat discovered (then conjectured) what one might call the Fermat-Euler theorem on prime divisors of the Mersenne numbers: for prime p every prime divisor q of satisfies:

(mod p )

But it wasn't that alone that Fermat noticed, for he went one step further (he didn't have congruence terminology, but in that language this is what he observed):

One has (mod 23), and so (squaring, cubing, etc) one has:

etc (are all) = 1 (mod 23)

One has (mod 89), and so (squaring, cubing, etc) one has:

, ... , etc (are all) = 1 (mod 89)

One also has (looking at case (ii)) (mod 47), and so (squaring, cubing, etc) one has:

etc (are all) = 1 (mod 47)

One also has (looking at case (ii)) (mod 178481), and so (squaring, cubing, etc) one has:

, ... , , etc (are all) = 1 (mod 178481)

What I am trying to draw attention to is that for each of the above primes p one has (mod p ) for various values of m , but that in all cases one of those m 's is ( ).

In short, for the primes one has

(mod p )

But, is this true for other primes? Yes, of course it is (or appears to be), , of course:

> for r to 15 do
[ithprime(r), 2^(ithprime(r)-1), 2^(ithprime(r)-1) mod ithprime(r)]
od;
# the reason for the '0' in the 1st output is obvious:

>

And what about changing that '2' to , etc?

> for r to 15 do
[ithprime(r), 3^(ithprime(r)-1), 3^(ithprime(r)-1) mod ithprime(r)]
od;
# the reason for the '0' in the 2nd output is obvious:

etc. In short, one comes to suspect that (mod p ) providing, of course, that (mod p ), namely Fermat's little theorem .