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

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in number theory, primes, proof and tagged , , . Bookmark the permalink.

One Response to Four formats for Fermat

  1. Pingback: Fermat’s Little Theorem: proof by modular arithmetic | The Math Less Traveled

Leave a reply. You can include LaTeX $latex like this$. Note you have to literally write 'latex' after the first dollar sign!

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