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:
11two = 3ten
101two = 5ten
10001two = 17ten
100000001two = 257ten
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 = 2k + 1.
And our description of m is another way of saying
m = 2j – 1.
And a 1 followed by m 0’s and then a 1 is a number of the form
2m+1 + 1.
So the theorem above is saying that if 2k + 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 2k + 1 as follows:
We’ve shown above that 2k + 1 is prime when k = 2j and j = 0, 1, 2, and 3.
What about j = 4? Yes, 216 + 1 = 65537 is prime.
We’re on a roll. What about j = 5? Is 232 + 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 nth Fermat number is given by
Fermat observed that Fn was prime for n = 0, 1, 2, 3, and 4. He conjectured that Fn is prime for all n, but Euler factored F5, 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.