The best examples of Fermat's Little Theorem: practical examples in modern math

Let’s recall the statement informally, then immediately push into concrete use.

Fermat’s Little Theorem (FLT) says:

If \(p\) is prime and \(a\) is an integer not divisible by \(p\), then
[
a^{p-1} \equiv 1 \pmod p.
]

Equivalently, many people prefer the version
[
a^{p} \equiv a \pmod p.
]

Instead of staring at symbols, let’s walk through a few examples of Fermat’s Little Theorem: practical examples with actual numbers.

Take \(p = 7\) (which is prime) and \(a = 3\). Then FLT predicts:
[
3^{6} \equiv 1 \pmod 7.
]
Compute step by step using modular arithmetic to keep numbers small:

• \(3^2 = 9 \equiv 2 \pmod 7\)
• \(3^4 = (3^2)^2 \equiv 2^2 = 4 \pmod 7\)
• \(3^6 = 3^4 \cdot 3^2 \equiv 4 \cdot 2 = 8 \equiv 1 \pmod 7\).

The theorem delivers exactly what we see: \(3^6\) leaves remainder 1 when divided by 7.

Try another: \(p = 11\), \(a = 2\).
FLT says \(2^{10} \equiv 1 \pmod{11}\).

Use repeated squaring:

• \(2^2 = 4\)
• \(2^4 = 16 \equiv 5 \pmod{11}\)
• \(2^8 = 5^2 = 25 \equiv 3 \pmod{11}\)
• \(2^{10} = 2^8 \cdot 2^2 \equiv 3 \cdot 4 = 12 \equiv 1 \pmod{11}\).

Again, the pattern holds. These tiny calculations are the first examples of Fermat’s Little Theorem: practical examples that you can verify by hand.

Everyday-style arithmetic tricks: mental math examples include shortcuts

One surprisingly friendly example of Fermat’s Little Theorem in action is a mental math shortcut: computing huge powers modulo a prime without a calculator.

Say someone asks for the remainder of \(7^{100}\) when divided by 13. Brute force is impossible by hand, but FLT says for prime \(13\):
[
7^{12} \equiv 1 \pmod{13}.
]

Rewrite \(100\) as \(12 \cdot 8 + 4\):
[
7^{100} = 7^{12 \cdot 8 + 4} = (7^{12})^8 \cdot 7^4.
]
By FLT, \(7^{12} \equiv 1\), so
[
7^{100} \equiv 1^8 \cdot 7^4 \equiv 7^4 \pmod{13}.
]
Now keep it small:

• \(7^2 = 49 \equiv 10 \pmod{13}\)
• \(7^4 = 10^2 = 100 \equiv 9 \pmod{13}.\)

So \(7^{100} \equiv 9 \pmod{13}\).

In contest problems, coding interviews, and math team practice, these examples of Fermat’s Little Theorem: practical examples show up constantly: turn a monstrous exponent into something manageable by chopping it modulo \(p-1\).

Another everyday-style use: suppose you want the last digit of \(3^{2025}\). That’s \(3^{2025} \bmod 10\). FLT does not directly apply to 10 (not prime), but it applies to each prime factor, 2 and 5.

• Mod 2: any odd power of 3 is \(1 \pmod 2\).
• Mod 5: FLT gives \(3^4 \equiv 1 \pmod 5\), and \(2025 \equiv 1 \pmod 4\), so \(3^{2025} \equiv 3 \pmod 5\).

Now use the Chinese Remainder Theorem (a standard tool in number theory): the number is

• \(\equiv 1 \pmod 2\)
• \(\equiv 3 \pmod 5\).

The only digit from 0–9 that satisfies both is 3, so the last digit of \(3^{2025}\) is 3. Behind the scenes, this is another example of Fermat’s Little Theorem: practical examples mixing with other tools.

Modular inverses: one of the best examples for problem solving

If you work with modular equations, you quickly run into the question: how do I divide by a number modulo a prime? In modular arithmetic, division means multiplying by an inverse.

