Fermat's Ladder

Fermat numbers are F_n = 2²ⁿ + 1. Each rung comes from the last: take one away, square it, add one back. So F_n+1 = (F_n − 1)² + 1. Starting from 3, you get 5, 17, 257 and 65,537, all prime. In 1640 Fermat guessed the pattern held forever.

In 1732 Euler found that the sixth rung, F₅ = 4,294,967,297, equals 641 × 6,700,417. Since then every Fermat number anyone has been able to test has turned out composite.

To ask whether a prime p divides F_n, you only need F_n's remainder when divided by p. Start at 2 and square n times, keeping only the remainder mod p each time (that's modular arithmetic). If you land on p − 1, then 2²ⁿ ≡ −1 mod p, and p divides F_n. Every number along the way stays smaller than p².

Euler and Lucas also showed that any factor has the shape p = k · 2ⁿ⁺² + 1. So the search runs over k, and each test costs only n squarings.

Run the same idea in C over every k up to two million (keeping p under 2⁶³ so it fits in one machine word) and it finishes in under a minute. It turns up factors of 23 different Fermat numbers between F₅ and F₅₅, among them F₃₂, which has about 1.3 billion digits. Here is the smallest factor it found for each:

Take any prime of the form p = k · 2^m + 1 with k odd. It divides some Fermat number exactly when 2 is a k-th power residue mod p, and for a "random" number that happens about once in k tries. We tested every such prime with odd k below 200 and 2 ≤ m ≤ 300.

This is why every factor search hammers small k first: those are the best odds. The hits it turns up are tiny factors of unimaginably large numbers. 5 · 2¹²⁷ + 1 divides F₁₂₅, and 7 · 2²⁹⁰ + 1 divides F₂₈₄.

For k = 3 the coin flip has an exact rule. Gauss showed that 2 is a cube mod p exactly when p can be written as x² + 27y², a quadratic form. So "does 3 · 2^m + 1 divide a Fermat number?" becomes a question about a shape on a grid. We checked every prime 3 · 2^m + 1 with 2 ≤ m ≤ 300.

Fourteen for fourteen. The geometry gives exactly the same answer as the arithmetic. It's a real change of viewpoint, but each candidate still has to be checked one at a time.

Finding a factor proves F_n composite. Without one, the only known test is Pépin's test (1877): F_n is prime exactly when 3^(F_n−1)/2 ≡ −1 mod F_n. Now the clock is the giant itself, so every one of the 2ⁿ − 1 squarings works on a number as large as F_n.

For F₃₃ that means about 8.6 billion squarings of 8.6-billion-bit numbers. Even with the fastest multiplication methods, that is far beyond routine computing today, which is why F₃₃ remains open.

Changing the setting has cracked hard cases before. Lenstra's elliptic curve method (1985) finds factors by working on elliptic curves mod p instead of with ordinary multiplication mod p. Each new curve gives a hidden factor another chance to fall out, and it is how Richard Brent finished factoring F₁₀ and F₁₁. The Lucas–Lehmer test for Mersenne numbers and Pépin's test for Fermat numbers are earlier versions of the same idea: a special structure turns "is it prime?" into one clean chain of squarings.