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 ap – 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.
ap – 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.
ap = a (mod p)
Then, simplify the both sides with a
ap-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 ap 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 ap – a strings consisting of at least two symbols. All these remaning ap – 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.
Support this blog if you do like!
I think I actually understood your explanation. Thank you and well done !