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 :
Notice how raising any integer to the -th power modulo returns the original value .
Formal Definitions and Notation
Fermat's Little Theorem (FLT) states that if is a prime number and is any integer, then:
If is not divisible by or in other words are coprime to eachother (that is, ), we can divide both sides by to get the more primarily used form:
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 must be a prime number.
Scaffolded Examples
Direct Application (Easy)
Find .
Solution:
Since is a prime number and , we apply Fermat's Little Theorem:
Next, we divide the exponent by :
Since is a multiple of , we can rewrite as:
So our answer is:
Slightly Harder Problem (Medium)
Find the remainder when is divided by .
Solution:
First, simplify the base modulo :
Since is prime and , per FLT we know . Thus, we try to express the exponent modulo :
This tells us that for some integer . Now, substitute this back into our original expression modulo :
Finally, :
Yields
Notice this can apply to alot of problems.
Olympiad Application (Hard)
Determine all prime numbers such that divides .
Solution
The condition can be written in modular arithmetic as:
By Fermat's Little Theorem, for any prime , we know:
We now have two distinct equivalences for . Equating them gives:
Working out gives:
This implies that must be a prime factor of . Since is prime, the only possible candidate is .
As a sufficiency check, we check if satisfies the original condition:
And because , we know:
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 and an integer that are coprime (), any power can be written by reducing the exponent modulo :
this is as seen in the easy example above.
Finding Modular Inverses
Since , the multiplicative inverse of modulo a prime is directly given by:
This is especially useful when in time constrained competitions such as AMC and AIME.
When to Use Which Technique
| Situation | Recommended Tool |
|---|---|
| Large powers modulo prime when coprime | Reduce the exponent modulo |
| Nested powers | Reduce modulo first, then reduce modulo , very general use |
| Modular division / inverse modulo prime | See above |
Practice Problems
| Status | Source | Problem Name | Difficulty | Tags | ||
|---|---|---|---|---|---|---|
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.
