The theorem itself.

According to Dickson (and others; see Bibliography) Fermat first announced his theorem in a letter to Mersenne, June (?), 1640.

Fermat's 'little' theorem. Let p be prime, and a be any integer with (mod p ), then

(mod p )

In non-congruence language: let p be any prime, and a be any integer not divisible by p , then leaves remainder 1 on division by p .

A small hand performed illustration. Let and , then = * .

Maple examples (the meaning of each command should be clear).

> restart;

> p[1] := nextprime(120);

> a[1] := 2;

> 57 mod 5; # the remainder 57 leaves on division by 5

> a[1]^(p[1] - 1);

> a[1]^(p[1] - 1) mod p[1];

> p[2] := nextprime(10^20 + rand());

> a[2] := rand(); # Maple has a 12-digit random number generator:

> a[2] mod p[2];

> a[2]^(p[2] - 1);

Error, integer too large in context

That expected, and intentional output can be overcome by using the so-called square-and-multiply method which is incorporated into a Maple command by the use of '&' as follows. (The mathematics of that command, the so-called square-and-multiply method - modular exponentiation - is covered in a Maple worksheet at my web site. It forms part of my 3rd year course on Number Theory and Cryptography.)

> a[2]&^(p[2] - 1) mod p[2];

And let's just see the values :

> 2&^(p[2] - 1) mod p[2];

> 3&^(p[2] - 1) mod p[2];

> 5&^(p[2] - 1) mod p[2];

>

Anyone who already knows some Number Theory will understand why I didn't check that

(mod )

It is an automatic consequence of

(mod )

as indeed

(mod )

is a consequence of

(mod ) and (mod )

and now consider this:

> p := 10^80*rand()^2 + 20! + 2*rand() + 127;

> length(p);

Could that p be a prime? Let's see: if p is prime then automatically we have (mod p ), etc.

So, let's calculate;

> 2&^(p - 1) mod p;

>

Ah! So it isn't, since the output was not 1. I hope you realise how powerful that calculation is, for in a microsecond it has determined that the above p is composite.

Question . But what if the output had been '1'? What then? Would it follow that p is prime? If you don't already know the answer to that question, then you might like to think about it before you read Section 4 (Primality Testing).

Software Note . The above fast computation might appear impressive, but for seriously large numbers - ones with hundreds of thousands, or several million digits - Maple is, quite simply , absolutely useless . For seriously large numbers a user must avail of remarkable public-domain programs like:

prime95.exe (George Woltman's GIMPS project)

Everyone will know that George's program has found - on desktop computers - the last four record sized Mersenne primes (most earlier ones had been found on CRAY supercomputers), the most recent of which is the only known prime with more than a million digits.

proth.exe (Yves Gallot's Proth project)

In July 1999 - using Yves' program - I had the good fortune to find the 115130 digit prime 3* (the then largest known prime), and a factor of the (then, and still ) largest known composite Fermat number:


That prime proved to be a divisor of the generalised Fermat numbers:

,
,
and

each of which were new records for their type (of which the last two still stand).

Prime Form (Chris Nash's original version, based on Yves Gallot's Proth library)

NewPGen (Paul Jobling's sieve program, based on Yves Gallot's Proth library)

PRP (George Woltman's probabilistic primality program - which actually uses Fermat's little theorem - to be used in conjunction with NewPGen, and Proth.exe). A faster version - PRP2 - also by GW, exploits the recent Intel Pentium IV chip

In May 2001 - using a combination of Yves Gallot's proth, Paul Jobling's NewPGen, and George Woltman's PRP - I also had the good fortune to find the 275,977 digit prime 3* (the then largest known prime; it may still be, but these prime rankings have a habit of not lasting for a long time!) That prime proved to be a divisor of the generalised Fermat numbers:

and

The first of those broke the previous record (above), and the second established a new record for its type.

Last month - here in Klagenfurt - Manfred Toplic found the 246767 digit prime 5* (the largest known prime), and a divisor of the generalised Fermat number:

pfgw (the Chris Nash managed program; the 'pf' is 'Prime Form,' the 'g' is 'Gallot,' and the 'w' is 'Woltman.')

That list is not complete; one should consult the web sites of Chris Caldwell (exclusively devoted to prime numbers) or Keith Matthews (which covers Number Theory in general). Those two sites are the "cream of the cream."