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² 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⁹⁰  =1 (mod 91), but 91 is not prime.
        We can test 3⁹⁰ using Fermat's Little Theorem without ever finding out what the actual value of 3⁹⁰ 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⁶ = 1 (mod 91)  then any power of 3⁶ will also be =1 (mod 91), and 3⁹⁰= (3⁶)¹⁵.

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