- MacTutor History of Mathematics

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^{n}k + 1

modulo

F_{0} = 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^{n}k + 1

with

k

odd (respectively even) are divisible by

F_{0}

and hence composite. The value of

2^{n}k + 1

modulo

F_{1} = 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^{n}k + 1

with

n

in any fixed residue class mod 4 are divisible by

F_{1}

and hence composite. We choose the residue class of

k

mod 5 so that the values of

n

with

2^{n}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^{n}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_{0} F_{1}

= 15 = 24 - 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_{2}

in two ways (given the previous choices modulo

F_{0}

and

F_{1}

) in such a way as to eliminate one of the remaining two residue classes of

n

mod 8, then choose

k

modulo

F_{3}

in two ways to eliminate half of the remaining values of

n

, and then again modulo

F_{4}

.

At this stage we have chosen

k

modulo

F_{0} F_{1} F_{2} F_{3} F_{4} = 2^{32} - 1

(more precisely, we have found 32 possible choices, one for each residue class

n_{0}

mod 32) in such a way that the numbers

2^{n}k + 1

with

n ≠ n_{0}

(modulo 32) are always divisible by one of the primes

F_{0}, F_{1}, F_{2}, F_{3}

F_{4}

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_{5}

factorizes as 641 × 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_{0} F_{1} F_{2} F_{3} F_{4} F_{5}

= 264 - 1 such that all members of the sequence

2^{n}k + 1

have a factor in common with 264 - 1 and hence are composite. The smallest

k

which works is k0 = 201446503145165177, which is congruent to 217 modulo (264 - 1)/641 and to -217 modulo 641.

Using covering congruences to composite moduli different from 264 - 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^{n}k - 1

or any similar sequence.