Carmichael numbers and Fermat primality

I did some recreational mathematics today, and created this plot, showing the number of values for which a^(n-1) = 1 (mod n), for all composite n in the range [3..10000]:

The formula a^(n-1) mod n appears in Fermat's Little Theorem, which says that for prime values of n, the result will always be 1, no matter what a you choose.  If you get a value other than 1, you know that n is composite.

That's neat because it lets us test whether a given n is composite much more quickly than by trying to factor it.  We call that the Fermat Primality Test.  

However, the converse doesn't always hold: sometimes a^(n-1)=1 (mod n) even if n is composite.  When  that happens for some a and n, we say that a is a false witness for n, since it incorrectly suggests that n might be prime.

And that's what the above graph shows: how many false witnesses there are for each value n up to 10,000.  In particular, I scaled the y axis so that it shows the percentage of relatively prime a values that are false witnesses.

Carmichael Numbers

Most interesting are the vertical lines in the graph that reach all the way to the top.  Those are the falsest of the pseudoprimes (with respect to the Fermat test).  They're called the Carmichael Numbers, and I've always found them fascinating, because the smallest of them is 561!  That's the leftmost line in the graph that reaches all the way to the top.

Just how prime are you?

The other thing I was surprised to find in this graph are what we might call the halfway-prime numbers -- numbers for which half of the witnesses will suggest primality with the Fermat test.  And there are one-third-prime numbers, and so on.

Merry Christmas!

All that graphing got me wondering how often a^(n-1) produces numbers other than 1.  So I created this image, which shows increasing values of n as you work downward, and shows how often we get a remainder r.  r is shown on the X axis, while the number of times it came up is shown as a color:

 0=black, 1=dark gray, 2=light gray, 3=blue, 4=orange, 5=red, 6 or more = white

The other trick is that in number theory, we sometimes talk about negative remainders.  If you're working (mod 5), you might get remainders of 0,1,2,3,4, but since the next remainder after 4 is 0 again, sometimes it's easier to think of a remainder of 4 as -1.  So instead of 0,1,2,3,4, we call them 0,1,2,-2,-1, and that's what I've done here. 

Consider the topmost orange pixel in the above image.  It's the 5th pixel from the top, so that whole row represents n=5.  The orange pixel (and all the ones below it) are the "remainder=1" column.  The column to the left of it is the "remainder=0" column, and the one to the right is "remainder=2".  Since 5 is prime, we expect a^4 to be 1 (mod 5) for all 4 possible values of a: 1,2,3 and 4.  And indeed, orange is the color for 4.

Two pixels down, you'll see a white pixel telling us that 7 is prime, since a^6=1 (mod 7) for a=1,2,3,4,5,6.  In the above image, you can keep counting down from the orange pixel at n=5 and see all the primes as white pixels, with 31 at the very bottom.

Give me one of everything

One surprise to me was row 6 (just below the topmost orange pixel).  It has a solid dark gray line extending all the way across.  That means that the five values of a: 1,2,3,4,5 in the equation a^5 (mod 6) produced... the values 1,2,3,4,5!  (Try it: 2^5=32, mod 6=2.  3^5=243, mod 6=3.)

And you can see that lots of other numbers have this behavior: 10, 14, (but not 18!), 22, 26, 30 and so on.

I need a bigger tree

Here's how the image looks if we keep going all the way to 100:

And if you really have a tall living room, you can see the numbers up to 1000, as well as the python source code I used to generate the images.