When Numbers Deceive: Exploring Fermat’s Little Theorem, Carmichael Numbers, and the Miller Test

May 10, 2025

Have you ever been fooled by something that looked correct but wasn’t? I think we all have. But what if I told you that even numbers—those supposedly objective, immutable entities—can be deceptive? Let’s take a fascinating journey through some remarkable number theory concepts that reveal how even mathematics can present us with sophisticated impostors.

Fermat’s Little Theorem: The Foundation

Let’s begin with Fermat’s Little Theorem—not to be confused with his more famous Last Theorem. But what exactly does this theorem tell us? And why is it so important for cryptography and primality testing?

Pierre de Fermat, that brilliant 17th-century mathematician who loved writing notes in margins, gave us this gem: If \(p\) is a prime number and \(a\) is any integer not divisible by \(p\), then:

Alternatively, we can express this as:

What does this mean in plain language? It means that when we raise any number \(a\) to the power of \(p-1\) and divide by \(p\), we’ll always get a remainder of 1. That’s remarkable, isn’t it?

Let’s see a simple example. Take \(p = 5\) (a prime) and \(a = 2\):

But here’s where things get interesting—and potentially deceptive. Can we use this theorem to determine whether a number is prime? Yes, of course! And no, of course not! (You see how this works?)

If a number \(n\) fails this test for some value of \(a\) (meaning \(a^{n-1} \not\equiv 1 \pmod{n}\)), then \(n\) is definitely not prime. But—and this is a big “but”—if \(n\) passes the test, it’s not necessarily prime. It could be what we call a “pseudoprime.”

The Imposters: Carmichael Numbers

Now, let’s meet the most deceptive numbers in the prime number world: Carmichael numbers. These are the sophisticated con artists of number theory, the numbers that can fool Fermat’s primality test for every value of \(a\) that’s coprime to them, despite not being prime themselves.

The smallest Carmichael number is 561. Let’s break it down:

Let’s verify this with a specific example. Take \(a = 2\):

How is this possible? Well, Carmichael numbers have a special property: they’re square-free (not divisible by any perfect square) and for each prime factor \(p\) of a Carmichael number \(n\), the value \(p-1\) divides \(n-1\). This specific structure allows them to satisfy Fermat’s condition despite being composite.

For 561, we can check:

But why should we care about these mathematical imposters? Because they teach us something crucial about testing methods and the nature of certainty. They remind us that passing a single test doesn’t always guarantee truth—a principle that extends far beyond mathematics.

And here’s a question worth pondering: how common are these deceptive numbers? Not very, but more than you might expect. The first few Carmichael numbers are:

Interestingly, \(1729\) is also the famous “Ramanujan number” (the smallest number expressible as the sum of two cubes in two different ways):

Is this just coincidence, or is there something deeper connecting these mathematical curiosities? I’ll leave that thread for another day.

Getting Smarter: The Miller-Rabin Test

So how do we outsmart these numerical con artists? This is where the Miller-Rabin primality test enters our story.

Let’s break down the Miller test (which forms the deterministic part of the Miller-Rabin algorithm). The key insight is to leverage another property of prime numbers: if \(p\) is an odd prime, then \(p-1\) is even, so we can write it as \(p-1 = 2^s \times d\) where \(d\) is odd.

Now, for any \(a\) coprime to \(p\), either:

Let’s see how this works for a prime number. Take \(p = 13\):

But what makes this test so much stronger than Fermat’s? Think of it this way: Fermat’s test only checks the final value (\(a^{n-1} \equiv 1 \pmod{n}\)), while the Miller test examines the “square roots” along the way. It’s like checking not just the destination but the journey itself.

And here’s the remarkable part—all Carmichael numbers will fail the Miller test for at least some values of \(a\). In fact, it can be proven that if \(n\) is composite, then at least 75% of the possible bases \(a\) will serve as witnesses to its compositeness in the Miller-Rabin test.

For example, the Carmichael number \(561\) will fail the Miller test for \(a = 2\):

From Theory to Practice

So what does this mean for practical primality testing? Let’s think about this in terms of a real-world analogy.

Imagine you’re a security guard at an exclusive event, checking IDs. Fermat’s test is like looking only at the photo on the ID—easy to fake. The Miller-Rabin test is like examining the holographic elements, the microprinting, and the texture of the card as well—much harder to counterfeit successfully.

In cryptography—where prime numbers are the building blocks of secure communication—this matters tremendously. RSA encryption, for example, relies on the product of two large primes. If we accidentally use a Carmichael number instead of a prime, the security of the entire system could be compromised.

The Miller-Rabin algorithm combines the deterministic Miller test with random selection of bases, making it a probabilistic algorithm. The probability of error can be expressed as:

The Philosophical Implications

But I think there’s something deeper here than just mathematical techniques. Don’t these deceptive numbers teach us something about truth and verification in general?

Consider how this parallels other domains:

• In science, a single experiment supporting a hypothesis isn’t enough—we need multiple, different tests.
• In journalism, a single source isn’t sufficient—verification requires multiple, independent confirmations.
• In critical thinking, a claim that survives one form of scrutiny might still fail under another.

The Carmichael numbers remind us that even in mathematics—perhaps the most objective realm of human knowledge—appearances can deceive. Passing a test doesn’t guarantee truth; it merely eliminates one possibility of falsehood.

And isn’t that a humbling thought? Even in the crystal-clear world of numbers, certainty requires rigor, multiple perspectives, and clever thinking. If that’s true for mathematics, how much more so for the messy, complex questions of human life?

Bringing It All Together

So what have we learned on this journey through number theory?

We’ve seen how Fermat’s Little Theorem provides a powerful but imperfect test for primality:

We’ve met the Carmichael numbers—those sophisticated numerical con artists that can fool Fermat’s test despite being composite:

And we’ve explored how the Miller-Rabin test outsmarts these imposters by examining the structure of \(n-1 = 2^s \times d\) and checking:

But perhaps the most important lesson is this: even in mathematics, truth often requires multiple approaches and perspectives. A single test, a single viewpoint, a single method is rarely enough.

And that, I think, is a principle worth carrying beyond the realm of number theory into our broader intellectual lives.

What mathematical concepts do you find most philosophically provocative? And how have you applied mathematical thinking to other areas of life? I’d love to hear your thoughts in the comments.