Fermat’s Little Theorem: proof by modular arithmetic

In a previous post I explained four (mostly) equivalent statements of Fermat’s Little Theorem (which I will abbreviate “FlT”—not “FLT” since that usually refers to Fermat’s Last Theorem, whose proof I am definitely not qualified to write about!).

Today I want to present the first proof of FlT. We’re going to prove statement (2), that is,

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

We already saw that statements (1), (2), and (3) are logically equivalent, so proving (2) is sufficient to prove all of them. (As I’ll show in a future post, we can also generalize this proof to prove the corrected version of statement (4).)

So, suppose $p$ is a prime, and $a$ is any integer not divisible by $p$ . Now consider the set of multiples of $a$ up to $(p-1)a$ :

$\{a, 2a, 3a, \dots, (p-1)a \}$ .

However, we will consider not the multiples of $a$ themselves but their remainders when divided by $p$ . As an example, suppose $p = 7$ and $a = 3$ . Then we want to look at multiples of $a$ : $3, 6, 9, 12, 15, 18$ —and then take their remainders $\pmod 7$ . As you can check, this yields the set

$\{3, 6, 2, 5, 1, 4\}$ .

As another example, suppose $p = 13$ and $a = 20$ . Then the multiples of $a$ , considered $\pmod {13}$ , are $20 \equiv 7$ , $40 \equiv 1$ , $60 \equiv 8$ , and so on, ultimately yielding the set of remainders (which you can again check):

$\{7,1,8,2,9,3,10,4,11,5,12,6\}$

Have you noticed anything about the previous examples? It looks like every possible remainder (other than $0$ ) shows up exactly once, (though obviously not in order). Will this always be true?

The fact that $0$ doesn’t show up is no mystery: we specified that $a$ is not divisible by $p$ , and in that case none of $a, 2a, \dots, (p-1)a$ will be divisible by $p$ either, so none of them have a remainder of $0$ . But why would their remainders all be different?

Suppose there are two multiples of $a$ , say, $ja$ and $ka$ , which have the same remainder when divided by $p$ . We can write this as $ja \equiv ka \pmod p$ . Subtracting $ka$ from both sides and factoring out $a$ , we find that $a(j-k) \equiv 0 \pmod p$ , that is, $a(j-k)$ is divisible by $p$ . Well, when a prime divides a product of two things, it must divide one or the other (or both). But we already assumed $a$ is not divisible by $p$ . Hence $p$ must evenly divide $j-k$ . But $j$ and $k$ are both less than $p$ , so their difference must lie strictly between $-p$ and $p$ . The only multiple of $p$ strictly between $-p$ and $p$ is zero, so $j - k = 0$ , that is, $j = k$ . So the only way to have $ja \equiv ka \pmod p$ is if $j = k$ . Put the other way around, we’ve shown that if $j \neq k$ then $ja$ and $ka$ don’t have the same remainder $\pmod p$ . So this proves that all the multiples of $a$ from $a$ up to $(p-1)a$ have different remainders when divided by $p$ .

Finally, since there are exactly $p-1$ multiples of $a$ in our set, and $p-1$ possible nonzero remainders $\pmod p$ , and all the remainders have to be different, we conclude that each remainder shows up exactly once.

So what? Here comes the clever trick: what happens if we take all those multiples of $a$ and multiply them all together, and then take the remainder $\pmod p$ ? Since taking remainders commutes with multiplication (that is, $ab \bmod p \equiv (a \bmod p)(b \bmod p)$ ), this is the same as if we first take their remainders and then multiply those. But we already know that the remainders will contain each number from $1$ to $(p-1)$ exactly once—and if we’re multiplying them then the order doesn’t matter. So,

$a \cdot 2a \cdot 3a \cdot \dots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) \pmod p$ ,

that is, the product of all the multiples of $a$ has the same remainder as the factorial of $(p-1)$ when divided by $p$ . For example, looking at the example of $p = 7$ and $a = 3$ again, the product of the multiples of $a$ is $3 \cdot 6 \cdot 9 \cdot 12 \cdot 15 \cdot 18 = 524880$ , whereas $6! = 720$ ; but both have a remainder of $6$ when divided by $p = 7$ .

Now, we can factor the $(p-1)$ copies of $a$ out of the left side, and we are left with

$a^{p-1} (p-1)! \equiv (p-1)! \pmod p$

Now we just want to cancel $(p-1)!$ from both sides—though we have to be a little careful when dividing both sides of a modular equation. In general it’s only valid when the thing you want to divide by is relatively prime to the modulus (this same issue came up in my previous post). But that is indeed the case here: $(p-1)!$ is not divisible by $p$ (since $p$ is prime and $(p-1)!$ is the product of a bunch of things that are all smaller than $p$ ). So we are justified in dividing both sides by it, and this completes the proof:

$a^{p-1} \equiv 1 \pmod p$ .

About Brent

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

View all posts by Brent →

8 Responses to Fermat’s Little Theorem: proof by modular arithmetic

Anthony says:

November 13, 2017 at 5:48 pm

Did Fermat give a proof?
- Brent says:
  
  November 13, 2017 at 6:00 pm
  
  Actually, he didn’t: he stated the theorem in a letter to a friend, but never published a proof. However, it seems likely that he did, in fact, know of one (unlike the case of his infamous “Last” theorem).
  - Kaligule says:
    
    November 14, 2017 at 10:48 am
    
    Or he was just really good at guessing.
Pingback: The Little One – The nth Root
Naren Sundar says:

November 14, 2017 at 7:56 pm

Hi Brent. Instead of the proof by contradiction you have given for all the remainders being unique, is there a more direct way to establish a bijection between the remainders and the multiples?
- Brent says:
  
  November 14, 2017 at 9:07 pm
  
  Hi Naren, I don’t think I gave a proof by contradiction; which part is it that looks like a proof by contradiction to you? The function sending multiples to remainders is $j \mapsto j a \pmod p$ . I proved that function is injective, i.e. $(ja \equiv ka \pmod p) \implies (j = k)$ , and any injective function between two finite sets of the same size must be a bijection.
  - Naren Sundar says:
    
    November 14, 2017 at 9:19 pm
    
    You’re right. I forgot that we already had a map to start with and that we just needed to show injectivity! I looked at the initial statement “suppose ja and ka have the same remainder” and concluded that it was a proof by contradiction. Thanks!
Pingback: Euler’s Theorem: proof by modular arithmetic | The Math Less Traveled