## 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

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