Fermat's Little Theorem
I. In-Class Exercises
Programming Exercises
II. Knowledge Summary
Core Idea
Fermat's Little Theorem is one of the most important theorems in number theory:
If p is prime and a is not a multiple of p, then a^(p-1) ≡ 1 (mod p).
An equivalent form is: for any integer a, a^p ≡ a (mod p).
Fermat's Little Theorem is the theoretical basis for modular inverses
a^(-1) ≡ a^(p-2) mod p,
and it is also the reason fast exponentiation is so widely used in modular arithmetic.
Theorem Statement and Proof
Theorem
If p is prime and gcd(a, p) = 1, then a^(p-1) ≡ 1 (mod p).
Proof Using the Multiplicative Group Modulo p
Consider the set {1, 2, 3, ..., p-1}. Multiply every element by a, obtaining
{a, 2a, 3a, ..., (p-1)a}.
Key property: these numbers, reduced modulo p, are still a permutation of {1, 2, ..., p-1}.
Proof: if ia ≡ ja (mod p) with i ≠ j, then (i-j)a ≡ 0 (mod p). Since gcd(a,p)=1, it follows that p | (i-j). But 1 ≤ i, j ≤ p-1, so |i-j| < p, a contradiction. Therefore these p-1 values are pairwise distinct modulo p.
Multiply the two sets together:
(a)(2a)(3a)...((p-1)a) ≡ 1 × 2 × 3 × ... × (p-1) (mod p)
a^(p-1) × (p-1)! ≡ (p-1)! (mod p)Since gcd((p-1)!, p) = 1, divide both sides by (p-1)! to obtain:
a^(p-1) ≡ 1 (mod p)Corollaries
a^(-1) ≡ a^(p-2) (mod p): this is the standard way to compute modular inverses with Fermat's theorem.a^n mod p = a^(n mod (p-1)) mod pwhengcd(a,p)=1: useful for exponent reduction.
Code Implementation
Fast Exponentiation
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6// Fast exponentiation: compute a^n mod p
7ll power(ll a, ll n, ll p) {
8 ll result = 1;
9 a %= p;
10
11 while (n > 0) {
12 if (n & 1) {
13 result = result * a % p;
14 }
15 a = a * a % p;
16 n >>= 1;
17 }
18 return result;
19}
20
21int main() {
22 ios::sync_with_stdio(false);
23 cin.tie(nullptr);
24
25 ll a, n, p;
26 cin >> a >> n >> p;
27
28 cout << a << "^" << n << " mod " << p << " = "
29 << power(a, n, p) << "\n";
30
31 return 0;
32}Application: Reducing Huge Exponents
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5
6ll power(ll a, ll n, ll p) {
7 ll result = 1;
8 a %= p;
9 while (n > 0) {
10 if (n & 1) result = result * a % p;
11 a = a * a % p;
12 n >>= 1;
13 }
14 return result;
15}
16
17// Compute a^(b^c) mod p, where p is prime
18ll solve(ll a, ll b, ll c, ll p) {
19 if (a % p == 0) return 0;
20
21 ll exp = power(b, c, p - 1);
22 return power(a, exp, p);
23}
24
25int main() {
26 ios::sync_with_stdio(false);
27 cin.tie(nullptr);
28
29 ll a, b, c, p;
30 cin >> a >> b >> c >> p;
31
32 cout << a << "^(" << b << "^" << c << ") mod " << p
33 << " = " << solve(a, b, c, p) << "\n";
34
35 return 0;
36}Binomial Coefficients Modulo a Prime
1#include <bits/stdc++.h>
2using namespace std;
3
4typedef long long ll;
5const ll MOD = 1e9 + 7;
6const int MAXN = 1000005;
7
8ll fac[MAXN];
9ll inv_fac[MAXN];
10
11ll power(ll a, ll n, ll p) {
12 ll result = 1;
13 a %= p;
14 while (n > 0) {
15 if (n & 1) result = result * a % p;
16 a = a * a % p;
17 n >>= 1;
18 }
19 return result;
20}
21
22void init(int n) {
23 fac[0] = 1;
24 for (int i = 1; i <= n; i++) {
25 fac[i] = fac[i - 1] * i % MOD;
26 }
27
28 inv_fac[n] = power(fac[n], MOD - 2, MOD);
29
30 for (int i = n - 1; i >= 0; i--) {
31 inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
32 }
33}
34
35ll comb(int n, int k) {
36 if (k < 0 || k > n) return 0;
37 return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
38}
39
40int main() {
41 ios::sync_with_stdio(false);
42 cin.tie(nullptr);
43
44 init(MAXN - 1);
45
46 int n, k;
47 cin >> n >> k;
48
49 cout << "C(" << n << ", " << k << ") mod " << MOD
50 << " = " << comb(n, k) << "\n";
51
52 return 0;
53}Execution Example
Fast Exponentiation for 2^10 mod 1000000007
1n = 10 = 1010 (binary)
2
3Steps:
4n=10, bit=0: a=2, result=1 (do not multiply) -> a=4
5n=5, bit=1: a=4, result=1*4=4 -> a=16
6n=2, bit=0: a=16, result=4 (do not multiply) -> a=256
7n=1, bit=1: a=256, result=4*256=1024 -> a=65536
8
9Result: 2^10 = 1024 ✓Exponent Reduction with Fermat's Little Theorem
Compute 2^(3^100) mod 13:
1p = 13 (prime), so p-1 = 12
2
3Step 1: compute 3^100 mod 12
4 3^1 mod 12 = 3
5 3^2 mod 12 = 9
6 3^3 mod 12 = 27 mod 12 = 3
7 Pattern: 3^odd ≡ 3, 3^even ≡ 9 (mod 12)
8 Since 100 is even, 3^100 mod 12 = 9
9
10Step 2: compute 2^9 mod 13
11 2^1 = 2
12 2^2 = 4
13 2^4 = 16 mod 13 = 3
14 2^8 = 9
15 2^9 = 2^8 * 2^1 = 9 * 2 = 18 mod 13 = 5
16
17Result: 2^(3^100) mod 13 = 5Detailed Problem-Solving Steps
- Recognize when Fermat's Little Theorem applies:
- modular inverse:
a^(-1) = a^(p-2) mod p - modular exponentiation with huge exponents: reduce the exponent modulo
p-1 - binomial coefficients modulo a prime: use inverse factorials
- modular inverse:
- Implement fast exponentiation: this is the computational basis of the theorem
- Use preprocessing when needed: for repeated binomial-coefficient queries, precompute factorials and inverse factorials
- Handle special cases: if
ais a multiple ofp, thena^(p-1)is 0, not 1
Common Mistakes
- Ignoring the condition
gcd(a,p)=1: ifais a multiple ofp, exponent reduction via Fermat's theorem does not apply - Overflow in fast exponentiation:
a * amay exceedint, so uselong long; if the modulus is near10^18, use__int128 - Using the wrong modulus for exponent reduction: in
a^n mod p, reduce the exponent modulop-1, not modulop - Using the wrong direction for inverse-factorial recurrence: compute
inv_fac[n]first, then iterate backward fromn-1to0 - Forgetting the case
k > nin binomial coefficients: it should return 0
Evaluation
| Metric | Value |
|---|---|
| Fast exponentiation time complexity | O(log n) |
| Binomial precomputation | O(n + log p) |
| Single binomial query | O(1) |
| Applicability | The modulus p must be prime |
| Contest frequency | Extremely high |
Fermat's Little Theorem and fast exponentiation are among the most fundamental and frequently used tools in algorithm contests. They are essential not only for modular inverses, but also for combinatorial counting, matrix exponentiation, and many other topics.