Fermat's Little Theorem: Definition, Proof, Examples, Applications

Fermat’s Little Theorem is one of the most elegant and useful results in number theory. It gives a clean, powerful way to compute large powers modulo a prime — turning what might seem like an impossibly large calculation into a simple remainder problem. It appears in the Euclid Contest, the COMC, and the Canadian Mathematical Olympiad, and it is the foundation for several important results in modern cryptography, including RSA encryption.

This guide explains Fermat’s Little Theorem clearly, proves it in two ways, works through examples at increasing difficulty, and shows how to apply it strategically in competition problems.

What Is Fermat’s Little Theorem?

Fermat’s Little Theorem states:

If $p$ p is a prime number and $a$ a is an integer not divisible by $p$ p, then: $a^{p-1} \equiv 1 \pmod{p}$ ap−1≡1(modp)

Equivalently (and more generally, without the divisibility condition): $a^p \equiv a \pmod{p}$ ap≡a(modp)

In plain English: Raise any integer $a$ a to the power $p$ p (where $p$ p is prime) and divide by $p$ p — the remainder is $a$ a itself. Or: raise $a$ a to the power $p – 1$ p−1 (when $p$ p does not divide $a$ a) — the remainder when divided by $p$ p is always 1.

A first example:

Let $p = 7$ p=7 and $a = 2$ a=2.

$2^{7-1} = 2^6 = 64 = 9 \times 7 + 1$ 27−1=26=64=9×7+1, so $2^6 \equiv 1 \pmod{7}$ 26≡1(mod7). ✓

$2^7 = 128 = 18 \times 7 + 2$ 27=128=18×7+2, so $2^7 \equiv 2 \pmod{7}$ 27≡2(mod7). ✓

Another example:

Let $p = 5$ p=5 and $a = 3$ a=3.

$3^4 = 81 = 16 \times 5 + 1$ 34=81=16×5+1, so $3^4 \equiv 1 \pmod{5}$ 34≡1(mod5). ✓

The theorem works for every prime $p$ p and every integer $a$ a not divisible by $p$ p — always.

A Brief History

Pierre de Fermat stated this theorem in a letter in 1640 — without proof. (Fermat was notorious for claiming results without publishing proofs; his marginal note about Fermat’s Last Theorem is the most famous example.) The first published proof was given by Leonhard Euler in 1736, nearly a century later.

The name “Little” Theorem distinguishes it from Fermat’s Last Theorem ( $a^n + b^n = c^n$ an+bn=cn has no positive integer solutions for $n \geq 3$ n≥3) — which is little in the sense of being easier to state, not in the sense of being less important. In practice, Fermat’s Little Theorem is far more useful in everyday mathematics than the Last Theorem.

Two Proofs of Fermat’s Little Theorem

Proof 1: The Necklace Argument (Most Elegant)

Consider sequences of length $p$ p using $a$ a colours (where $p$ p is prime and $a > 0$ a>0). The number of such sequences is $a^p$ ap.

Of these, exactly $a$ a are constant sequences (all the same colour). The remaining $a^p – a$ ap−a sequences are non-constant.

Now arrange each non-constant sequence in a circle (a necklace). Each necklace corresponds to exactly $p$ p sequences (the $p$ p rotations of the circular arrangement) — and these are all distinct because $p$ p is prime and the sequence is non-constant.

Therefore $a^p – a$ ap−a is divisible by $p$ p: $p \mid a^p – a \implies a^p \equiv a \pmod{p}$ p∣ap−a⟹ap≡a(modp)

This proves the second (more general) form of Fermat’s Little Theorem. $\square$ □

Why primality matters: If $p$ p were not prime — say $p = 4$ p=4 — the rotations of a non-constant circular sequence might not all be distinct (e.g., the sequence ABAB has period 2, so its 4 rotations give only 2 distinct sequences). The argument breaks down. The theorem is specifically about primes.

Proof 2: The Cancellation Argument (Standard Algebraic Proof)

We prove $a^{p-1} \equiv 1 \pmod{p}$ ap−1≡1(modp) for $\gcd(a, p) = 1$ gcd(a,p)=1.

Consider the $p – 1$ p−1 numbers: $a, 2a, 3a, \ldots, (p-1)a$ a,2a,3a,…,(p−1)a modulo $p$ p.

Claim: These are all distinct modulo $p$ p, and none is $\equiv 0$ ≡0.

