There are tricks for determining whether a number is divisible by various primes, but many of these tricks have to be applied one at a time. You can make a procedure for testing divisibility by any prime p that is easier than having to carry out long division, but these rules are of little use if every one of them is different.

Say I make a rule for testing whether a number is divisible by 59. That’s great, if you routinely need to test divisibility by 59. Maybe you work for a company that, for some bizarre reason, ships widgets in boxes of 59 and you frequently have to test whether numbers are multiples of 59.

When you want to factor numbers, you’d like to test divisibility by a set of primes at once, using fewer separate algorithms, and taking advantage of work you’ve already done.

John Conway came up with his 150 Method to test for divisibility by a sequence of small primes. This article explains how Conway’s 150 method and a couple variations work. The core idea behind Conway’s 150 Method, his 2000 Method, and analogous methods developed by others is this:

1. Find a range of integers, near a round number, that contains a lot of distinct prime factors.
2. Reduce your number modulo the round number, then test for divisibility sequentially, reusing work.

Conway’s 150 Method starts by taking the quotient and remainder by 150. And you’ll never guess what his 2000 Method does. :)

This post will focus on the pattern behind Conway’s method, and similar methods. For examples and practical tips on carrying out the methods, see the paper linked above and a paper I’ll link to below.

The 150 Method

Conway exploited the fact that the numbers 152 through 156 are divisible by a lot of primes: 2, 3, 5, 7, 11, 13, 17, 19, and 31.

He starts his method with 150 rather than 152 because 150 is a round number and easier to work with. We start by taking the quotient and remainder by 150.

Say n = 150q + r. Then n – 152q = r – 2q. If n has three or four digits, q only has one or two digits, and so subtracting q is relatively easy.

Since 19 divides 152, we can test whether n is divisible by 19 by testing whether r – 2q is divisible by 19.

The next step is where sequential testing saves effort. Next we want to subtract off a multiple of 153 to test for divisibility by 17, because 17 divides 153. But we don’t have to start over. We can reuse our work from the previous step.

We want n – 153q = (n – 152q) – q, and we’ve already calculated n – 152q in the previous step, so we only need to subtract q.

The next step is to find n – 154q, and that equals (n – 153q) – q, so again we subtract q from the result of the previous step. We repeat this process, subtracting q each time, and testing for divisibility by a new set of primes each time.

The 2000 method

Conway’s more extensive method exploited the fact that the numbers 1998 through 2021 are divisible by all primes up to 67. So he would start by taking the quotient and remainder by 2000, which is really easy to do.

Say n = 2000q + r. Then we would add (or subtract) q each time.

You could start with r, then test r for divisibility by the factors of 2000, then test r – q for divisibility by the factors of 2001, then test r – 2q for divisibility by the factors of 2002, and so on up to testing r – 21q for divisibility by the factors of 2021. Then you’d need to go back and test r + q for divisibility by the factors of 1999 and test r + 2q for divisibility by the factors of 1998.

In principle that’s how Conways 2000 Method works. In practice, he did something more clever.

Most of the prime factors of the numbers 1998 through 2021 are prime factors of 1998 through 2002, so it makes sense to test this smaller range first hoping for early wins. Also, there’s no need to test divisibility by the factors of 1999 because 1999 is prime.

Conway tested r – kq for k = -2 through 21, but not sequentially. He would try out the values of k in an order most likely to terminate the factoring process early.

The 10,000 method

This paper gives a much more extensive approach to mental factoring than Conway’s 150 method. The authors, Hilarie Orman and Richard Schroeppel, outline a strategy for factoring any six-digit number. Conway’s rule is more modest, intended for three and four digit numbers.

Orman and Schroeppel suggest a sequence of factoring methods, including more advanced techniques to use after you’ve tried testing for divisibility by small primes. One of the techniques in the paper might be called the 10,000 Method by analogy to Conway’s method, though the authors don’t call it that. They call it “check the m‘s” for reasons that make more sense if you read the paper.

