USAMO 82/4 solution

11th USAMO 1982

Problem 4

Show that there is a positive integer k such that, for every positive integer n, k 2ⁿ + 1 is composite.

Solution

Answer: k = 542258 (for example).

Suppose p is a prime dividing 2^b - 1, 0 ≤ a < b and k = -2^b-a mod p. Then if n = a mod b, we have k 2ⁿ = -2^b-a2^a+hb = -2^(h+1)b = -1 mod p, so k 2ⁿ + 1 is divisible by p. So we would like to find a collection of pairs (a, b), such that every positive integer n satisfies n = a mod b for at least one member of the collection. We need the corresponding p distinct so that we can be sure of finding k by the Chinese Remainder theorem which satisfies k = -2^b-a mod p for all members of the collection. For the congruences n = a mod b to cover all the integers, we need the lcm of the b to be small relative to their size, so we look for an lcm with many factors.

6 = 2.3 does not work because 2² - 1 = 3, 2³ - 1 = 7, 2⁶ - 1 = 3²7, we cannot find distinct primes p. 10 = 2.5 does not work because there are not enough factors to cover all integers. The mod 2 residue covers 1/2, the mod 5 residue covers 1/5 and the mod 10 residue covers 1/10, but that adds up to less than 1. Similarly 12 does not work. We must drop one of 2, 3, 6. But then the rest cover at most 11 residue classes mod 12. So we try 24. Again we drop 6, but we have:


2: 2² - 1 = 3

3: 2³ - 1 = 7

4: 2⁵ - 1 has factor 5

8: 2⁸ - 1 has factor 17

12: 2¹² - 1 has factor 13

24: 2²⁴ - 1 has factor 241

We now find, for example, the following covering set:


0 mod 2 covers the even residues

1 mod 3 covers 1, 7, 13, 19

3 mod 4 covers 3, 11, 15, 23

5 mod 8 covers 5, 21

5 mod 12 covers 17

9 mod 24 covers 9

So we now need k which is


-4 mod 3

-4 mod 7

-2 mod 5

-8 mod 17

-128 mod 13

-2¹⁵ mod 241

The Chinese Remainder Theorem gives 542258.

Comment. This is one of the hardest problems ever set in the USAMO. You have almost no hope of solving it in a reasonable time if you have not seen it before.

11th USAMO 1982