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 different)

References:
Wikepedia