Theorem (Fermat's Little Theorem)
If
is a prime and
is any integer with
then
(1)
Proof: Consider the set of
integers
None of these numbers is congruent
to 0 for if
then by Euclid's Lemma either
or
neither of which is true here. Neither are any congruent to each other
for if
then since
we can cancel it to give
It follows that
is the set
possibly reordered.
Multiplying all the numbers in the first set together gives the same resultas multiplying all the numbers in the second set together, hence
Which becomes
Sincedoes not divide
we can cancel this factor to give
(1) only holds for
but multiplication bygives
which holds for all
Fermat's little theorem may be used as in the following examples:
Example Find the remainder when
is divided by 17.
Fermat's little theorem tells us that
hence
Example: Show that for any odd prime
is divisible by