For prime \(p\) and integer \(a\) with \(p \nmid a\), FLT says
[
a^{p-1} \equiv 1 \pmod p.
]
Rearrange:
[
a^{p-2} \equiv a^{-1} \pmod p.
]

So \(a^{p-2}\) is the modular inverse of \(a\) modulo \(p\). This is one of the best examples of Fermat’s Little Theorem: practical examples that directly power algorithms.

Take \(a = 7, p = 19\). We want the inverse of 7 modulo 19, i.e., a number \(x\) such that
[
7x \equiv 1 \pmod{19}.
]
FLT tells us
[
7^{17} \equiv 1 \pmod{19}, \quad 7^{17} = 7 \cdot 7^{16}.
]
So
[
7^{16} \equiv 7^{-1} \pmod{19}.
]

We can compute \(7^{16} \bmod 19\) by fast exponentiation:

• \(7^2 = 49 \equiv 11 \pmod{19}\)
• \(7^4 = 11^2 = 121 \equiv 7 \pmod{19}\)
• \(7^8 = 7^2 \cdot 7^6\) is a bit messy, so instead:
  • \(7^4 \equiv 7\)
  • \(7^8 \equiv 7^2 = 49 \equiv 11 \pmod{19}\)
  • \(7^{16} \equiv 11^2 = 121 \equiv 7 \pmod{19}.\)

So \(7^{-1} \equiv 7 \pmod{19}\), and indeed \(7 \cdot 7 = 49 \equiv 49 - 38 = 11 \pmod{19}\). That means we made a slip in the shortcut chain; let’s correct carefully using a cleaner exponent path, which is exactly how you’d debug this in code.

Better approach:

• \(7^2 \equiv 11 \pmod{19}\)
• \(7^4 \equiv 11^2 = 121 \equiv 7 \pmod{19}\)
• \(7^8 \equiv 7^4 \cdot 7^4 \equiv 7 \cdot 7 = 49 \equiv 11 \pmod{19}\)
• \(7^{16} \equiv 7^8 \cdot 7^8 \equiv 11 \cdot 11 = 121 \equiv 7 \pmod{19}.\)

So FLT is telling us \(7^{-1} \equiv 7 \pmod{19}\), but direct check:
\(7 \cdot 7 = 49 \equiv 11 \pmod{19}\), not 1. The problem is that we identified \(7^{16}\) with the inverse, but for \(p = 19\), we should use exponent \(p-2 = 17\):
[
7^{17} \equiv 7^{-1} \pmod{19}]
not \(7^{16}\). Let’s compute \(7^{17} = 7^{16} \cdot 7 \equiv 7 \cdot 7 = 49 \equiv 11 \pmod{19}.\)

So the correct inverse is \(7^{-1} \equiv 11 \pmod{19}\), and
[
7 \cdot 11 = 77 \equiv 1 \pmod{19}.
]

That small correction is exactly the kind of detail that matters in code and contests. It also shows why these examples of Fermat’s Little Theorem: practical examples are worth doing by hand at least once.

This inverse trick is used constantly in:

• Competitive programming (modular division in combinatorics problems)
• Implementing binomial coefficients \(\binom{n}{k} \bmod p\)
• Many cryptographic routines where you need modular inversion quickly

Fast exponentiation and primality testing: real examples from computing

Now let’s jump from hand calculations to real examples in computing where Fermat’s Little Theorem quietly runs the show.

Fermat primality test: a probabilistic filter

A direct example of FLT in algorithms is the Fermat primality test. The idea is simple:

If \(n\) is prime, then for any \(a\) with \(1 \le a < n\) and \(\gcd(a, n) = 1\),
[
a^{n-1} \equiv 1 \pmod n.
]

So if you pick an \(a\) and find that \(a^{n-1} \not\equiv 1 \pmod n\), then \(n\) is definitely composite.

