imo.wolfram.com
header_a.gif Wolfram Research  
mainscorescontestantscompetition problemsaboutphotoIMO Facts


41st International Mathematical Olympiad


IMO 2000 Problems and Solutions

Taejon, Korea
July 13-25, 2000



Problem 5

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

Back to Competition Problems page


Solution

Answer: yes.

Note that for b odd we have 2ab + 1 = (2a + 1) (2a(b - 1) - 2a(b - 2) + ... + 1), and so 2a + 1 is a factor of 2ab + 1. It is sufficient therefore to find m such that (1) m has only a few distinct prime factors, (2) 2m + 1 has a large number of distinct prime factors, (3) m divides 2m + 1. For then we can take k, a product of enough distinct primes dividing 2m + 1 (but not m), so that km has exactly 2000 factors. Then km still divides 2m + 1 and hence 2km + 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 2p - 2, so the only p for which p divides 2p + 1 is 3. So the questions are whether ah = 2m + 1 (1) is divisible by m = 3h and (2) has a large number of distinct prime factors.

ah + 1 = ah(22m - 2m + 1), where m = 3h. But 2m = (ah - 1), so ah + 1 = ah(a2h - 3ah + 3). Now a1 = 9, so an easy induction shows that 3h + 1 divides ah, which answers (1) affirmatively. Also, since ah is a factor of ah + 1, any prime dividing ah also divides ah + 1. Put ah = 3h + 1 bh. Then bh + 1 = bh(32h + 1 b2h - 3h + 2 bh + 1). Now (32 h + 1 b2h - 3h + 2 bh + 1) > 1, so it must have some prime factor p > 1. But p be 3 or divide bh (since (32 h + 1 b2h - 3h + 2 bh + 1) is a multiple of 3 bh plus 1), so bh + 1 has at least one prime factor p > 3 which does not divide bh. So bh + 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 32000: (1) m has only one distinct prime factor, (2) 2m + 1 = 32001 b2000 has at least 1999 distinct prime factors other than 3, (3) m divides 2m + 1. Take k to be a product of 1999 distinct prime factors dividing b2000. Then N = km is the required number with exactly 2000 distinct prime factors which divides 2N + 1.



Back to Competition Problems page