The Intuition Behind Fermat's Little Theorem

Imagine a theorem so fundamental to Olympiad mathematics number theory problems that you are bound to come across it in some way or form during any competition; that theorem is the so called Fermat's Little Theorem named after the 17th century polymath Pierre De Fermat (the funny thing is he never wrote it down and only briefly mentioned it in a letter). Even so it is often abbreviated as 'FLT' in the math Olympiad community. To build intuition, consider powers of integers with modulo a prime number, say p=5p = 5:

  • 25=32≡2(mod5)2^5 = 32 \equiv 2 \pmod 5
  • 35=243≡3(mod5)3^5 = 243 \equiv 3 \pmod 5
  • 45=1024≡4(mod5)4^5 = 1024 \equiv 4 \pmod 5

Notice how raising any integer aa to the pp-th power modulo pp returns the original value aa.

Formal Definitions and Notation

Fermat's Little Theorem (FLT) states that if pp is a prime number and nn is any integer, then:

np≡n(modp)[form 1]n^p \equiv n \pmod{p} \quad \text{[form 1]}

If nn is not divisible by pp or in other words are coprime to eachother (that is, gcd⁡(n,p)=1\gcd(n, p) = 1), we can divide both sides by nn to get the more primarily used form:

np−1≡1(modp)[form 2]n^{p-1} \equiv 1 \pmod{p} \quad \text{[form 2]}

The 2 forms are used interchangeably; it is important you know that they are the same thing and are able to recognise them quickly.

Important note: The modulus pp must be a prime number.

Scaffolded Examples

Direct Application (Easy)

Find 7224(mod17)7^{224} \pmod{17}.

Solution:

Since 1717 is a prime number and gcd⁡(7,17)=1\gcd(7, 17) = 1, we apply Fermat's Little Theorem:

716≡1(mod17)7^{16} \equiv 1 \pmod{17}

Next, we divide the exponent 224224 by 1616:

224=16⋅14+0224 = 16 \cdot 14 + 0

Since 224224 is a multiple of 1616, we can rewrite 72247^{224} as:

7224=(716)14≡114≡1(mod17)7^{224} = (7^{16})^{14} \equiv 1^{14} \equiv 1 \pmod{17}

So our answer is:

1\boxed{1}

Slightly Harder Problem (Medium)

Find the remainder when 17171717^{17^{17}} is divided by 77.

Solution:

First, simplify the base modulo 77:

17≡3(mod7)  ⟹  171717≡31717(mod7)17 \equiv 3 \pmod 7 \implies 17^{17^{17}} \equiv 3^{17^{17}} \pmod 7

Since 77 is prime and gcd⁡(3,7)=1\gcd(3, 7) = 1, per FLT we know 36≡1(mod7)3^6 \equiv 1 \pmod 7. Thus, we try to express the exponent 171717^{17} modulo 66:

17≡−1(mod6)17 \equiv -1 \pmod 6
1717≡(−1)17≡−1≡5(mod6)17^{17} \equiv (-1)^{17} \equiv -1 \equiv 5 \pmod 6

This tells us that 1717=6k+517^{17} = 6k + 5 for some integer kk. Now, substitute this back into our original expression modulo 77:

31717=36k+5=(36)k⋅35≡1k⋅35(mod7)3^{17^{17}} = 3^{6k + 5} = (3^6)^k \cdot 3^5 \equiv 1^k \cdot 3^5 \pmod 7

Finally, 35(mod7)3^5 \pmod 7:

35=243=7⋅34+5≡5(mod7)3^5 = 243 = 7 \cdot 34 + 5 \equiv 5 \pmod 7

Yields

5\boxed{5}

Notice this can apply to alot of problems.

Olympiad Application (Hard)

Determine all prime numbers pp such that pp divides 2p+12^p + 1.

Solution

The condition p∣(2p+1)p \mid (2^p + 1) can be written in modular arithmetic as:

2p+1≡0(modp)  ⟹  2p≡−1(modp)2^p + 1 \equiv 0 \pmod p \implies 2^p \equiv -1 \pmod p

By Fermat's Little Theorem, for any prime pp, we know:

2p≡2(modp)2^p \equiv 2 \pmod p

We now have two distinct equivalences for 2p(modp)2^p \pmod p. Equating them gives:

2≡−1(modp)2 \equiv -1 \pmod p

Working out gives:

3≡0(modp)3 \equiv 0 \pmod p

This implies that pp must be a prime factor of 33. Since 33 is prime, the only possible candidate is p=3p = 3.

As a sufficiency check, we check if p=3p = 3 satisfies the original condition:

23+1=8+1=92^3 + 1 = 8 + 1 = 9

And because 3∣93 \mid 9, we know:

3\boxed{3}

is the answer.

Reference Guide

Fermat's Little Theorem provides a powerful set of tools for simplifying modular exponentiation, finding modular inverses, and solving divisibility problems involving primes. In fact is is a special case of Euler's theorem when n is a prime number. In number theory, considering FLT as an intermediate step should be thought of firsthand when seeing a prime number.

Modulo Exponent Simplifying

For a prime pp and an integer aa that are coprime (gcd⁡(a,p)=1\gcd(a, p) = 1), any power ak(modp)a^k \pmod p can be written by reducing the exponent kk modulo p−1p - 1:

ak≡ak(modp−1)(modp)a^k \equiv a^{k \pmod{p-1}} \pmod p

this is as seen in the easy example above.

Finding Modular Inverses

Since a⋅ap−2=ap−1≡1(modp)a \cdot a^{p-2} = a^{p-1} \equiv 1 \pmod p, the multiplicative inverse of aa modulo a prime pp is directly given by:

a−1≡ap−2(modp)a^{-1} \equiv a^{p-2} \pmod p

This is especially useful when in time constrained competitions such as AMC and AIME.

When to Use Which Technique

SituationRecommended Tool
Large powers modulo aa prime pp when coprimeReduce the exponent modulo p−1p-1
Nested powers abc(modp)a^{b^c} \pmod pReduce bcb^c modulo p−1p-1 first, then reduce aa modulo pp, very general use
Modular division / inverse modulo aa prime ppSee above

Practice Problems

StatusSourceProblem NameDifficultyTags

Module Progress:

Join the Discord Community!

Stuck on a problem, or don't understand a module? Join the Discord and get help with your doubts while making more math friends.