The 10,000 Method is much like the 2000 Method. The numbers 10,001 through 10,019 have a lot of prime factors, and the method tests for divisibility by these factors sequentially, taking advantage of previous work at each step, just as Conway’s methods do. The authors do not backtrack the way Conway did; they test numbers in order. However, they do skip over some numbers, like Conway skipped over 1999.

More Conway-related posts

• A sort of opposite of Parkinson’s law
• Never applied for a job
• Mentally calculating the day of the week
• Mental exercise rituals

The previous post took a mathematical look at the National Football League. This post will do the same for Major League Baseball.

Like the NFL, MLB teams are organized into a nice tree structure, though the MLB tree is a little more complicated. There are 32 NFL teams organized into a complete binary tree, with a couple levels collapsed. There are 30 MLB teams, so the tree structure has to be a bit different.

MLB has leagues rather than conferences, but the top-level division is into American and Nation as with the NFL. So the top division is into the American League and the National League.

And as with football, the next level of the hierarchy is divisions. But baseball has three divisions—East, Central, and West—in contrast to four in football.

Each division has five baseball teams, while each football division has four teams.

Here’s the basic tree structure.

Under each division are five teams. Here’s a PDF with the full graph including teams.

Geography

How do the division names correspond to actual geography?

Within each league, the Central teams are to the west of the East teams and to the east of the West teams, with one exception: in the National League, the Pittsburgh Pirates are a Central division team, but they are east of the Atlanta Braves and Miami Marlins in the East division. But essentially the East, Central, and West divisions do correspond to geographic east, center, and west, within a league.

Numbering

We can’t number baseball teams as elegantly as the previous post numbered football teams. We’d need a mixed-base number. The leading digit would be binary, the next digit base 3, and the final digit base 5.

We could number the teams so that you could tell the league and division of the team by looking at the remainders when the number is divided by 2 and 3, and each team is unique mod 5. By the Chinese Remainder Theorem, we can solve the system of congruence equations mod 30 that specify the value of a number mod 2, mod 3, and mod 5.

If we number the teams as follows, then even numbered teams are in the American League and odd numbered teams are in the National League. When the numbers are divided by 3, those with remainder 0 are in an Eastern division, those with remainder 1 are in a Central division, and those with remainder 2 are in a Western division. Teams within the same league and division have unique remainders by 5.

1. Cincinnati Reds
2. Oakland Athletics
3. Philadelphia Phillies
4. Minnesota Twins
5. Arizona Diamondbacks
6. Boston Red Sox
7. Milwaukee Brewers
8. Seattle Mariners
9. Washington Nationals
10. Chicago Whitesocks
11. Colorado Rockies
12. New York Yankees
13. Pittsburgh Pirates
14. Texas Rangers
15. Atlanta Braves
16. Cleveland Guardians
17. Los Angeles Dodgers
18. Tampa Bay Rays
19. St. Louis Cardinals
20. Houston Astros
21. Miami Marlins
22. Detroit Tigers
23. San Diego Padres
24. Toronto Blue Jays
25. Chicago Cubs
26. Los Angeles Angels
27. New York Mets
28. Kansas City Royals
29. San Francisco Giants
30. Baltimore Orioles

Related posts

• A mathematical look at the NFL
• Solving systems of congruences

To test whether a number is divisible by 11, add every other digit together and subtract the rest of the digits. The result is divisible by 11 if and only if the original number is divisible by 11.

For example, start with n = 31425. Add 3, 4, and 5, and subtract 1 and 2. Since 3 + 4 + 5 – 1 – 2 = 9, and 9 is not divisible by 11, neither is 31425.

For another example, take 349041. We have 3 + 9 + 4 = 16, and 4 + 0 + 1 = 5, and 16 – 5 = 11. Since 11 is obviously divisible by 11, so is 349041.

The same trick that works for testing base 10 numbers for divisibility by 11 works for testing base 16 numbers for divisibility by 17. More generally, it works for testing base b numbers for divisibility by b+1.

Let m = b + 1. Then

which implies

Here a_n is the nth digit of a number in base b, numbering the digits from the least significant, counting from 0.

