Fermat’s Little Theorem states that if p is a prime number and a is an integer then ܽ ap is congruent to a modulo p . This result is of huge importance in elementary and algebraic number theory. This theorem has many interesting and sometimes unexpected proofs. One modern proof is based upon Euler’s phi function and Euler’s theorem.