Fermat’s Little Theorem: proof by group theory

It’s time for our third and final proof of Fermat’s Little Theorem, this time using some group theory. This proof is probably the shortest—explaining this proof to a professional mathematician would probably take only a single sentence—but requires you to know some group theory as background. Fortunately I’ve written about the relevant group theory before, so I will link to the relevant posts if you want to read up on the background.

This time we’re going to prove statement 1:

If $p$ is prime and $a$ is an integer where $0 < a < p$ , then $a^{p-1} \equiv 1 \pmod p$ .

Consider the set $P = \{1, 2, \dots, p-1\}$ . I claim that this set forms a group under the operation of multiplication $\pmod p$ . To verify this we need to check several things:

First, we need to check that the set is closed under the given operation, that is, if we start with two elements from $P$ and multiply them $\pmod p$ , we will end up with an element in $P$ again. If we reduce the product $\pmod p$ , we will definitely get something less than $p$ ; so the real question is why we will never get $0$ . This is because if $0 < a,b < p$ and $p$ is prime, then neither $a$ nor $b$ is divisible by $p$ , and hence neither is $ab$ .
We need to check that this operation is associative—and indeed, multiplication $\pmod p$ is associative.
There needs to be an identity element, and there is: $1 \cdot a \equiv a \cdot 1 \equiv a \pmod p$ .
Finally, every element must have a multiplicative inverse, that is, for any $a \in P$ , there must be some $b \in P$ such that $ab \equiv 1 \pmod p$ . But we already know this is true (this also came up when proving two of the statements of Fermat’s Little Theorem equivalent).

So $P$ is a group under the operation of multiplication $\pmod p$ , and it has $p-1$ elements, that is, its order is $p-1$ . But by Lagrange’s Theorem, the order of each element evenly divides the order of the group. So let $a \in P$ and suppose $a$ has order $k$ , that is, $a^k \equiv 1 \pmod p$ . Then $k$ divides $p-1$ , that is, there is some $j$ such that $jk = p-1$ . Then $a^{p-1} \equiv a^{jk} \equiv (a^k)^j \equiv 1^j \equiv 1 \pmod p$ .

It is also easy to generalize this proof to a proof of Euler’s Theorem; I will leave it to interested readers to fill in the details. Recall that Euler’s Theorem says that if $n$ is any integer and $a$ is relatively prime to $n$ , then $a^{\varphi(n)} \equiv 1 \pmod p$ . Consider the set $\Phi(n)$ of all positive integers $0 < a < n$ which are relatively prime to $n$ . This also forms a group under the multiplication $\pmod n$ , and hence any element $a$ raised to the order of the group ( $\varphi(n)$ ) results in the identity element ( $1$ ).

There are many more proofs of Fermat’s Little Theorem, but this has been a representative sampling! In future posts, I’m going to explore the mathematics behind several computational tests for primality, most of which end up relying on Fermat’s Little Theorem in one way or another.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

Follow Blog via Email

Meta

Categories

Archives