Fermat's Little Theorem

The famous "Last Theorem"
for which Fermat is best know by students is not used nearly so often as
the one which is remembered as his "little" theorem. The little theorem
is often used in number theory in the testing of large primes and simply
states that: if p is a prime which does not divide a, then a^{p-1}=1
(mod p) . In more simple language this says that if p is a prime
that is not a factor of a, then when a is multiplied together p-1 times,
and the result divided by p, we get a remainder of one. For example,
if we use a=7 and p=3, the rule says that 7^{2}
divided by 3 will have a remainder of one. In fact 49/3 does have
a remainder of one. The theorem was first stated by Fermat in a letter in 1640 without a proof. Euler gave the first published proof in 1736. Here is a link to a proof of the theorem.

The theorem is a one
direction theorem, what mathematicians call "necessary, but not sufficient".
What that means is that although it is true for all primes, it is not true
**JUST** for primes, and will sometimes be true for other numbers as
well. For example 3^{90}
=1 (mod 91), but 91 is not prime.

We can test 3^{90} using
Fermat's Little Theorem without ever finding out what the actual value
of 3^{90} is, by using the patterns of remainders
for powers of 3 divided by 91...

3^1 = 3
remainder on division is 3

3^2 = 9
........................
9

3^3=27
........................
27

3^4=81
........................
81

3^5=243
........................
61

3^6= 729
.......................
1

Since 3^{6}
= 1 (mod 91) then any power of 3^{6}
will also be =1 (mod 91), and 3^{90}= (3^{6})^{15}.

Numbers which meet the conditions
of Fermat's Little Theorem but are not prime are called **pseudoprimes**,
or probable primes relative base n. Although 91 is a pseudoprime
base three, it does not work for other bases. For mathematicians
testing large numbers, it is much easier to test against several bases
using a^{p-1} then to try to factor huge numbers.
Since there are relatively few pseudoprimes, and even less that are pseudoprimes
to more than one base, this often works. There are, however,
some numbers that are pseudoprimes to every base to which they are relatively
prime. These most difficult of pseudoprimes are called Carmichael
numbers. Since there is little written about Carmichael on the net,
I include a rather nice capsule history of his life and work presented
by Julio Cabillon to the Math History Newsgroup a few years ago.

Robert Daniel Carmichael, a very
talented and versatile mathematician,

was born in Alabama (USA) in 1879.
Early in his career he was interested

in a hot topic of the time: the
theory of relativity. In fact, in 1913,

he published a book on that issue
[1], based mainly on a short course of

lectures he delivered at Indiana
University in the autumn of 1912, and on

papers appeared in the Physical
Review [volume 35, pp. 153-176, and second

series, volume 1, pp. 161-197].
He kept on developing these ideas for many

years. Just recall that in 1920,
a second edition [4] of this book saw the

light, and in 1927 he addressed
"A debate on the theory of relativity",

which included an introduction
by William Lowe Bryan [5].

In 1914 he published "The Theory
of Numbers" [2], and a year later,

"Diophantine Analysis" [3], two
well-known monographs edited by M. Merriman

and R.S. Woodward. Fortunately
enough, in 1959 these two works were

jointly published by Dover as an
unabridged and unaltered republication

of original editions.

In 1915, Carmichael was appointed
Assistant professor of Mathematics at the

University of Illinois. As early
as 1929 he was Chair of his department.

Five years later he was the Dean
of the Graduate School, a position he

maintained until his retirement
in 1947.

In 1927, Carmichael not only addressed
his "debate on the theory of

relativity", but also published
with James Henry Weaver (1883-1942) a

textbook simply entitled "The Calculus"
[6], of which a revised edition

[9] was carried out by both authors
and Lincoln La Paz, in 1937.

That very year, Carmichael showed
his fine conditions of mathematician and

writer with a well-known textbook
on Group Theory [10]. Some time ago, on

this list, John H. Conway told
us that that book was something

"which a whole generation of group theorists remember

with affection. I recall a conversation in which several

prominent group theorists tried to estimate the times

they had taken over various exercises (these times ranging

from minutes to years!)."

After retirement, Carmichael asked
himself a philosophical big question,

and conceived "What is man? A poem",
published by University of Illinois

Press, in 1959. An excerpt of five
lines follows:

"Good will must reign to make our future safe,

And this requires an understanding mind.

The man who knows not other men will chafe

Against suspicion since his heart is blind,

And he will tend to hold himself to self confined."

Once, Harrison E. Cunningham gave the following description of Carmichael:

"Of unyielding integrity, he loved the truth and hated

sham and pretense. His appreciation of the beautiful,

the true, and the good is exceptional.

His friendship is firm, his loyalty unbreakable. Those who

know him are fortunate beyond words."

Carmichael published many papers
in the most prestigious periodicals

(pointers that I leave out in order
to save bandwidth and time!), as well

as other books and manuals -- for
instance, cf. [7] and [8].

After a remarkable life, plenty
of mathematical achievements, Robert D.

Carmichael passed away in 1967.

A FEW REFERENCES:

[1] "The Theory of Relativity",
1st edition, New York: John Wiley & Sons,

Inc.,
pp. 74, 1913.

[2] "The Theory of Numbers",
New York: John Wiley & Sons, Inc., pp. 94,

1914.

[3] "Diophantine Analysis",
1st ed., New York: John Wiley & Sons, Inc.,

pp. 118,
1915.

[4] "The Theory of Relativity",
2nd edition, New York: John Wiley & Sons,

Inc.,
pp. 112, 1920.

[5] "A Debate on the Theory
of Relativity", with an introduction by

William
Lowe Bryan, Chicago: Open Court Pub. Co., pp. 154, 1927.

[6] "The Calculus", by Robert
D. Carmichael and James H. Weaver,

Boston/New
York: Ginn and Company, pp. 345, 1927.

[7] "The Logic of Discovery",
Chicago/London: Open Court Publishing Co.,

pp. 280,
1930; also reprinted by Arno Press, New York, 1975

[8] "Mathematical Tables and
Formulas", compiled by Robert D. Carmichael

and Edwin
R. Smith, Boston: Ginn and Company, pp. 269, 1931; also

reprinted
by Dover Publications, Inc., New York, 1962.

[9] "The Calculus", revised
edition by Robert D. Carmichael, James H. Weaver

and Lincoln
La Paz, Boston/New York: Ginn and Company, pp. 384, 1937.

[10] "Introduction to the Theory
of Groups of Finite Order", Boston/New York:

Ginn and
Company, pp. 447, 1937; also reprinted by Dover Publications,

Inc.,
New York, 1956.

Best wishes from Montevideo,

Julio Gonzalez Cabillon