This doesn’t give a guaranteed proof of primality, because there are composite numbers (Carmichael numbers) that pass the test for many bases \(a\). But it is fast and still used as a preliminary filter in some systems before running stronger tests like Miller–Rabin. For a modern discussion of primality tests and their role in cryptography, you can check out materials from places like MIT OpenCourseWare or Stanford’s number theory notes, often hosted under .edu domains.

In 2024, high-level languages and libraries still rely on variants of these ideas to generate large primes for encryption keys. Python’s sympy library, for example, uses probabilistic primality checks that are conceptually related to these examples of Fermat’s Little Theorem: practical examples.

Fast modular exponentiation in real software

Any time you see code that computes \(a^b \bmod m\) for large \(b\), you are usually seeing two ingredients:

• Binary exponentiation (a fast algorithm), and
• Number-theoretic shortcuts like FLT to reduce exponents modulo \(\varphi(m)\) when \(m\) is prime or has known factorization.

In public-key cryptography (RSA, Diffie–Hellman variants, and related schemes), this pattern is everywhere. While the detailed security analysis goes beyond FLT, the basic arithmetic operations still lean on these number-theoretic relationships. For a solid, math-first overview of public-key cryptography, the National Institute of Standards and Technology (NIST) publishes open resources at nist.gov.

Cryptography: real examples using Fermat’s Little Theorem

Let’s look at more concrete cryptography-flavored examples, because these are often the most convincing real examples.

Toy RSA-style example (for intuition)

RSA itself is based on Euler’s theorem more than directly on FLT, but when the modulus is prime or when you look at one prime factor at a time, FLT is the underlying pattern.

Imagine a simplified setting:

• Choose a prime \(p = 23\).
• Choose a small exponent \(e = 5\) with \(\gcd(e, p-1) = 1\). Here, \(p-1 = 22\), and 5 is coprime to 22.

We want a decryption exponent \(d\) such that
[
e d \equiv 1 \pmod{p-1}.
]

Solve \(5d \equiv 1 \pmod{22}\). A quick inspection shows \(d = 9\) works because \(5 \cdot 9 = 45 \equiv 1 \pmod{22}\).

Now encryption is c ≡ m^e (mod p) and decryption is m ≡ c^d (mod p). Why does this recover the original message \(m\) for all \(m\) not divisible by 23?

Because
[
m^{ed} = m^{1 + 22k} = m \cdot (m^{22})^k \equiv m \cdot 1^k \equiv m \pmod{23}
]
by Fermat’s Little Theorem, since \(m^{22} \equiv 1 \pmod{23}\).

This is a stripped-down, one-prime version of how RSA-style systems rely on the same structure. It’s not secure in practice (real RSA uses a product of large primes), but as an example of Fermat’s Little Theorem at work, it’s clean and transparent.

For a more formal treatment of RSA and its mathematics, see open course notes from universities such as Harvard University or detailed cryptography texts hosted on .edu domains.

Fermat little theorem in modern protocols

Modern protocols like TLS, which secure HTTPS connections, rely on modular exponentiation under the hood. While the exact constructions use more advanced mathematics (elliptic curves, finite fields of large order, etc.), Fermat’s Little Theorem still provides intuition for why exponentiation in a finite field cycles and how inverses exist for nonzero elements.

The U.S. National Security Agency and NIST both publish guidance on approved cryptographic standards; see NIST’s cryptographic standards pages at nist.gov for current recommendations as of 2024–2025. The math that underlies these standards includes many real examples of Fermat’s Little Theorem: practical examples generalized to richer algebraic structures.

Combinatorics and programming contests: more applied examples

In programming contests and competitive math, you see examples include:

• Computing \(\binom{n}{k} \bmod p\) where \(p\) is prime
• Using Fermat’s Little Theorem to precompute factorials and inverse factorials
• Speeding up dynamic programming with modular inverses

Take binomial coefficients modulo a prime \(p\):
[
\binom{n}{k} = \frac{n!}{k!(n-k)!}.
]

