Note that the opposite is not always true: if the result is a, p is not necesarily prime. However, the contrapositive? is always true, so if the result is not a, then p is not prime.
There are applications, such as public key cryptography like RSA that need large prime numbers. The usual algorithm to generate prime numbers is to generate a random odd numbers and test them for primality. However, primality tests are slow. If the user does not require the test to be completely accurate (say, he might tolerate a very small chance that a composite number is declared to be primte), there are fast algorithms based on Fermat's Little Theorem. For example, a simple way to check wheter a number n is prime, is to check if n divides a ^{ n } - a for some integer a. If n fails this, it is composite with certainty, if it doesn't then it is a probable prime for base a. To be reasonably sure that a number is prime, test it against several a's.
Improved versions of this test give strong probable primes. It has been shown by Monier and Rabin that for the improved test that for each a, the chance of catching a false prime is at least 3 in 4.
A number that is not prime but satisfies Fermat's Little Theorem for a given value of a, is called a pseudo prime to that base. The smallest pseudo-prime for the base 2 is 341. It is not a prime, since it equals 11*31, nevertheless it satifies Fermats little theorem; 2^{341}=2 (mod 341).
A number p that is a pseudo-prime for all values of a that are relatively prime to it, is called a [Carmichael number]?. The lowest Carmichael number is 561=3*11*17. In 1994 W.R. Alford, Andrew Granville, and Carl Pomerance proved that there are infinitely many Carmichael numbers.
Proving the "Little Theorem" is straightforward: we can use mathematical induction. First, the theorem is true for a=1, then one proves that that if it is true for a = k, it is also true for a = k + 1, concluding that the theorem is true for all a.
Before the main argument the following lemma is needed
Back to the proof. We proceed now with the two induction steps.
Fermat's little theorem was generalized by Euler: for any modulus n and any integer a that does not have any divisors in common with n, a^{φ(n)} is congruent to 1 modulo n, where φ(n) denotes Euler's φ function counting the integers between 1 and n that don't have divisors in common with n.
An easy proof of this theorem: multiplication by a permutes the residue classes mod n that are coprime to n; in other words (writing R for the set of all such classes) the sets { x : x in R } and { ax : x in R } are equal; therefore, their products are equal. Hence, a^{φ(n)}P = P where P is the first of those products. Since P is coprime to n, it follows that a^{φ(n)} = 1. (Note that everything in the foregoing is modulo n.)