Wikipedia: Fermats little theorem

Showing revision 19

Fermat's little theorem states that if p is a prime number, then for any integer a where a is not divisible by p,

: a^p = a mod p.

This means that if you you take some number a, multiply it by itself p times and substract a, the result is divisible by p (see modular arithmetic). It is called Fermat's little theorem to differentiate it from Fermat's last theorem.

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 ⁿ - 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³⁴¹=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

: (a + b)^p mod p = a^p + b^p mod p

when p is prime. The Binomial theorem tells us that

: (a + b)ⁿ = ∑_i=0^p (pCi)aⁱb^p-i = a^p + b^p + ∑_i=1^p-1 (pCi)aⁱb^p-i .

Here pCi = p(p - 1)(p - 2)(p - 3) ... (p - (i-1)) / i! if 0 < i < p. Since i is less than p, and p is prime, p cannot be divided by i!, so the whole term (pCi)aⁱb^p-i is a multiple of p if 0 < i < p. This means the whole sum from i = 1 to i = p - 1 equals 0 mod p. So, (a + b)^p mod p indeed equals a^p + bⁿ mod p when p is prime.

Back to the proof. We proceed now with the two induction steps.

Obviously, when a = 1, a^p mod p = a.
We assume for now that when a = k, the theorem is true, that is, we assume that k^p mod p = k if k < p, and see what happens when a = k + 1:

(k + 1)^p mod p =

: (by the little side theorem I demonstrated)

k^p + 1^p mod p = k^p + 1 mod p.

Since we assumed that k^p mod p = k if k < p, we conclude that (k + 1)^p mod p = k + 1 if k + 1 < p, which is what we wanted to demonstrate.

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.)

/Talk