Aditya Ghosh

This is it. All the previous articles (links at the bottom of the page) have been building to this very moment. I promised you we would prove Fermat’s Little Theorem:

For any prime p, p divides a^p – a for all whole numbers a

Or, to rephrase it with the new notation we’ve learned (see article 1 for a reminder):

For all whole numbers, a^p ≡ a (div p)  if p is prime

Whenever we are tackling complicated problems like this, we should always start by asking ourselves: can we break it down to a simpler problem?

Recall the property we discussed in article 1,

If a ≡ x (div p)

    and b ≡ y (div p)

Then, ab ≡ xy (div p)

This simply says, if you’re multiplying numbers in div p, just multiply the remainders instead. 

So, if we want to check a^p ≡ a (div p) for some a, we just need to check if its remainder satisfies this property. Or in other words, instead of checking for ALL whole numbers a, we just need to check if this holds for all the remainders we can get when we divide a by p.

So, the question is what are these remainders? Well they are just the numbers 0,1,2,…,(p-1). Take p = 2, for example, then we can only have remainders 0 or 1, since working div p for p=2 there are no other possible remainders.

Okay, we have simplified the problem quite a lot now. We can immediately see a = 0 will hold because 0^p – 0 is just 0. Any number divides 0, so p divides 0. 

Which means we are left to prove this for a = 1,2,…,(p-1).

---

There is actually another simplification we can make: notice a^p – a = a (a^p-1 – 1). So,  

If p divides a (a^p-1 – 1)    for a =1,2,…,p-1

Then, p divides a^p-1 – 1

Why is this true? Well, a prime p has no factors other than 1 or itself. Here, the number a is less than p, so it only has 1 as a common factor to p. So if p divides the product of the two numbers a and a^p-1 – 1, it has to divide the ‘other’one, ie. a^p-1 – 1.

So, we can safely say that a has no useful impact as far as divisibility is concerned. As an example, consider p = 5. Well, 5 divides 15. But if you take 3 x 15 = 45, it’s still is divisible by 5. Multiplying by 3 (our value of a) has no impact whatsoever. 

Now, since a^p-1 – 1 is divisible by p, a^p-1 must give 1 as a remainder when divided by p. For example, since 11 gives remainder 1 when divided by 5, five must divide 11 – 1 , that is, 10. 

This means our original theorem can now be stated equivalently as:

a^p-1 ≡ 1 (div p)        for a=1,2,…,p-1

This is the result that we will show to be true at the end of the proof so remember it!

---

Now, here comes to the juicy part of the proof. We claim that this set S of p-1 elements, {1,2,…,p-1} forms a group under multiplication div p. If you need a reminder of what a group is check out article 2 on symmetry and article 3 on the group axioms. 

It is easy to check for closure and associativity, and the identity is just 1. The difficulty lies in proving that inverses exist. Remember, when we used the Rearranging Row Property in article 2, we said we can always find an inverse because a row will always contain the identity somewhere (see this section in Article 2 if you’re unsure). So, we can try and prove the Rearranging Row Property here. 

Take row a, it must have the elements a, 2a, 3a,…,(p-1)a under div p. If we show all these elements are different from each other, we would have p-1 different elements of set S in the row. But, the set has p-1 elements in total, which means all the elements will appear exactly once. Hence 1 will appear somewhere, which means we always can find an inverse of the element a.

To show all the elements are different, we employ one of the oldest techniques in mathematics, a proof by contradiction! 

Assumption: Two elements in row a are the same.

Since they are in row a, they are of the form ax and ay, where x and y can be 1,2,… or p-1. As they have the same value div p, we can say

ax ≡ ay (div p)

Hence, ax – ay ≡ 0 (divp)

So, p divides a(x-y)

Like we said earlier, a is irrelevant here, so p must divide (x-y). 

We know, x and y are between 1 and p-1, so x-y can never take values like p or -p, that would be too high or too low. Their difference can be at most (p-2). Check this with some values just to be sure.

This means the only option is for x-y to equal 0 for p to divide it (remember, any number divides 0).

But that means x = y, and hence the element ax = ay. The elements are not different as we first stated. Contradiction! So our assumption was wrong, all the elements are actually different.

We have now successfully proved the Rearranging Row Property and hence the inverse property. Therefore, our set S does indeed form a group div p as we first claimed.

---

Now we come to the most beautiful part of the proof. Let’s take the row a again. We multiply all the elements of the row (that is a, 2a, …, (p-1)a) together. Here, we are essentially multiplying all the elements in the set S, but just in a different order (Rearranging Row Property!). Writing this down neatly in the language of algebra, 

a x 2a x … x (p-1)a ≡ 1 x 2 x … x (p-1)  (div p)

In mathematics, we have a very neat way of writing consecutive products like 1 x 2 x 3 x … x n, we just write “n!”. For example, 3! = 1 x 2 x 3 = 6. ”3!” is read as “3 factorial”. Using this notation here and factoring out all of the a terms, we have:

 (p-1)! a^p-1 ≡ (p-1)! (div p)

Now we use a property of group theory which we proved earlier: the Cancellation Property! We can just cancel (p-1)! from both sides to get:

a^p-1 ≡ 1 (div p)

And we have finally proved Fermat’s Little Theorem!

Article 1: Modular Arithmetic and calculating expenses

Article 2: The Importance of being Symmetric

Article 3: When do equations have solutions? (An introduction to Group Theory)