## 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

Which becomes

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