IMO 2000/B2 solution

IMO 2000

Problem B2

Can we find N divisible by just 2000 different primes, so that N divides 2^N + 1? [N may be divisible by a prime power.]

Answer

Yes

Solution

Note that for b odd we have 2^ab + 1 = (2^a + 1)(2^a(b-1) - 2^a(b-2) + ... + 1), and so 2^a + 1 is a factor of 2^ab + 1. It is sufficient therefore to find m such that (1) m has only a few distinct prime factors, (2) 2^m + 1 has a large number of distinct prime factors, (3) m divides 2^m + 1. For then we can take k, a product of enough distinct primes dividing 2^m + 1 (but not m), so that km has exactly 2000 factors. Then km still divides 2^m + 1 and hence 2^km + 1.

The simplest case is where m has only one distinct prime factor p, in other words it is a power of p. But if p is a prime, then p divides 2^p - 2, so the only p for which p divides 2^p + 1 is 3. So the questions are whether a_h = 2^m + 1 is (1) divisible by m = 3^h and (2) has a large number of distinct prime factors.

a_h+1 = a_h(2^2m - 2^m + 1), where m = 3^h. But 2^m = (a_h - 1), so a_h+1 = a_h(a_h² - 3 a_h + 3). Now a₁ = 9, so an easy induction shows that 3^h+1 divides a_h, which answers (1) affirmatively. Also, since a_h is a factor of a_h+1, any prime dividing a_h also divides a_h+1. Put a_h = 3^h+1b_h. Then b_h+1 = b_h(3^2h+1b_h² - 3^h+2b_h + 1). Now (3^2h+1b_h² - 3^h+2b_h + 1) > 1, so it must have some prime factor p > 1. But p cannot be 3 or divide b_h (since (3^2h+1b_h² - 3^h+2b_h + 1) is a multiple of 3b_h plus 1), so b_h+1 has at least one prime factor p > 3 which does not divide b_h. So b_h+1 has at least h distinct prime factors greater than 3, which answers (2) affirmatively. But that is all we need. We can take m in the first paragraph above to be 3²⁰⁰⁰: (1) m has only one distinct prime factor, (2) 2^m + 1 = 3²⁰⁰¹ b₂₀₀₀ has at least 1999 distinct prime factors other than 3, (3) m divides 2^m + 1. Take k to be a product of 1999 distinct prime factors dividing b₂₀₀₀. Then N = km is the required number with exactly 2000 distinct prime factors which divides 2^N + 1.

41st IMO 2000