Sherlock Holmes, The Library Bar and Carmichael numbers

Back in grad school, I used to frequent a bar called “The Library.” They had books, food, and drinks, and the music was always great. There was nothing I enjoyed more than showing up there after a long day at work, finding a spot under the bright lights, and reading Sherlock Holmes. The walls were lined with actual bookshelves, but I usually stuck to the hard wooden chairs with my own worn paperbacks.

If you would have told me back then that I would eventually be seriously attempting to learn math that wasn't essential for my work, I would’ve laughed in your face. My way of thinking felt completely incompatible with the rigid world of mathematics. I saw myself as a person of prose and puzzles, not proofs and polynomials.

My perspective has changed over the last five years. I have slowly begun to realize that the thrill of a Holmesian deduction is not so different from the thrill of a mathematical discovery. Today, as I sat down with Silverman’s chapter on Carmichael numbers, those old evenings at the bar came rushing back.

In "The Adventure of Silver Blaze," Holmes famously points to the "curious incident of the dog in the night-time." The dog did nothing, which was the clue that the intruder was someone the dog knew.

In the world of Carmichael numbers, we see a similar logic. We expect a composite number to "bark": to fail the Fermat primality test: when we check it against various bases. But a Carmichael number like 561 stays silent. It passes the test for every base a that is coprime to it, just as if it were a prime number.

To understand how a number like 561 (which is 3 \times 11 \times 17) pulls off this stunt, we have to look at Korselt's Criterion. This is the "forensic evidence" that reveals why the number behaves the way it does.

Korselt's Criterion states that a positive composite integer n is a Carmichael number if and only if:

• n is square-free (it has no repeated prime factors).
• For every prime factor p of n, the value (p - 1) divides (n - 1).

When I look at the math for 561, I see the "clues" clicking into place just like a Holmesian deduction:

* For the prime 3: (3-1) = 2, and 2 divides 560.

* For the prime 11: (11-1) = 10, and 10 divides 560.

* For the prime 17: (17-1) = 16, and 16 divides 560 (16 \times 35 = 560).

The Carmichael number seems impossible at first: how can a composite number act so much like a prime? But once you see the relationship between (p-1) and (n-1), the disguise falls away. The "criminal" is caught, and the logic is undeniable.