Four formats for Fermat

In my previous post I mentioned Fermat’s Little Theorem, a beautiful, fundamental result in number theory that underlies lots of things like public-key cryptography and primality testing. (It’s called “little” to distinguish it from his (in)famous Last Theorem.) There are several different forms in which it is commonly presented, so I wanted to start by introducing them and showing how they are related.

Statement 1

Let’s start with the statement that looks the least general:

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

(Recall that $x \equiv y \pmod p$ means that $x$ and $y$ have the same remainder when you divide them by $p$ .) For example, $7$ is prime, and we can check that for each $a \in \{1, \dots, 6\}$ , if you raise $a$ to the $6$ th power, you get a number which is one more than a multiple of $7$ :

$\displaystyle \begin{array}{ccrcr} 1^6 &=& 1 &=& 0 \cdot 7 + 1 \\[0.2em] 2^6 &=& 64 &=& 9 \cdot 7 + 1 \\[0.2em] 3^6 &=& 729 &=& 104 \cdot 7 + 1 \\[0.2em] 4^6 &=& 4096 &=& 585 \cdot 7 + 1 \\[0.2em] 5^6 &=& 15625 &=& 2232 \cdot 7 + 1 \\[0.2em] 6^6 &=& 46656 &=& 6665 \cdot 7 + 1 \end{array}$

Statement 2

Here’s a second variant of the theorem that looks slightly more general than the first:

If $p$ is a prime and $a$ is any integer not divisible by $p$ , then $a^{p-1} \equiv 1 \pmod p$ .

This looks more general because $a$ can be any integer not divisible by $p$ , not just an integer between $0$ and $p$ . As an example, let $a = 10$ . Then $10^6 = 1000000 = 7 \cdot 142857 + 1$ .

We can see that (2) is more general than (1), since if $0 < a < p$ then it is certainly the case that is not divisible by $p$ . Hence (2) implies (1). But actually, it turns out that (1) implies (2) as well!

Here’s a proof: let’s assume (1) and use it to show (2). In order to show (2), we have to show that $a^{p-1} \equiv 1 \pmod p$ whenever $p$ is prime and $a$ is any integer not divisible by $p$ . So let $p$ be an arbitrary prime and $a$ an arbitrary integer not divisible by $p$ . Then by the Euclidean division theorem, we can write $a$ in the form $a = qp + b$ , where $q$ is the quotient when dividing $a$ by $p$ , and $0 \leq b < p$ is the remainder. $b$ can’t actually be $0$ , since we assumed $a$ is not divisible by $p$ . Hence $0 < b < p$ , so (1) applies and we can conclude that $b^{p-1} \equiv 1 \pmod p$ . But notice that $a \equiv b \pmod p$ (since $a$ is $b$ more than a multiple of $p$ ), and hence $a^{p-1} \equiv b^{p-1} \equiv 1 \pmod p$ as well.

So although (2) “looks” more general than (1), the two statements are in fact logically equivalent.

Statement 3

Here’s another version which seems to be yet more general, since it drops the restriction that $a$ can’t be divisible by $p$ :

If $p$ is prime and $a$ is any integer, then $a^p \equiv a \pmod p$ .

Notice, however, that the conclusion is different: $a^p \equiv a \pmod p$ rather than $a^{p-1} \equiv 1 \pmod p$ .

As an example, let $p = 7$ and $a = 10$ again. Then $10^7 = 10000000 = 1428570 \cdot 7 + 10$ , that is, the remainder of $10^7$ when divided by $7$ is $10$ . As another example, if $a = 14$ , then $14^7 = 105413504 \equiv 14 \pmod 7$ since both are divisible by $7$ .

Once again, although this seems more general, it turns out to be equivalent to (1) and (2).

First of all, to see that (2) implies (3), suppose $p$ is prime and $a$ any integer. If $a$ is divisible by $p$ , then $a \equiv 0 \pmod p$ and clearly $a^p \equiv 0 \equiv a \pmod p$ . On the other hand, if $a$ is not divisible by $p$ , then (2) applies and we may conclude that $a^{p-1} \equiv 1 \pmod p$ ; multiplying both sides of this equation by $a$ yields $a^p \equiv a \pmod p$ .

Now, to see that (3) implies (2), let $p$ be a prime and $a$ any integer not divisible by $p$ . Then (3) says that $a^p \equiv a \pmod p$ ; we wish to show that $a^{p-1} \equiv 1 \pmod p$ . However, since $a$ is not divisible by $p$ we know that $a$ has a multiplicative inverse $\pmod p$ , that is, there is some $b$ such that $ab \equiv 1 \pmod p$ . (I have written about this fact before; it is a consequence of Bézout’s Identity.) If we take $a^p \equiv a \pmod p$ and multiply both sides by $b$ , we get to cancel one $a$ from each side, yielding $a^{p-1} \equiv 1 \pmod p$ as desired.

Statement 4

The final form is the most general yet: it even drops the restriction that $p$ be prime.

If $n \geq 1$ and $a$ is any integer relatively prime to $n$ , then $a^{\varphi(n)} \equiv 1 \pmod n$ .

[The first version of this post accidentally omitted the phrase “relatively prime to $n$ ” from the above statement, rendering it false; here’s my later post explaining and correcting the error.]

$\varphi(n)$ is the Euler totient function, i.e. the number of positive integers less than $n$ which are relatively prime to $n$ . For example, $\varphi(12) = 4$ since there are four positive integers less than $n$ which have no factors in common with $12$ : namely, $1$ , $5$ , $7$ , and $11$ .

We can see that (4) implies (2), since when $n = p$ is prime, $\varphi(p) = p-1$ (since every integer in $\{1, \dots, p-1\}$ is relatively prime to $p$ ). None of (1), (2), or (3) directly imply (4)—so it is, in fact, a bit more general—but we can generalize some of the proofs of these other facts to prove (4).