Suppose a number *n* written in binary has two 1s and all the rest of its bits are zeros. If *n* is prime, then the 1s must be the first and last bits of *n*. The first bit is 1 because the first bit of every positive integer is 1. The last bit is 1 because if the second 1 appeared anywhere else then *n* would be divisible by 2.

Here are the first four examples:

11_{two} = 3_{ten}

101_{two} = 5_{ten}

10001_{two} = 17_{ten}

100000001_{two} = 257_{ten}

Let’s count how many 0 bits each number contains. We get 0, 1, 3, and 7 if we count in base 10, or 0, 1, 11, and 111 if we count in binary. It seems that the number of 0 bits is either zero or a number whose binary representation is all 1s. In fact this turns out to be a theorem:

Suppose a number *n* is written in binary as a 1, followed by *m* 0’s, and finally a 1. Then ifÂ *n* is prime, then either *m* = 0 or the binary representation of *m* consists entirely of 1’s.

To prove this theorem, let’s move away from talking about bits and move toward more standard math terminology.

Our description of *n* in terms of bits is another way of saying

*n* = 2^{k} + 1.

And our description of *m* is another way of saying

*m* = 2^{j} – 1.

And a 1 followed by *m* 0’s and then a 1 is a number of the form

2^{m+1} + 1.

So the theorem above is saying that if 2^{k} + 1 is a prime number, then *k* is a power of 2.

Here’s a proof. Suppose *k* is not a power of 2. Then *k* has an odd factor, i.e. *k* = *ab* where *b* > 1 is an odd number. In that case we can factor 2^{k} + 1 as follows:

We’ve shown above that 2^{k} + 1 is prime when *k* = 2^{j} and *j* = 0, 1, 2, and 3.

What about *j* = 4? Yes, 2^{16} + 1 = 65537 is prime.

We’re on a roll. What about *j* = 5? Is 2^{32} + 1 prime? No, it’s not.

What about larger values of *j*? Do any of them produce primes? Nobody knows.

This post has secretly been about Fermat primes. The *n*th Fermat number is given by

Fermat observed that *F*_{n} was prime for *n* = 0, 1, 2, 3, and 4. He conjectured that *F*_{n} is prime for all *n*, but Euler factored *F*_{5}, disproving Fermat’s conjecture.

Why did this post delay using standard terminology? The first reason was to unpack the math. The direct discussion can go by so quickly that it’s hard to appreciate what it is going on. The second reason was to illustrate how much easier things can become when we switch from discussing bit patterns to using math notation. Sometimes things go the other way, with bits being easier to understand than mathematical equations.

I enjoy the fact that Fermat could have disproven that F_5 was prime using his own Little Theorem, which states 3^{2^32}} \equiv 1 \pmod {2^32+1} when 2^32+1 is prime. Since 3^{2^32}} \equiv 3029026160, he could’ve done this with 32 multiplications. (Concrete Mathematics talks about this on pg 131)