Unofficial Guide to Fermat’s Little Theorem

Fermat contributes construction of modern math with well known theorems. Today, we are going to mention the little one. This is called little one because the biggest and the last one can be proven in 350 years. Fermat’s little theorem states that if p is a prime, and a is any integer not divisible by p, then a^p – a is divisible without remainder by p.

Vlog

You can continue to read this tutorial or watch the following video. They both cover the proof of Fermat’s little theorem.

---

🙋‍♂️ You may consider to enroll my top-rated cryptography course on Udemy

---

Alternatively, Fermat’s Little Theorem can be proven by induction.

Theorem

We can express Fermat’s little theorem as illustrated below.

a^p – a = 0 (mod p)

Here, p has to be a prime number, and also a and p must be coprimes. Some sources modifies this equation and move minus a term to the right hand side.

a^p = a (mod p)

Then, simplify the both sides with a

a^p-1 = 1 (mod p)

This form is much similar to Euler’s theorem.

---

---

Concrete Example

Suppose that our alphabet consists of a symbols, and we are going to produce all possible strings length of p. To make it concrete, put real numbers to a and p pair.

a = 8, p = 5

Here, I would like to define symbols in my alphabet 1 to 8.

alphabet = {1, 2, 3, 4, 5, 6, 7, 8}

I wonder that how many different strings length of 5 can be written for this alphabet. First character of the string can be 1 to 8. Similarly, second character of the string can still be 1 to 8. In this same way, 3rd, 4rd and 5th characters can be 1 to 8. This means that there are a^p strings can be written in defined space.

Now, consider strings consist of same symbol.

11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888

As seen, there are a strings consisting of same symbol.

Then, consider string consisting of at least two symbols (E.g. 11112). Shifting symbols in that string would produce p different strings.

11112, 11121, 11211, 12111, 21111

---

---

11113, 11131, 11311, 13111, 31111

11114, 11141, 11411, 14111, 41111

11115, 11151, 11511, 15111, 51111

…

It goes like this.

Subtracting number of all possible strings to number of strings consisting of same symbol is the number of strings consisting of at least two different symbols. In other words, we can say that there are a^p – a strings consisting of at least two symbols. All these remaning a^p – a strings can be divided by p because each representation can be rotated p=5 times. BTW, each representation refers to custom line as illustrated above.

In literature, restricted size of strings are called necklace. Connecting begin and end character of string reveals the necklace. One can rotate the necklace and have different appearance.

So, we’ve demonstrated the easiest proof of Fermat’s little theorem. Actually, there are lots of different ways to prove this theorem. Fermat’s little theorem is very important topic in cryptography world. RSA algorithm is based on its modified version named Euler-Fermat generalization.

---

Like this blog? Support me on Patreon

---