Introduction to Fermat's Little Theorem
Fermat's Little Theorem is one of the most elegant and powerful results in number theory. First discovered by Pierre de Fermat in 1640, it provides a fundamental relationship between prime numbers and modular arithmetic that has profound implications in cryptography, computer science, and pure mathematics.
Pierre de Fermat (1607-1665) was a French lawyer and mathematician who made significant contributions to number theory, probability, and analytic geometry. While he often stated theorems without proof, his Little Theorem was one of the few he claimed to have proven. The first published proof came from Leonhard Euler in 1736.
Why Fermat's Little Theorem Matters:
- Foundation for modern public-key cryptography (RSA)
- Essential for primality testing algorithms
- Provides efficient computation of large modular exponentiations
- Connects group theory and number theory
- Generalizes to Euler's Theorem and Carmichael's Theorem
- Used in error-correcting codes and digital signatures
This guide will take you from the basic statement of the theorem through multiple proofs, practical applications, computational implementations, and interactive practice problems to ensure deep understanding.
Fermat's Little Theorem: Formal Statement
Then: ap-1 ≡ 1 (mod p)
In words: For any integer a not divisible by a prime p, raising a to the power (p-1) gives a number that is congruent to 1 modulo p.
Alternative Form: For any integer a and prime p:
This form holds for all integers a, including those divisible by p (in which case both sides are congruent to 0 modulo p).
Examples:
Let p = 5 (prime), a = 2:
24 = 16 ≡ 1 (mod 5) ✓
Let p = 7 (prime), a = 3:
36 = 729 ≡ 1 (mod 7) because 729 ÷ 7 = 104 remainder 1 ✓
Let p = 11 (prime), a = 4:
410 = 1,048,576 ≡ 1 (mod 11) ✓
Theorem Verifier
Modular Arithmetic: Essential Background
Understanding modular arithmetic is crucial for working with Fermat's Little Theorem. Modular arithmetic, often called "clock arithmetic," deals with remainders after division.
Definition: a ≡ b (mod n) if and only if n divides (a - b).
Equivalently, a and b have the same remainder when divided by n.
Modular Clock Visualization (mod 7)
Select a number to see its equivalence class:
Addition: If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n)
Multiplication: If a ≡ b (mod n) and c ≡ d (mod n), then a × c ≡ b × d (mod n)
Exponentiation: If a ≡ b (mod n), then ak ≡ bk (mod n) for any positive integer k
Cancellation: If gcd(c, n) = 1 and ac ≡ bc (mod n), then a ≡ b (mod n)
Multiplicative Inverses in Modular Arithmetic:
For a modulo n, the multiplicative inverse exists if and only if gcd(a, n) = 1.
If gcd(a, n) = 1, then there exists an integer b such that:
This inverse is unique modulo n and is denoted a-1 (mod n).
Example: Find the multiplicative inverse of 3 modulo 7.
We need x such that 3x ≡ 1 (mod 7).
Testing values: 3×5 = 15 ≡ 1 (mod 7), so 3-1 ≡ 5 (mod 7).
Verification: 3 × 5 = 15, 15 ÷ 7 = 2 remainder 1 ✓
Multiple Proofs of Fermat's Little Theorem
One of the beautiful aspects of Fermat's Little Theorem is that it can be proven in several different ways, each offering unique insights. Here we present three elegant proofs.
Step 1: Consider the multiplicative group (ℤ/pℤ)× of integers modulo p that are coprime to p.
Step 2: This group has order p-1 (since there are p-1 numbers from 1 to p-1 that are coprime to p).
Step 3: By Lagrange's Theorem, the order of any element divides the order of the group.
Step 4: Therefore, for any a in (ℤ/pℤ)×, ap-1 = 1 in the group, which means ap-1 ≡ 1 (mod p).
Step 1: First prove that for any integer a, ap ≡ a (mod p) by induction on a.
Step 2: Base case: 0p ≡ 0 (mod p) and 1p ≡ 1 (mod p).
Step 3: Inductive step: Assume kp ≡ k (mod p). Consider (k+1)p.
Step 4: By the binomial theorem: (k+1)p = Σi=0p C(p,i) ki.
Step 5: For 0 < i < p, C(p,i) is divisible by p, so (k+1)p ≡ kp + 1 (mod p).
Step 6: By inductive hypothesis, this is ≡ k + 1 (mod p), completing the induction.
Step 7: If gcd(a,p) = 1, we can cancel a from ap ≡ a (mod p) to get ap-1 ≡ 1 (mod p).
Step 1: Consider the set S = {a, 2a, 3a, ..., (p-1)a} modulo p.
Step 2: Since gcd(a,p) = 1, multiplication by a is a permutation of ℤ/pℤ.
Step 3: Therefore, S contains each nonzero residue exactly once.
Step 4: Multiply all elements of S: a × 2a × 3a × ... × (p-1)a ≡ 1 × 2 × 3 × ... × (p-1) (mod p).
Step 5: Simplify: ap-1 × (p-1)! ≡ (p-1)! (mod p).
Step 6: Since (p-1)! is not divisible by p, we can cancel it to get ap-1 ≡ 1 (mod p).
Interactive Proof Explorer
Select a proof type to see detailed explanation and visualization.
Applications of Fermat's Little Theorem
Fermat's Little Theorem has numerous practical applications in cryptography, computer science, and mathematics. Here are the most important ones:
RSA Cryptography
The foundation of RSA public-key encryption relies on Fermat's Little Theorem and Euler's generalization.
Key Insight: For RSA modulus n = pq (product of two primes), for any message m with gcd(m,n) = 1:
mφ(n) ≡ 1 (mod n), where φ(n) = (p-1)(q-1) (Euler's totient function)
This ensures that encryption and decryption are inverse operations.
Primality Testing
Fermat's Little Theorem provides the basis for the Fermat primality test.
Test: To test if n is prime, check if an-1 ≡ 1 (mod n) for several bases a.
If it fails for any a with gcd(a,n) = 1, n is composite. If it passes for many a, n is probably prime.
Note: There are Carmichael numbers that pass the test but are composite.
Modular Exponentiation
Fermat's Little Theorem enables efficient computation of large modular exponentiations.
Example: Compute 7100 (mod 11)
Since 11 is prime and gcd(7,11) = 1, by FLT: 710 ≡ 1 (mod 11)
Thus 7100 = (710)10 ≡ 110 = 1 (mod 11)
This reduces exponentiation from 100 to 10 operations.
Modular Inverses
Compute modular inverses efficiently using Fermat's Little Theorem.
Formula: For prime p and a with gcd(a,p) = 1:
a-1 ≡ ap-2 (mod p)
Example: Find 5-1 (mod 7)
55 = 3125 ≡ 3 (mod 7), so 5-1 ≡ 3 (mod 7)
Verification: 5 × 3 = 15 ≡ 1 (mod 7) ✓
Problem: In RSA with p=3, q=11, public exponent e=7, find the private exponent d.
Step 1: Compute n = p × q = 3 × 11 = 33
Step 2: Compute φ(n) = (p-1)(q-1) = 2 × 10 = 20
Step 3: Find d such that e × d ≡ 1 (mod φ(n)), i.e., 7d ≡ 1 (mod 20)
Step 4: Using FLT-based inverse: d ≡ 7φ(20)-1 (mod 20)
φ(20) = 8, so d ≡ 77 (mod 20)
Step 5: Compute 72 = 49 ≡ 9 (mod 20)
74 = 92 = 81 ≡ 1 (mod 20)
77 = 74 × 72 × 7 ≡ 1 × 9 × 7 = 63 ≡ 3 (mod 20)
Step 6: Verify: 7 × 3 = 21 ≡ 1 (mod 20) ✓
Answer: The private exponent d = 3.
Generalizations and Related Theorems
Fermat's Little Theorem has several important generalizations that extend its applicability beyond prime moduli.
Then: aφ(n) ≡ 1 (mod n)
Where φ(n) is Euler's totient function, which counts the numbers from 1 to n that are coprime to n.
Note: When n is prime, φ(n) = n-1, so Euler's Theorem reduces to Fermat's Little Theorem.
Example of Euler's Theorem:
Let n = 15, φ(15) = 8 (numbers coprime to 15: 1,2,4,7,8,11,13,14)
Take a = 7 with gcd(7,15) = 1:
78 = 5,764,801 ≡ 1 (mod 15) because 5,764,801 ÷ 15 = 384,320 remainder 1 ✓
Then for any a with gcd(a, n) = 1: aλ(n) ≡ 1 (mod n)
Where λ(n) is the smallest positive integer such that the congruence holds for all a coprime to n.
Note: λ(n) divides φ(n) and gives a tighter bound than Euler's Theorem.
Relationship with Chinese Remainder Theorem:
Fermat's Little Theorem can be combined with the Chinese Remainder Theorem to solve systems of congruences and compute modular exponentiations efficiently for composite moduli.
For n = p1k₁p2k₂...prkᵣ, we can compute am (mod n) by computing it modulo each prime power and combining the results.
Theorem Generalization Explorer
Computational Aspects and Algorithms
Implementing Fermat's Little Theorem efficiently requires understanding computational number theory and algorithm design.
function modExp(base, exp, mod) {
if (mod === 1) return 0;
let result = 1;
base = base % mod;
while (exp > 0) {
if (exp & 1) {
result = (result * base) % mod;
}
exp = exp >> 1;
base = (base * base) % mod;
}
return result;
}
// Using FLT to compute modular inverse for prime modulus
function modInverseFLT(a, p) {
// Assumes p is prime and gcd(a, p) = 1
return modExp(a, p - 2, p);
}
Fast Modular Exponentiation: O(log e) multiplications, where e is the exponent.
Using FLT: For prime modulus p, computing ap-2 (mod p) takes O(log p) operations.
Without FLT: Computing a-1 via extended Euclidean algorithm takes O(log p) operations.
Conclusion: Both methods have similar asymptotic complexity, but FLT provides conceptual clarity and direct connection to exponentiation.
Efficient Approach: Using FLT for modular inverse
Algorithm: Compute ap-2 (mod p) using fast exponentiation
Complexity: O(log p) multiplications
Advantage: Conceptually simple, uses same exponentiation routine
Alternative Efficient Approach: Extended Euclidean Algorithm
Algorithm: Solve ax + py = 1 using Euclid's algorithm
Complexity: O(log p) operations
Advantage: Works for composite moduli too
Inefficient Approach: Brute force search
Algorithm: Try all numbers from 1 to p-1
Complexity: O(p) operations
Disadvantage: Impractical for large primes
Algorithm Performance Comparison
Interactive Practice Problems
Fermat's Little Theorem Practice Tool
Practice all aspects of Fermat's Little Theorem with randomly generated problems or create your own.
Select a topic and click "Generate Problem"
Solution:
1. Since 101 is prime and gcd(3,101) = 1, by FLT: 3100 ≡ 1 (mod 101)
2. Therefore, 3100 (mod 101) = 1
Verification: 3100 = 515377520732011331036461129765621272702107522001
Dividing by 101 gives remainder 1 ✓
Solution:
1. We want 7100 (mod 100)
2. Use Chinese Remainder Theorem: 100 = 4 × 25
3. Compute 7100 (mod 4): 7 ≡ 3 (mod 4), 32 ≡ 1 (mod 4), so 3100 = (32)50 ≡ 150 = 1 (mod 4)
4. Compute 7100 (mod 25): Since φ(25)=20, by Euler's Theorem: 720 ≡ 1 (mod 25)
5. So 7100 = (720)5 ≡ 15 = 1 (mod 25)
6. Solve x ≡ 1 (mod 4) and x ≡ 1 (mod 25) → x ≡ 1 (mod 100)
Answer: The last two digits are 01
Fermat's Little Theorem Summary & Cheat Sheet
| Concept | Statement | Conditions | Applications |
|---|---|---|---|
| Fermat's Little Theorem | ap-1 ≡ 1 (mod p) | p prime, gcd(a,p)=1 | Primality testing, modular inverses |
| Alternative Form | ap ≡ a (mod p) | p prime, any a | Simplifies calculations |
| Euler's Theorem | aφ(n) ≡ 1 (mod n) | gcd(a,n)=1 | RSA cryptography, general moduli |
| Carmichael's Theorem | aλ(n) ≡ 1 (mod n) | gcd(a,n)=1 | Tightest exponent, composite moduli |
| Modular Inverse via FLT | a-1 ≡ ap-2 (mod p) | p prime, gcd(a,p)=1 | Efficient inverse computation |
Mistake: Applying FLT to composite moduli
Wrong: 210 ≡ 1 (mod 11) but 214 ≢ 1 (mod 15)
Correct: FLT only applies when modulus is prime
Mistake: Forgetting the gcd condition
Wrong: 610 ≡ 1 (mod 11) (false, gcd(6,11)=1 actually works here)
Wrong Example: 1110 ≡ 1 (mod 11) is false because gcd(11,11)=11≠1
Correct: Require gcd(a,p)=1 for ap-1 ≡ 1 (mod p)
Mistake: Confusing with Fermat's Last Theorem
Wrong: xn + yn = zn has no solutions (that's Fermat's Last Theorem)
Correct: Fermat's Little Theorem is about modular exponentiation
Mistake: Assuming converse is true
Wrong: If an-1 ≡ 1 (mod n), then n is prime
Correct: Carmichael numbers satisfy this but are composite
- Always check conditions: Is p prime? Is gcd(a,p)=1?
- Use the corollary form: ap ≡ a (mod p) works for all a, including multiples of p
- Combine with Chinese Remainder Theorem: For composite moduli, break into prime powers
- Use fast exponentiation: Implement modular exponentiation in O(log n) time
- Remember generalizations: Euler's Theorem extends FLT to composite moduli
- Practice with large numbers: Real applications use 100+ digit primes