Over the integers, that fraction is fine. Modulo \(p\), direct division doesn’t exist, but we can rewrite it as
[
\binom{n}{k} \equiv n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \pmod p.
]

Here, \((k!)^{-1}\) and \(((n-k)!)^{-1}\) are modular inverses. If \(p\) is prime and none of these factorials is divisible by \(p\) (which is true when \(n < p\)), then FLT gives
[
(k!)^{-1} \equiv (k!)^{p-2} \pmod p.
]

Contest coders precompute:

• An array of factorials fact[i] ≡ i! (mod p)
• An array of inverse factorials invfact[i] ≡ (i!)^{-1} (mod p) using FLT

Then each binomial coefficient can be answered in constant time using just a few multiplications modulo \(p\). This is one of the best examples of Fermat’s Little Theorem: practical examples that directly translate to performance.

If you browse editorial solutions for problems on major competitive programming platforms in 2024–2025, you’ll see this pattern repeatedly. FLT is baked into the standard “mod binomial coefficient” template.

Spotting when Fermat’s Little Theorem fails: a diagnostic example

It’s also instructive to see an example of when the theorem does not apply, because that’s just as useful in practice.

Take \(n = 15\), which is composite, and \(a = 2\). If 15 were prime, FLT would suggest
[
2^{14} \equiv 1 \pmod{15}.
]

Compute stepwise:

• \(2^2 = 4\)
• \(2^4 = 16 \equiv 1 \pmod{15}\)
• \(2^8 = 1^2 = 1 \pmod{15}\)
• \(2^{14} = 2^8 \cdot 2^4 \cdot 2^2 \equiv 1 \cdot 1 \cdot 4 = 4 \pmod{15}.\)

We get 4, not 1, so 15 immediately fails this Fermat-style test for base 2 and is confirmed composite. This is exactly how the Fermat primality test works as a fast filter: it looks for violations of the FLT pattern.

FAQ: common questions about examples of Fermat’s Little Theorem

What are some quick classroom-style examples of Fermat’s Little Theorem?

Classic classroom examples include verifying \(2^{10} \equiv 1 \pmod{11}\), checking \(3^{6} \equiv 1 \pmod{7}\), and using \(a^{p-1} \equiv 1 \pmod p\) to show that \(a^{p} \equiv a \pmod p\). These examples of Fermat’s Little Theorem: practical examples help students see the pattern before moving to proofs.

Can you give an example of Fermat’s Little Theorem in cryptography?

A standard example of FLT in cryptography is computing modular inverses for key-related operations: for a prime modulus \(p\), the inverse of \(a\) is \(a^{p-2} \bmod p\). This is used in many public-key schemes and in supporting algorithms like modular inversion in finite fields.

Do real examples of Fermat’s Little Theorem appear in modern software?

Yes. Large-integer libraries, primality testing routines, and competitive programming templates all use patterns directly linked to Fermat’s Little Theorem. In 2024–2025, fast modular exponentiation using ideas from FLT is still a workhorse inside cryptographic libraries and big-number toolkits.

How is Fermat’s Little Theorem different from Euler’s theorem?

Fermat’s Little Theorem is the prime-modulus special case of Euler’s theorem. Euler’s theorem says \(a^{\varphi(n)} \equiv 1 \pmod n\) when \(\gcd(a, n) = 1\), where \(\varphi(n)\) is Euler’s totient function. When \(n = p\) is prime, \(\varphi(p) = p-1\), so Euler’s theorem reduces to FLT. Many real examples of Fermat’s Little Theorem: practical examples are actually special cases of Euler’s more general statement.

Where can I read more about the theory behind these examples?

For a deeper mathematical treatment, university lecture notes and open textbooks from .edu domains are a good starting point. For instance, introductory number theory courses from MIT or Harvard often include sections on Fermat’s Little Theorem, Euler’s theorem, and their applications to cryptography and algorithms.