Fermat’s Little Theorem


This is a beautiful theorem which states that the difference between a positive integer a and a prime power of a, a^p-a, is divisible by p. It’s history can be found in Wikipedia: Fermat posited the theorem (and as usual, did not give the proof) while Euler first published a proof using mathematical induction. Below, we will state the theorem and provide a simple-to-understand proof using only modular arithmetic, followed by another simple proof using mathematical induction.


For an integer a and a prime p, the following is true:

\displaystyle a^{p} \equiv a\mod{p}\ \ \ \ (1)


Note that if a\equiv 0\mod{p}, the statement is trivially true. Therefore, we focus on the case that a\not \equiv 0 \mod{p}, that is, a is a positive integer such that p does not divide a. (This also implies that a\neq 0.) In that case, we can divide both side of the main statement by a and have the following statement:

a^{p-1}\equiv 1\mod{p}\ \ \ \ (2)

Proving the above statement will complete the proof.

When we divide a with prime p, the remainder must be one of 1,2,3,\cdots , p-1. Therefore, one of the following congruences must be true:

a\equiv 1\mod{p}

a\equiv 2\mod{p}


a\equiv (p-1)\mod{p}

Now consider the numbers s_k=k\cdot a, 1\leq k \leq p-1. These numbers are 1\cdot a, 2\cdot a, 3\cdot a, \cdots , (p-1)\cdot a. We ask the following question: is it possible that two different numbers s_i and s_j be congruent modulo p? Let us find out. (Hint: we are going to use contradiction.)

Suppose when x\neq y, we have s_x=x\cdot a and s_y=y\cdot a such that 0\leq x,y\leq p-1, x\neq y and yet s_i\equiv s_j\mod{p}. Since x,y \leq p-1 and x\neq y, it follows that

\displaystyle x\not \equiv y\mod{p}\ \ \ \ (3)

Next, we have, due to our assumption, that

\begin{array}{lrcl}  & s_x &\equiv & s_y\mod{p}\\  \implies & xa &\equiv & ya\mod{p}\\  \implies & (x-y)a &\equiv & 0\mod{p}\\  \implies & x-y &\equiv & 0\mod{p}\text{ since }a\not \equiv 0\mod{p}\\  \implies & x &\equiv & y\mod{p}  \end{array}

which contradicts (3). This implies, if i\neq j, s_i \neq s_j, 1\leq i,j\leq p-1. Therefore each s_k,1\leq k\leq p-1 is congruent to a unique number u, 1\leq u\leq p-1. Thus the sequence of all numbers

\displaystyle (1\cdot a)\mod{p},(2\cdot a)\mod{p},(3\cdot a)\mod{p},\cdots \left((p-1)\cdot a\right)\mod{p}

is nothing but a rearrangement of the numbers

\displaystyle 1,2,3,\cdots ,(p-1)\,.

\begin{array}{lrcl}  & (1\cdot a)(2\cdot a)(3\cdot a)\cdots \left((p-1)\cdot a\right) &\equiv & 1\cdot 2\cdot 3\cdots (p-1) \mod{p}\\  \implies & (p-1)!a^{p-1}&\equiv & (p-1)!\mod{p}\\  \end{array}

Since p\geq 2 \implies (p-1)!\neq 0, by dividing both sides by (p-1)! it follows that

\displaystyle a^{p-1} \equiv 1\mod{p}.


A Proof by Induction

We will prove that for a given prime p, the following statement is true for all natural number a such that p does not divide a:

a^{p-1}\equiv 1\mod{p}\ \ \ \ (2)


When a=1, the statement trivially holds since p \geq 2.

(Inductive Hypothesis)

Suppose the above statement is true for 1\leq a\leq n-1. That is,

(n-1)^{p-1}\equiv 1\mod{p} where p \nmid (n-1). This implies,

(n-1)^p\equiv (n-1)\mod{p}.


We need to prove that n^{p-1} \equiv 1\mod{p} where p \nmid n.

Now there can be two cases depending on whether p divides  n-1.

[Case 1] n-1\not \equiv 0\mod{p}

In this case, we can use the inductive hypothesis: (n-1)^{p-1} \equiv 1 \mod{p}.


\begin{array}{rlll}  & n^{p} &=& \left(1+(n-1)\right)^{p}\\  & &=& 1 + \underbrace{p(n-1) + \frac{p(p-1)}{2!}(n-1)^2 + \cdots }_{\text{multiples of  }p} + (n-1)^{p}\\  & &\equiv & 1 + (n-1)^{p} \mod{p}\\  & &\equiv & 1 + (n-1) \mod{p} \ \ \ \ \text{[by using the inductive hypothesis]}\\  & &\equiv & n\mod{p}\,.\\  \end{array}
Since n\not \equiv 0\mod{p}, we can divide both sides by n and thus arrive at
n^{p-1} \equiv 1\mod{p}.

Now the second case.

[Case 2] n-1 \equiv 0\mod{p}

If p divides n-1, then
\begin{array}{rlll}  & n-1\equiv 0 \mod{p}\\  \implies & n \equiv 1 \mod{p}\\  \implies & n^{p-1} \equiv 1\mod{p} \ \ \ \ \text{since }p\geq 2 \,.  \end{array}

Therefore, for all primes p and natural numbers n\not \equiv 0\mod{p},  the following statement holds:
n^{p-1}\equiv 1\mod{p}.



3 thoughts on “Fermat’s Little Theorem

    1. Yes! Thank you very much for pointing towards it. (Let me summarize the counting argument below. A nice presentation can be found here.)

      Suppose we are making necklaces from beads. Each bead can be one of k colors. Since we have no restriction on colors, there can be k^p different bead-strings of length p. Of these, only k strings are single-colored. Let’s take them out: now we have k^p-k strings left. Now let’s join the two ends of each of these strings to make a necklace. How many of these necklaces are unique? Only
      \displaystyle \frac{k^p-k}{p},
      because every unique necklace can be generated from p different strings. Since the cardinality of any set is an integer, the cardinality of the set “unique non-monochromatic necklaces containing p beads, each bead having one of k colors” is also an integer. This implies that \frac{k^p-k}{p} is an integer, or equivalently, {k^p-k} is a multiple of p.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s