Solution: Day 1, problem 2

We certainly cannot prove this, since the case k = 1 would be the assertion that there are infinitely many Fermat primes, so we must disprove it. This uses "covering congruences" and Euler's observation that Fermat's claim that F_r = 2^{2^r} + 1 is always prime fails for r = 5, as follows:
The value of 2ⁿk + 1 modulo F₀ = 3 depends on n modulo 2, so by choosing k congruent to 1 (respectively to 2) modulo 3 we can arrange that all of the values of 2ⁿ k + 1 with k odd (respectively even) are divisible by F₀ and hence composite. The value of 2ⁿ k + 1 modulo F₁ =5 depends on n modulo 4, so by choosing k congruent to 1, 2, 3 or 4 modulo 5 we can ensure that all of the values of 2ⁿ k +1 with n in any fixed residue class mod 4 are divisible by F₁ and hence composite. We choose the residue class of k mod 5 so that the values of n with 2ⁿ k + 1 = 0 (modulo 5) are disjoint from those already eliminated by the choice of k mod 3. For instance, we could choose k = 2 (modulo 3) to make the values of 2ⁿ k + 1 with n even divisible by 3, and then choose k = 3 (modulo 5) to eliminate the residue class n = 3 (modulo 4). At this point we have fixed k mod F₀ F₁ = 15 = 2⁴ - 1 (more specifically, we have 4 ways of choosing the residue class of k mod 15) and have eliminated 3/4 of the values of n.
Continuing, we find that, since the order of 2 mod F_r is exactly 2^r+1, we can choose k modulo F₂ in two ways (given the previous choices modulo F₀ and F₁ ) in such a way as to eliminate one of the remaining two residue classes of n mod 8, then choose k modulo F₃ in two ways to eliminate half of the remaining values of n, and then again modulo F₄ .
At this stage we have chosen k modulo F₀F₁ F₂ F₃ F₄ = 2³² -1 (more precisely, we have found 32 possible choices, one for each residue class n₀ mod 32) in such a way that the numbers 2ⁿ k + 1 with n not equals

n₀ (modulo 32) are always divisible by one of the primes F₀, F₁, F₂, F₃ or F₄ and hence are composite. If all F_r were prime, we would continue this way indefinitely and never eliminate all n. But Euler's discovery that F₅ factorizes as 641 x 6700417 means that at the next stage we can choose k modulo 641 to eliminate one of the two surviving residue classes of n modulo 64 and independently choose k modulo 6700417 to eliminate the other one, thus giving finally 64 choices of k modulo F₀ F₁ F₂ F₃ F₄ F₅ = 2⁶⁴ - 1 such that all members of the sequence 2ⁿ k + 1 have a factor in common with 2⁶⁴ - 1 and hence are composite. The smallest k which works is k₀ = 201446503145165177, which is congruent to 2¹⁷ modulo (2⁶⁴ - 1)/641 and to -2¹⁷ modulo 641.

Using covering congruences to composite moduli different from 2⁶⁴ - 1 we can get somewhat smaller values of k which also work, but this requires some numerical computations, while the argument using Fermat primes needs only "pure thought" plus the fact that there is at least one composite Fermat number. Note, too, that similar arguments apply for 2ⁿ k - 1 or any similar sequence.

Return to the problems.

Don Zagier 1996