Non User
Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z	Business Non User Industries Finance Tax

Home > Proofs of Fermat's little theorem

a^p = a ( mod p)

for every prime number p and every integer a.

Note that it is enough to prove

a^{p − 1} = 1 (mod p)

for every integer a which is relatively prime to p (i.e. not a multiple of p). Multiplying with a then gives the above version of the theorem for those numbers a; for the multiples of p the above version is clear anyway.

1 A direct proof

We will assume a to be relatively prime to p. This proof will make use of our base a multiplied by all the numbers from 1 to p − 1. It turns out that if p is prime, the values 1a through (p − 1)a (modulo p) are just the numbers from 1 through p − 1 rearranged, a consequence of the following lemma. We then multiply all those numbers together, resulting in a formula from which the theorem follows.

Lemma: If a is relatively prime to p and x and y are integers such that xa = ya (mod p), then x = y (mod p).

Proof of lemma: xa = ya (mod p) means that p divides xa − ya = a (x − y). We know that a does not contain the prime factor p, so (x − y) must contain it, since the prime factorization is unique by the fundamental theorem of arithmetic. So p divides (x − y), which means x = y (mod p), which completes the proof of the lemma.

Proof of theorem: Consider the set P = {1a, 2a, 3a, ... (p − 1)a}. These numbers are different modulo p by the lemma, and none of them is zero modulo p (again by the lemma: 0a = ka (mod p) would imply 0 = k modulo p, but k is too small for that). So modulo p, the set P is the same as the set N = {1, 2, 3, ... (p − 1)}. So if we multiply the elements of these two sets together, we will get the same result modulo p:

1a * 2a * 3a * ... (p − 1)a = 1 * 2 * 3 * ... (p − 1) (mod p)

Regrouping the left side:

(1*2*3*...(p − 1)) * a^{p − 1} = 1*2*3*...(p − 1) (mod p)

Now we would like to cancel the common term (p − 1) ! from both sides. This is allowed by the lemma, since p and (p − 1)! can have no factor in common, again by the fundamental theorem of arithmetic. Dividing out (p − 1)!, we get:

a^{p − 1} = 1 (mod p).

2 A proof using group theory

This is similar to the direct proof. Trivially, the integers 1, ..., p-1 form a group under multiplication mod p. This group is finite, so clearly the subgroup generated by any a in 1, ..., p-1 must have size q where q divides the size of the original group, p-1. That is, . But since p-1 = rq for some integer r, . Add the special case where a = p and we get the full proof.

3 Inductive proof with the binomial theorem

Here we 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

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

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

(k + 1)^p mod p

= k^p + 1^p mod p (by the statement shown above)

= k^p + 1 mod p.

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

Politics	Business	Finance

Topics: Proofs Of Fermat's Little Theorem Mod Minus Prime Numbers Proof...

---

Proofs of Fermat's little theoremThis is a collection of proofs of Fermat's little theorem: a p a ( mod p for every prime number p and every integer a''. Note that it is enough to prove a p − 1 1 (mod p for every integer a which is relatively prime to p (i. not a multiple of p . Proofs and RefutationsProof and Refutations is a book by the philosopher Imre Lakatos expounding his view of the progress of mathematics. The book is written as a series of Socratic dialogues involving a group of students. A central theme is that definitions are not carved in