Sometimes a rule for testing divisibility by m will also tell you the remainder when a number is divided by m, but sometimes not. The method presented here will give you the remainder by b + 1, but only if you start adding up digits from the right end. Note in the proof that the digits in even positions (counting from 0) have a positive coefficient and the digits in odd positions have a negative coefficient.

For example, let’s look at 1EDA86_hex in hexadecimal (base 16). If we add 6, A, and E, and subtract 8, D, and 1, we get 8, which is the remainder when 1EDA86_hex is divided by 11_hex (i.e. 17_ten). But if we add 1, D, and 8 and subtract E, A, and 8, we get 9.

You can start from either end of a number if you only want to test divisibility, not to compute a remainder. But if you do want the remainder, you might get the wrong result if you start at the wrong end.

Application: Divisibility by 7, 11, and 13

We can apply the technique above to test for divisibility by 1001 in base 1000. And why would we want to do that? Because 1001 = 7 × 11 × 13. Reducing a large number mod 1001 takes the problem of testing for divisibility mod 7, 11, or 13 down to the problem of testing 3-digit numbers.

Base 1000 is just base 10, thinking of triples of ordinary digits as a single base 1000 digit. If we write a number with thousands separators (i.e. commas in some countries, periods in others) then each segment is a base 1000 “digit.”

Example 1

For example, let’s test whether n = 598,203,918 is divisible by 7, 11, or 13.

The alternating (base 1000) digit sum is

598 – 203 + 918 = 1313 = 13 × 101.

The result is clearly divisible by 13, so n is divisible by 13. But since 101 is not divisible by 7 or 11, neither is n.

Example 2

For another example, let n = 314,159,265,358 and find the remainders when n is divided by 7, 11, and 13. We start by reducing n mod 1001.

314159265358 =  -314 + 159 – 265 + 358 = -62 = 939 mod 1001.

Now 939 = 1 = mod 7, so n = 1 mod 7.

Also, 9 + 9 – 3 = 15 = 4 mod 11, and so n = 4 mod 11.

Finally, 939 = 3 mod 13, so n = 3 mod 13.

 

Can a Pythagorean triangle have one size of length 2023? Yes, one possibility is a triangle with sides (2023, 6936, 7225).

Where did that come from? And can we be more systematic, listing all Pythagorean triangles with a side of length 2023?

Euclid’s formula generates Pythagorean triples by sticking integers m and n into the formula

(m² – n², 2mn, m² + n²).

If one of these three numbers equals 2023, it’s going to have to be the first one. Why? The second number is even, and 2023 is odd, so that one is ruled out.

It’s less obvious but true that the hypotenuse m² + n² cannot be 2023. We could verify this by brute force, trying integer values of m between 1 and √2023, subtracting m² from 2023, and seeing whether the result is a square. But there is a more elegant approach.

There is a theorem that says an integer N is the sum of two squares exactly when every prime that divides N is either congruent to 1 mod 4 or appears an even number of times in the factorization of N. The prime factorization of N is 7 × 17 × 17. The factor 7 appears to an odd power and 7 = 3 mod 4.

Is 2023 a difference of squares? Yes, every odd number is a difference of squares.

To write an number N as a difference of squares, we have to solve

m² – n² = (m + n)(m – n) = N.

If N is odd, we can always set m – n = 1. In the case N = 2023, this means m = 1012 and n = 1011.

The solution above corresponds to factoring 2023 as 2023 × 1. We could also factor 2023 as 289 × 7 or 119 × 17. (The first factor has to be larger than the second for m – n to be positive.) To find more possible value of m and n we solve the equations

m + n = 289
m – n = 7

and

m + n = 119
m – n = 17.

These have solution (148, 141) and (68, 51).

To summarize, we can find three Pythagorean triples with one component equal to 2023 using Euclid’s formula. These are

(2023, 2046264, 2046265)
(2023, 41736, 41785)
(2023, 6936, 7225)

corresponding to (m, n) = (1013, 1012), (148, 141), and (68, 51) respectively. The first two are primitive Pythagorean triples because the three numbers are relative prime in both cases. The last triple is not primitive because each number is divisible by 289.

Euclid’s formula generates all primitive Pythagorean triples, but it doesn’t generate all possible Pythagorean triples. To find all Pythagorean triples we have to consider solutions of the form

