Hello everyone,

I did like to give a brief overview of Fermat's theorem and its proof. There are various methods to prove Fermat's Little theorem, but I found the combinatorial approach to be the most straightforward and easy to understand. I'd like to discuss Fermat's theorem and its proof using combinatorics.

Fermat's Little Theorem

It states that given 2 integers $$$a$$$ , $$$p$$$ where $$$a > 1$$$ and $$$p$$$ is a prime, It follows that $$$a^{p-1} \equiv 1 \pmod{p}$$$

Example:

Say a = 2 , p = 5.
$$$a^{p-1} $$$
$$$ = 2^{5-1}$$$
$$$ = 2^4 = 16$$$
$$$ \equiv 1 \pmod{5}$$$

Proof (Combinatorics Approach)

The concept behind this proof is to approach it through a combinatorial problem and discover its solution, which indirectly verifies the theorem. Let's explore this straightforward combinatorial problem.

Problem

Consider a Necklace chain consisting of beads. There are $$$p$$$ beads in this chain. You are allowed to color each bead with $$$a$$$ possible colors available. The colors are available in infinite amounts, there is no other restriction on coloring. Find the number of ways to color these beads.

It can be easily shown that there are $$$a^p$$$ ways to color the beads to get different necklaces. (considering cyclic rotations as distinct). Every bead has $$$a$$$ options to be colored.

Consider a small variation to this problem, Among all possible $$$a^p$$$ permutations, Let's try to group them based on similar cyclic rotations. Two permutations are said to be equivalent if any of them can be generated from the cyclic rotation of the other.

For example, consider $$$a = 2, p = 3$$$. Let X and Y be the 2 possible colors available. Let's try to group these $$$2^3 = 8$$$ permutations based on similar cyclic rotations. We get:

• Group 1: XXX
• Group 2: YYY
• Group 3: XXY, XYX, YXX
• Group 4: XYY, YYX, YXY

Here we get 4 different groups of sizes 1,1,3,3 each. Let's try to analyze these group sizes in-depth.

Periodicity of a String:

The periodicity of a string refers to the smallest length of a substring that, when repeated, forms the entire string. In other words, it's the minimum length of a substring that can be repeated periodically to recreate the original string.

Example

• ABCABC has periodicity = 3 (ABC)
• ABABAB has periodicity = 2 (AB)

#Claim 1

The periodicity of a string is the same as its group size of similar cyclic rotations.

#Explanation

Let's assume the periodicity of a string is $$$X$$$. After performing $$$X$$$ cyclic rotations (either left or right) on this string, we return to the original string. Thus, at least $$$X$$$ cyclic rotations are needed to restore the string to its original form.

#Proof

Suppose, for the sake of contradiction, that we can return to the original string in $$$Y$$$ operations, where $$$Y < X$$$. If this were true, it would imply that every group of $$$Y$$$ characters is repetitive, meaning that the periodicity of the string would be $$$Y$$$. However, this contradicts our original assumption that the periodicity is $$$X$$$, not $$$Y$$$. Therefore, $$$Y < X$$$ cannot be true, and at least $$$X$$$ cyclic rotations are indeed required to return to the original string.

References:
Wikepedia