Fermat’s Little Theorem states that ap – a is divisible without remainder if p is a prime, and a is an integer co-prime to p. We’ve showed the correctness proof of the statement rationally without needing any math background. Now, we are going to approach problem with a more powerful way.
Vlog
You can either continue to read this tutorial or watch the following video. They both cover the inductive proof of Fermat’s Little Theorem.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
Alternatively, we can prove Fermat’s Little Theorem with necklace method which requires less math.
Theorem
Remember the Fermat’s Little Theorem
ap – a = 0 (mod p)
We’ve already known that the statement is true while a = 0. Also, statement is still valid while a = 1.
Proof by Induction
Now, we’ll jump to a = n and suppose that the statement would be true for this condition. If we can prove that statement is true while a = n + 1 based on the previous assumption, then we could prove the correctness proof of statement. This approach is called as proof by induction.
(n+1)p – (n+1)
Here, we can use binomial theorem to expand the term.
(x+y)n = C(n, 0)xny0 + C(n, 1)xn-1y1 + C(n, 2)xn-2y2 + … + C(n, n-1)x1yn-1 + C(n, n)x0yn
Let’s apply binomial theorem to expand n+1 to the power of p.
(n+1)p = C(p, 0)np + C(p, 1)np-1 + C(p, 2)np-2 + … + C(p, p-1)n1 + C(p, p)n0
Now, replace the power term in main statement.
(n+1)p – (n+1) = C(p, 0)np + C(p, 1)np-1 + C(p, 2)np-2 + … + C(p, p-1)n1 + C(p, p)n0 – (n+1)
C coefficients refer to combination and it can be calculated as
C(i, j) = i! / (j! (i-j)!)
That’s why, both C(p, 0) and C(p, p) terms are equal to 1.
(n+1)p – (n+1) = np + C(p, 1)np-1 + C(p, 2)np-2 + … + C(p, p-1)n1 + n0 – n – 1
Would you realize that (np – n) exists in the equation above. Let’s group them. Also, n0 is equal to 1, and there is a -1 term in the equation. Let’s remove them.
(n+1)p – (n+1) = (np – n) + C(p, 1)np-1 + C(p, 2)np-2 + … + C(p, p-1)n1
Notice that our assumption is (np – n) can be divided by p. That’s why, we can remove it and focus on the rest of the equation. The question is that the following term can be divided by p or not.
C(p, 1)np-1 + C(p, 2)np-2 + … + C(p, p-1)n1
Binomial Expansion and Pascal’s Triangle
We should focus on coefficient terms. Herein, imagine the binomial expansion and pascal’s triangle.
| Pow | Expansion |
| 0 | 1 |
| 1 | 1 1 |
| 2 | 1 2 1 |
| 3 | 1 3 3 1 |
| 4 | 1 4 6 41 |
| 5 | 1 5 10 10 5 1 |
| 6 | 1 6 15 20 20 15 6 1 |
| 7 | 1 7 21 35 35 21 7 1 |
We’ve already known that p is a prime. That’s why, we should focus on only prime pow lines.
| Pow | Expansion |
| 2 | 1 2 1 |
| 3 | 1 3 3 1 |
| 5 | 1 5 10 10 5 1 |
| 7 | 1 7 21 35 35 21 7 1 |
Remember that C(p, 0) and C(p, p) coefficients are equal to 1 and we separated them because we supposed that sum of their multipliers can be divided by p. That’s why, I’ll remove 1 terms in expansion column.
| Pow | Expansion |
| 2 | 2 |
| 3 | 3 3 |
| 5 | 5 10 10 5 |
| 7 | 7 21 35 35 21 7 |
Necklace method
Notice that pow can be divided by all terms in expansions. However, we have to prove this to be convinced.
Let’s focus on a concrete example. I pick p as 7 and my alphabet would be {1, 2, 3, 4, 5, 6, 7}. And I would like to produce strings length of 4. In other words, I wonder the C(7, 4).
Remember that order doesn’t matter in combination. I mean that both (1, 3, 5, 7) and (3, 5, 7, 1) sets are same in my combination space. How can I manipulate this set? The answer is easy. I can increase all item values for module 7.
(1, 3, 5, 7); (2, 4, 6, 1); (3, 5, 7, 2); (4, 6, 1, 3); (5, 7, 2, 4); (6, 1, 3, 5); (7, 2, 4, 6)
If final set (7, 2, 4, 6) were increased one more time, then it would be equal to first one (1, 3, 5, 7). As seen, any demonstration can be manipulated 7 times. This means all sets can be divided by 7 in C(7, 4).
Similarly, if you try to produce strings for C(7, 3) on same alphabet, then the number of all sets will be divisible by 7, too.
To sum up C(7, x) will be divisible by 7 always while x > 1 and < 8.
To sum up, C(p, x) can be divided by p if p is a prime. Let’s turn back to the main statement.
(n+1)p – (n+1) = (np – n) + C(p, 1)np-1 + C(p, 2)np-2 + … + C(p, p-1)n1
We have supposed that (np – n) can be divided by p and try to prove (n+1)p – (n+1) can be divided by p based on this assumption. We also proved that C(p, x) can be divided by p if p is a prime. That’s why, all terms in the equation illustrated above can be divided by p.
So, we can prove the correctness of Fermat’s Little Theorem based on proof by induction. We’ve benefited from binomial theorem and pascal triangle (binomial expansion). This approach requires more powerful math background than the necklace method.
Like this blog? Support me on Patreon