(km² – kn², 2kmn, km² + kn²)

for some integer k. If 2023 is k times a difference of squares, k must be a factor of 2023, and so k = 1, 7, 17, 119, 289, or 2023. We’ve already considered the case k = 1.

For k = 7, we express 289 as a difference of squares. The only solutions with positive integers is (m, n) = (145, 144). This yields the Pythagorean triple

(2023, 292320, 292327).

For k = 17, we express 119 as a difference of squares. The solutions are (m, n) = (60, 59) and (12, 5). These yield

(2023, 120360, 120377)

and

(2023, 2040, 2873).

For k = 119, we express 17 as a difference of squares. This can only be done one way, (m, n) = (9, 8). This yields

(2023, 17136, 17255).

For k = 289, we express 7 as a difference of squares. The unique solution (4, 3) yields the triple

(2023, 6936, 7225)

that we had found previously.

For k = 2023, we have to write 1 as a difference of squares. This has no solution if we require both squares to be positive.

So we’re done. We’ve found all Pythagorean triples containing 2023.

Related posts

• Fibonacci meets Pythagoras
• Pythagorean theorem on a sphere
• Dijkstra extends Pythagoras

The previous post illustrated a technique for finding factors of number of the form bⁿ – 1. This post will look at an analogous, though slightly less general, technique for numbers of the form bⁿ + 1.

There is a theorem that says that if m divides n then b^m + 1 divides bⁿ + 1 if n is odd. To see that the exponent must be odd, let b = 10, n = 4, and m = 2: 10,0001 is not divisible by 101.

Last time we looked at 2²⁰²³ – 1, so this time let’s look at J = 2²⁰²³ + 1.

Since 2023 = 7×17×17, we know J is divisible by 2ⁿ + 1 for n = 7, 17, 7×17, and 17×17. Factoring each of these factors tells us that J is divisible by

• 3
• 43691
• 72251
• 79187
• 1077971
• 823679683
• 18360250452977
• 197766803208315851
• 143162553165560959297
• 338858733065598401355195539629373089

(If it seems this post is moving too fast, you might want to go back and read the previous post and then come back.)

Let P be the product of the factors above, and let F = J/P.  Now F is a 493-digit number, so we don’t expect to be able to get much further unless we’re lucky. We can find three factors of F

• 43
• 4382432993
• 1809032819104754041

but then we get stuck. We know there are more factors, but it seems doubtful that I’m going to find any more anytime soon.

***

As in the previous post, we’ll conclude with Python code to verify the claims above.

from sympy import isprime