Distinct: If $ia \equiv ja \pmod{p}$ ia≡ja(modp) for $1 \leq i < j \leq p-1$ 1≤i<j≤p−1, then $p \mid (j-i)a$ p∣(j−i)a. Since $\gcd(a,p) = 1$ gcd(a,p)=1 and $0 < j-i < p$ 0<j−i<p, this is impossible. So all values are distinct.

Non-zero: Since $\gcd(a,p) = 1$ gcd(a,p)=1, none of $a, 2a, \ldots, (p-1)a$ a,2a,…,(p−1)a is divisible by $p$ p.

Therefore $\{a, 2a, \ldots, (p-1)a\} \equiv \{1, 2, \ldots, p-1\} \pmod{p}$ {a,2a,…,(p−1)a}≡{1,2,…,p−1}(modp) (as sets).

Multiplying all elements of each set: $a \cdot 2a \cdot 3a \cdots (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots (p-1) \pmod{p}$ a⋅2a⋅3a⋯(p−1)a≡1⋅2⋅3⋯(p−1)(modp) $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$ ap−1⋅(p−1)!≡(p−1)!(modp)

Since $\gcd((p-1)!, p) = 1$ gcd((p−1)!,p)=1, we can cancel $(p-1)!$ (p−1)!: $a^{p-1} \equiv 1 \pmod{p} \quad \square$ ap−1≡1(modp)□

How to Use Fermat’s Little Theorem: Computing Large Powers

The most immediate application of Fermat’s Little Theorem is computing $a^n \pmod{p}$ an(modp) for large $n$ n.

Method:

Reduce the exponent $n$ n modulo $p – 1$ p−1 (since $a^{p-1} \equiv 1$ ap−1≡1, the powers repeat with period $p – 1$ p−1).
If $n = q(p-1) + r$ n=q(p−1)+r with $0 \leq r < p-1$ 0≤r<p−1, then $a^n = (a^{p-1})^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r \pmod{p}$ an=(ap−1)q⋅ar≡1q⋅ar≡ar(modp).
Compute $a^r \pmod{p}$ ar(modp) directly (since $r < p – 1$ r<p−1, this is manageable).

Example 1: Find $2^{100} \pmod{7}$ 2100(mod7).

$p = 7$ p=7, so $a^{p-1} = 2^6 \equiv 1 \pmod{7}$ ap−1=26≡1(mod7).

$100 = 16 \times 6 + 4$ 100=16×6+4, so $2^{100} = (2^6)^{16} \cdot 2^4 \equiv 1^{16} \cdot 16 \equiv 16 \equiv 2 \pmod{7}$ 2100=(26)16⋅24≡116⋅16≡16≡2(mod7).

Answer: 2100≡2(mod7)2^{100} \equiv 2 \pmod{7} 2100≡2(mod7).

Example 2: Find $3^{200} \pmod{11}$ 3200(mod11).

$p = 11$ p=11, so $3^{10} \equiv 1 \pmod{11}$ 310≡1(mod11).

$200 = 20 \times 10 + 0$ 200=20×10+0, so $3^{200} = (3^{10})^{20} \equiv 1^{20} = 1 \pmod{11}$ 3200=(310)20≡120=1(mod11).

Answer: 3200≡1(mod11)3^{200} \equiv 1 \pmod{11} 3200≡1(mod11).

Example 3: Find $7^{52} \pmod{13}$ 752(mod13).

$p = 13$ p=13, so $7^{12} \equiv 1 \pmod{13}$ 712≡1(mod13).

$52 = 4 \times 12 + 4$ 52=4×12+4, so $7^{52} \equiv 7^4 \pmod{13}$ 752≡74(mod13).

$7^2 = 49 = 3 \times 13 + 10$ 72=49=3×13+10, so $7^2 \equiv 10 \equiv -3 \pmod{13}$ 72≡10≡−3(mod13).

$7^4 = (7^2)^2 \equiv (-3)^2 = 9 \pmod{13}$ 74=(72)2≡(−3)2=9(mod13).

Answer: 752≡9(mod13)7^{52} \equiv 9 \pmod{13} 752≡9(mod13).

Competition math rewards students who recognise the right shortcut—not those who attempt the longest calculation. Our free assessment shows how confidently your child applies mathematical techniques to unfamiliar problems.

Get your child’s free feedback report →

Finding the Last Digits of Large Powers

Fermat’s Little Theorem handles modulo $p$ p for prime $p$ p. The most common “last digit” problems use modulo 10, but since 10 is not prime, Fermat’s Little Theorem does not apply directly. Instead, use modulo 2 and modulo 5 separately, then combine with the Chinese Remainder Theorem.

However, for problems specifically modulo a prime (modulo 7, 11, 13, 17, etc.), Fermat’s Little Theorem is the direct tool.

Example 4: What is the remainder when $6^{83}$ 683 is divided by 7?

$6 \equiv -1 \pmod{7}$ 6≡−1(mod7), so $6^{83} \equiv (-1)^{83} = -1 \equiv 6 \pmod{7}$ 683≡(−1)83=−1≡6(mod7).

(Here we did not even need Fermat’s Little Theorem — the base $6 \equiv -1$ 6≡−1 mod 7 makes the power trivial. This illustrates that sometimes simpler observations suffice.)

Example 5: What is the remainder when $5^{100}$ 5100 is divided by 11?

$p = 11$ p=11, so $5^{10} \equiv 1 \pmod{11}$ 510≡1(mod11).

$100 = 10 \times 10$ 100=10×10, so $5^{100} = (5^{10})^{10} \equiv 1^{10} = 1 \pmod{11}$ 5100=(510)10≡110=1(mod11).

Remainder = 1.

Extended Applications

Wilson’s Theorem (Companion Result)

Wilson’s Theorem states: $p$ p is prime if and only if $(p-1)! \equiv -1 \pmod{p}$ (p−1)!≡−1(modp).

This is a companion to Fermat’s Little Theorem — both involve primes and modular arithmetic, and both appear in competition number theory. The proof of Wilson’s Theorem uses the cancellation argument in the Fermat proof as a model.

Euler’s Generalisation

Euler generalised Fermat’s Little Theorem to non-prime moduli using the Euler totient function $\phi(n)$ ϕ(n) — the count of integers from 1 to $n$ n coprime to $n$ n: $a^{\phi(n)} \equiv 1 \pmod{n} \quad \text{when } \gcd(a, n) = 1$ aϕ(n)≡1(modn)when gcd(a,n)=1

When $n = p$ n=p (prime), $\phi(p) = p – 1$ ϕ(p)=p−1, recovering Fermat’s Little Theorem. Euler’s generalisation is the foundation of RSA cryptography.

Primality Testing

Fermat’s Little Theorem provides a quick (but imperfect) primality test: if $a^{n-1} \not\equiv 1 \pmod{n}$ an−1≡1(modn) for some $a$ a with $\gcd(a, n) = 1$ gcd(a,n)=1, then $n$ n is definitely not prime. This is the Fermat primality test.

The test is not foolproof — there exist composite numbers $n$ n (called Carmichael numbers) for which $a^{n-1} \equiv 1 \pmod{n}$ an−1≡1(modn) for all $\gcd(a,n) = 1$ gcd(a,n)=1. The smallest is 561 = 3 × 11 × 17. But as a quick filter for competition problems, the Fermat test is useful.

Where Fermat’s Little Theorem Appears in Contests

Fermat’s Little Theorem is standard toolkit at the senior competition level.

Euclid Contest (CEMC, Grade 12): Number theory problems appear in every Euclid, and computing powers modulo a prime is a recurring theme. A student who knows Fermat’s Little Theorem solves these in seconds; a student who does not may attempt direct calculation (impossible for large exponents) or pattern-finding (slower and less reliable). See our Euclid math contest guide.

COMC Part C: Divisibility proofs and modular arithmetic arguments appear at every level of the COMC. Fermat’s Little Theorem is one of the tools for establishing that certain expressions are always divisible by a prime. See our COMC math contest guide.

Canadian Mathematical Olympiad: Number theory at the CMO level regularly involves modular arithmetic arguments where Fermat’s Little Theorem is a key step. CMO number theory problems often require combining Fermat’s Little Theorem with other results (Wilson’s Theorem, the Chinese Remainder Theorem, properties of prime factorisation) to establish a deeper result. See our Canadian Mathematical Olympiad guide.

AMC 10/12:The AMC 10 and AMC 12 include modular arithmetic problems where knowing Fermat’s Little Theorem — or its consequence that $a^{p-1} \equiv 1$ ap−1≡1 — allows rapid identification of the remainder without computation.

For the full competition landscape, see our math competitions in Canada guide.

Knowing Fermat’s Little Theorem is only one part of Euclid preparation. Students must recognise when to apply it, reduce large exponents accurately and combine it with other number-theory techniques. A free assessment identifies the skills they have mastered and what to develop next.

Assess their competition math skills →

Practice Problems

Set A — Direct application

Find each remainder:

$2^{50} \pmod{7}$ 250(mod7)
$3^{100} \pmod{11}$ 3100(mod11)
$4^{30} \pmod{13}$ 430(mod13)
$5^{999} \pmod{7}$ 5999(mod7)
$6^{1000} \pmod{7}$ 61000(mod7)
$10^{100} \pmod{11}$ 10100(mod11)

Set B — Mixed modular arithmetic

What is the units digit of $7^{100}$ 7100? (Work modulo 5 and modulo 2.)
Show that $5^{11} – 5$ 511−5 is divisible by 11.
If $p$ p is prime and $p \nmid a$ p∤a, show that $a^{2p-2} \equiv 1 \pmod{p}$ a2p−2≡1(modp).
Find the remainder when $2^{2024} + 3^{2024}$ 22024+32024 is divided by 5.

Set C — Competition level

Prove that for any prime $p$ p and integer $a$ a: $p \mid a^p – a$ p∣ap−a.
Show that $n^7 – n$ n7−n is divisible by 42 for every integer $n$ n.
Find all primes $p$ p such that $p \mid 2^p + 1$ p∣2p+1.

Answers:

Set A:

$2^6 \equiv 1 \pmod 7$ 26≡1(mod7); $50 = 8 \times 6 + 2$ 50=8×6+2; $2^{50} \equiv 2^2 = 4 \pmod 7$ 250≡22=4(mod7). Answer: 4
$3^{10} \equiv 1 \pmod{11}$ 310≡1(mod11); $100 = 10 \times 10$ 100=10×10; $3^{100} \equiv 1 \pmod{11}$ 3100≡1(mod11). Answer: 1
$4^{12} \equiv 1 \pmod{13}$ 412≡1(mod13); $30 = 2 \times 12 + 6$ 30=2×12+6; $4^{30} \equiv 4^6 = (4^2)^3 = 16^3 \equiv 3^3 = 27 \equiv 1 \pmod{13}$ 430≡46=(42)3=163≡33=27≡1(mod13). Answer: 1
$5^6 \equiv 1 \pmod 7$ 56≡1(mod7); $999 = 166 \times 6 + 3$ 999=166×6+3; $5^{999} \equiv 5^3 = 125 = 17 \times 7 + 6 \equiv 6 \pmod 7$ 5999≡53=125=17×7+6≡6(mod7). Answer: 6
$6 \equiv -1 \pmod 7$ 6≡−1(mod7); $6^{1000} \equiv (-1)^{1000} = 1 \pmod 7$ 61000≡(−1)1000=1(mod7). Answer: 1
$10 \equiv -1 \pmod{11}$ 10≡−1(mod11); $10^{100} \equiv (-1)^{100} = 1 \pmod{11}$ 10100≡(−1)100=1(mod11). Answer: 1

Set B: 7. Units digit of $7^{100}$ 7100: $7^4 \equiv 1 \pmod{10}$ 74≡1(mod10) (pattern: 7,9,3,1,7,…); $100 = 25 \times 4$ 100=25×4; units digit = 1. (Or: $7^4 \equiv 2 \pmod 5$ 74≡2(mod5) — actually $7^4 = 2401 \equiv 1 \pmod 5$ 74=2401≡1(mod5), and $7^{100} \equiv 1 \pmod 2$ 7100≡1(mod2), so $7^{100} \equiv 1 \pmod{10}$ 7100≡1(mod10).) 8. $p = 11$ p=11, $a = 5$ a=5: by Fermat’s Little Theorem $5^{11} \equiv 5 \pmod{11}$ 511≡5(mod11), so $11 \mid 5^{11} – 5$ 11∣511−5. ✓ 9. $a^{2p-2} = (a^{p-1})^2 \equiv 1^2 = 1 \pmod p$ a2p−2=(ap−1)2≡12=1(modp) by Fermat’s Little Theorem. ✓ 10. $2^4 \equiv 1 \pmod 5$ 24≡1(mod5) (period 4); $2024 = 506 \times 4$ 2024=506×4; $2^{2024} \equiv 1 \pmod 5$ 22024≡1(mod5). $3^4 \equiv 1 \pmod 5$ 34≡1(mod5) (period 4); $3^{2024} \equiv 1 \pmod 5$ 32024≡1(mod5). Sum $\equiv 2 \pmod 5$ ≡2(mod5). Answer: 2

Set C: 11. By Fermat’s Little Theorem: $a^p \equiv a \pmod p$ ap≡a(modp) for all integers $a$ a (the general form). Therefore $p \mid a^p – a$ p∣ap−a. ✓ (For $p \mid a$ p∣a: $a \equiv 0 \pmod p$ a≡0(modp), so $a^p \equiv 0 \equiv a \pmod p$ ap≡0≡a(modp).) 12. $n^7 – n = n(n^6 – 1) = n(n^2-1)(n^4+n^2+1)$ n7−n=n(n6−1)=n(n2−1)(n4+n2+1). By Fermat: $n^7 \equiv n \pmod 7$ n7≡n(mod7) (so $7 \mid n^7 – n$ 7∣n7−n); $n^3 \equiv n \pmod 3$ n3≡n(mod3) (so $3 \mid n^3 – n \mid n^7 – n$ 3∣n3−n∣n7−n); $n^2 \equiv n \pmod 2$ n2≡n(mod2) (so $2 \mid n^2 – n \mid n^7 – n$ 2∣n2−n∣n7−n). Since $\gcd(2,3,7) = 1$ gcd(2,3,7)=1 pairwise, $42 \mid n^7 – n$ 42∣n7−n. ✓ 13. By Fermat: $2^p \equiv 2 \pmod p$ 2p≡2(modp), so $p \mid 2^p + 1 \Rightarrow p \mid 2 + 1 = 3$ p∣2p+1⇒p∣2+1=3. So $p = 3$ p=3. Check: $2^3 + 1 = 9 = 3 \times 3$ 23+1=9=3×3. ✓ Answer: p=3p = 3 p=3.

Frequently Asked Questions

What does Fermat’s Little Theorem state?For any prime $p$ p and integer $a$ a not divisible by $p$ p: $a^{p-1} \equiv 1 \pmod{p}$ ap−1≡1(modp). Equivalently, $a^p \equiv a \pmod{p}$ ap≡a(modp) for any integer $a$ a and prime $p$ p.

Why is it called “Little”?To distinguish it from Fermat’s Last Theorem ( $a^n + b^n = c^n$ an+bn=cn has no positive integer solutions for $n \geq 3$ n≥3). The “little” theorem is the one about primes and modular arithmetic — more immediately useful in competition mathematics.

How do you use Fermat’s Little Theorem to find large remainders?Write the exponent $n$ n as $n = q(p-1) + r$ n=q(p−1)+r. Then $a^n = (a^{p-1})^q \cdot a^r \equiv 1^q \cdot a^r = a^r \pmod{p}$ an=(ap−1)q⋅ar≡1q⋅ar=ar(modp). Compute $a^r$ ar directly since $r < p-1$ r<p−1.

Does Fermat’s Little Theorem work for non-prime moduli?No — not directly. For non-prime moduli, Euler’s generalisation applies: $a^{\phi(n)} \equiv 1 \pmod{n}$ aϕ(n)≡1(modn) when $\gcd(a,n) = 1$ gcd(a,n)=1, where $\phi(n)$ ϕ(n) is Euler’s totient function.

What are Carmichael numbers?Composite numbers $n$ n that satisfy $a^{n-1} \equiv 1 \pmod{n}$ an−1≡1(modn) for all $\gcd(a,n) = 1$ gcd(a,n)=1 — making them pass the Fermat primality test despite being composite. The smallest is 561. They do not violate Fermat’s Little Theorem (which requires $n$ n to be prime) but do limit the usefulness of the Fermat primality test.

Does Fermat’s Little Theorem appear in the Euclid Contest? Yes. Number theory problems involving large powers modulo a prime appear regularly in the Euclid, and Fermat’s Little Theorem is the standard tool for solving them efficiently.

Fermat’s Little Theorem turns impossible calculations into one-line solutions. Know it cold before you need it.

Advanced number theory becomes manageable when students learn to see the structure behind each problem. In a free online trial lesson, your child can experience how Think Academy develops efficient, competition-level problem-solving strategies.

Book a free online trial lesson →

Fermat’s Little Theorem Explained: Definition, Proof and Applications