Fermat's Little Theorem
Theorem (Fermat's Little Theorem)
Ifis a prime andis any integer withthen(1)
Proof: Consider the set ofintegers
None of these numbers is congruentto 0 for ifthen by Euclid's Lemma eitherorneither of which is true here. Neither are any congruent to each otherfor ifthen sincewe can cancel it to giveIt follows thatis the setpossibly reordered.
Multiplying all the numbers in the first set together gives the same resultas multiplying all the numbers in the second set together, hence
Sincedoes not dividewe can cancel this factor to give
(1) only holds forbut multiplication bygiveswhich holds for all
Fermat's little theorem may be used as in the following examples:
Example Find the remainder whenis divided by 17.
Fermat's little theorem tells us thathence
Example: Show that for any odd primeis divisible by