41st International Mathematical OlympiadIMO 2000 Problems and SolutionsTaejon, KoreaJuly 13-25, 2000 Problem 5Can we find N divisible by just 2000 different primes, so that N divides 2^{N} + 1? [N may be divisible by a prime power.] Back to Competition Problems page SolutionAnswer: yes. 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 (1) is 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^{2}_{h} - 3a_{h} + 3). Now a_{1} = 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 + 1} b_{h}. Then b_{h + 1} = b_{h}(3^{2h + 1} b^{2}_{h} - 3^{h + 2} b_{h} + 1). Now (3^{2 h + 1} b^{2}_{h} - 3^{h + 2} b_{h} + 1) > 1, so it must have some prime factor p > 1. But p be 3 or divide b_{h} (since (3^{2 h + 1} b^{2}_{h} - 3^{h + 2} b_{h} + 1) is a multiple of 3 b_{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^{2000}: (1) m has only one distinct prime factor, (2) 2^{m} + 1 = 3^{2001} b_{2000} 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_{2000}. Then N = km is the required number with exactly 2000 distinct prime factors which divides 2^{N} + 1. Back to Competition Problems page |