Fermat's little theorem

Fermat's little theorem states that If P is a prime number then for any number a, (aP - a) must be divisible by P. This theorem is useful for testing if a number is not prime, though it can't tell if a number is prime. As was his habit, Pierre de Fermat didn't provide a proof (this time saying "I would send you the demonstration, if I did not fear its being too long"). Leonhard Euler first published a proof in 1736, but Gottfried Leibniz left virtually the same proof in an unpublished manuscript from sometime before 1683.