def verify_factors(N, factors, full=True):
    prod = 1
    for f in factors:
        assert(isprime(f))
        prod *= f
    if full:
        assert(N == prod)
    else:
        assert(N % prod == 0)
        assert(not isprime(N // prod))
    return N // prod

factors = [
    3,
    43691,
    72251,
    79187,
    1077971,
    823679683,
    18360250452977,
    197766803208315851,
    143162553165560959297,
    338858733065598401355195539629373089
]

J = 2**2023 + 1
F = verify_factors(J, factors, False)

factors = [43, 4382432993, 1809032819104754041]
verify_factors(F, factors, False)

print(len(str(F)))

Suppose you want to factor a number of the form bⁿ – 1.

There is a theorem that says that if m divides n then b^m – 1 divides bⁿ – 1.

Let’s use this theorem to try to factor J = 2²⁰²³ – 1, a 609-digit number. Factoring such a large number would be more difficult if it didn’t have a special form that we can exploit.

Our theorem tells us J is divisible by 2⁷ – 1 and 2²⁸⁹ – 1 because 2023 = 7×17×17.

Is J divisible by (2⁷ – 1)(2²⁸⁹ – 1)? In fact it is, but this doesn’t necessarily follow from the theorem above because (b^m – 1) and (b^n/m -1) could share factors, though in this case they do not.

So we have

J = (2⁷ – 1) (2²⁸⁹ – 1) F

for some factor F.  Now 2⁷ – 1 = 127, a prime. What about 2²⁸⁹ – 1?

By the theorem above we know that 2²⁸⁹ – 1 is divisible by 2¹⁷ – 1 = 131071, which turns out to be a prime. We can get a couple more factors of 2²⁸⁹ – 1 by consulting The Cunningham Project, a project that catalogs known factors of bⁿ ± 1 for small values of b. We learn from their site that 2²⁸⁹ – 1 is also divisible by 12761663 and 179058312604392742511009. All together

2²⁸⁹ – 1 = 131071 × 12761663 × 179058312604392742511009 × R

where

R = 3320934994356628805321733520790947608989420068445023

and R turns out to be prime.

So now we have five prime factors of J:

• 127
• 131071
• 12761663
• 179058312604392742511009
• R.

That leaves us with F above, a 520-digit number. It would seem we’ve gotten all the mileage we can out of our factoring trick. But there’s something we haven’t tried: We know that J is divisible by 2¹¹⁹ – 1 because 7 × 17 = 119 is a factor of 2023.

Now

2¹¹⁹ – 1 = 127 × 239 × 20231 × 131071 × 62983048367 × 131105292137

and so these prime factors divide J. However, two of these, 127 and 131071, we’ve already discovered. But we do learn 4 more prime factors. So

F = 239 × 20231 × 62983048367 × 131105292137 × G

where G is a 492-digit number. We can tell by Fermat’s test that G is not prime, but I’m unaware of any clever technique for easily finding any of the factors of G.

***

In general factoring a 492-digit number is hard. There are RSA challenge numbers smaller than this that have not yet been factored, such as RSA-260, a 260-digit number. On the other hand, the RSA numbers are designed to be hard to factor. RSA-260 has two prime factors, presumably both the same order of magnitude. We get a little luckier with G. It has three relatively small factors that I was able to find:

G = 166684901665026193 × 3845059207282831441 × 153641005986537578671 × H

where H is a 436-digit number. I know from Fermat’s test that H is composite but I could not find any factors.

Update: From the comments, 2605053667526976413491923719 is also a factor of G. I’ve updated the code below accordingly. Now the unfactored part H is a 408-digit number.

***

Here’s Python code to verify the claims made above.

from sympy import isprime

def verify_factors(N, factors, full=True):
    prod = 1
    for f in factors:
        assert(isprime(f))
        prod *= f
    assert(N % prod == 0)
    if full:
        assert(N == prod)

R = 3320934994356628805321733520790947608989420068445023
factors = [131071, 12761663, 179058312604392742511009, R]
verify_factors(2**289 - 1, factors)

J = 2**2023 - 1
prod = 127*(2**289 - 1)
F = J // prod
assert(J == prod*F)

factors = [127, 239, 20231, 131071, 62983048367, 131105292137]
verify_factors(2**119 - 1, factors)

prod = 239*20231*62983048367*131105292137
G = F // prod
assert(F == G*prod)

factors = [166684901665026193, 3845059207282831441, 153641005986537578671, 2605053667526976413491923719]
verify_factors(G, factors, False)

prod = 1
for f in factors:
    prod *= f
H = G // prod
assert(G == H*prod)
assert(not isprime(H))

assert(len(str(J)) == 609)
assert(len(str(F)) == 520)
assert(len(str(G)) == 492)
assert(len(str(H)) == 408)

Related post: Primality certificates

Update: See the next post for the case of bⁿ + 1.

I’ve written lately about two general ways to prove that a number is prime: Pratt certificates for moderately-large primes and elliptic curve certificates for very large primes.

If you can say more about the prime you wish to certify, there may be special forms of certificates that are more efficient. In particular, there are efficient tests to determine whether Fermat number or a Mersenne number is prime.

Pepin’s test, implemented in four lines of Python here, determines whether or not a Fermat number is prime. It can instantly prove that the known Fermat primes are indeed prime. It can quickly show that the next several Fermat numbers are composite, but the time required to run Pepin’s test increases rapidly for larger numbers.

The Lucas-Lehmer test, implemented in six lines of Python here, tests whether a Mersenne number is prime. The largest known primes are Mersenne primes because the Lucas-Lehmer test is relatively efficient, though it still takes a lot of effort to search for new Mersenne primes.

Certifying that a number is composite is potentially much easier than certifying that a number is prime. A famous example of a proof that a number is composite was Euler’s announcement in 1732 that

2³² + 1 = 641 × 6700417,

thereby proving that the fifth Fermat number is not prime, disproving Fermat’s conjecture.

Several Fermat numbers have been fully factored, concretely proving that they are composite, but some Fermat numbers have been proven composite via Pepin’s test that have not been factored. The analogous statement is true for Mersenne primes and the Lucas-Lehmer test.

I’ve written recently about a simple kind of primality certificates, Pratt certificates. These certificates are easy to understand, and easy to verify, but they’re expensive to produce. In order to produce a Pratt certificate that n is a prime you have to factor n-1, and that can take a long time if n is large [1]. So Pratt certificates are only used in practice for moderately large primes. “Moderate” could mean a 50-digit number, which is large for some purposes, but would not be considered large in the context of cryptography.

High-level description

Elliptic curve primality proofs are used to certify primes that are too large for Pratt certificates. The Goldwasser-Kilian theorem says that a number p is prime if there exists an elliptic curve with certain properties that depend on another prime q. As with Pratt certificates, this process is applied recursively: p is prime if q is prime, and q is prime if r is prime, … down some the base case of primes so small that they are recognized as prime.

The Goldwasser-Kilian theorem gives a lower bound on the size of q:

q > p^1/2 + p^1/4 + 1.

Ideally you find a q that’s not too much bigger than it needs to be. So to prove a 100-digit number is prime, maybe you reduce the problem to proving than an 80-digit number is prime, then reduce that to the problem of proving a 64-digit number is prime, etc.

Details

What is this elliptic curve in the theorem? You have to find a smooth curve mod p and a point M on the curve such that M is not the group identity, but qM is the group identity. How in the world would you go about finding such a curve? That’s a more complicated story, but the main idea of certificates is that they’re easy to verify, not easy to produce. Coming up with an elliptic curve primality proof is harder than verifying one [2].

Primality certificates need to be computationally easy to verify, not necessarily conceptually easy to verify. But they tend to be conceptually easier to verify than to produce as well. The rest of this post will outline how you could write your own code to verify an elliptic curve primality certificate.

How to verify from scratch

To verify an elliptic curve primality proof, you first [3] have to verify that someone has given you a smooth elliptic curve. They give you two numbers, a and b, and claim that

y² = x³ + ax + b

is a smooth elliptic curve over the integers mod p. To verify this you have to compute

4a³ + 27b²

and show that it is not divisible by n. Then you have to verify that the point M = (x, y) they gave you is on the curve, which requires sticking x and y into the cubic equation above and verifying that the equation holds mod p.

The last and most difficult step is to verify that qM gives the group identity for the elliptic curve. You have to add M to itself q times using the group law of the curve [4].

Implementing the group law for an elliptic curve modulo a prime is a little tedious, but the only difficult part is finding a multiplicative inverse mod p. Presumably your computing environment would have a library routine for modular inverses. For example, Mathematica has the function ModularInverse.

Related posts

• Cryptography articles
• How probable is a probable prime?

[1] If n is a safe prime then q = (p-1)/2 is also a prime, and so proving that q is prime is just about as hard as proving p is prime. Such hard luck can’t keep going. As you recurse you eventually get to primes p such that p-1 factors into pieces much smaller than p, but the process can start of being difficult.

[2] Elliptic curve primality certificates are sometimes called Atkin-Goldwasser-Kilian-Morain certificates or Atkin-Morain certificates because Atkin and Morain did a lot of work to make the idea of Goldwasser and Kilian practical.

[3] The Goldwasser-Kilian theorem also requires that p is not divisible by 2 or 3, but that’s trivial to verify.

[4] In practice you don’t literally add M to itself q times, but you produce a result that is the same as if you did. You’d use repeated doubling, analogous to using repeated squaring in fast exponentiation.

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¹⁶ + 1 = 65537 is prime.

We’re on a roll. What about j = 5? Is 2³² + 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 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₅, 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.