IMO 2000 SL N3

Origin: RUS | Category: Number Theory

Problem

Does there exist a positive integer n such that n has exactly 2000 prime divisors and 2n + 1 is divisible by n?

Solution

More generally, we will prove by induction on k that for each k \inN there exists nk \inN that has exactly k distinct prime divisors such that nk | 2nk + 1 and 3 | nk. For k = 1, n1 = 3 satisfies the given conditions. Now assume that k \geq1 and nk = 3\alpham where 3 ∤m, so that m has exactly k −1 prime divisors. Then the number 3nk = 3\alpha+1m has exactly k prime divisors and 23nk+1 = (2nk + 1)(22nk −2nk + 1) is divisible by 3nk, since 3 | 22nk −2nk + 1. We shall find a prime p not dividing nk such that nk+1 = 3pnk. It is enough to find p such that p | 23nk + 1 and p ∤2nk + 1. Moreover, we shall show that for every integer a > 2 there exists a prime number p that divides a3 + 1 = (a + 1)(a2 −a + 1) but not a + 1. To prove this we observe that gcd(a2 −a + 1, a + 1) = gcd(3, a + 1). Now if 3 ∤a + 1, we can simply take p = 3; otherwise, if a = 3b −1, then a2 −a + 1 = 9b2 −9b + 3 is not divisible by 32; hence we can take for p any prime divisor of a2−a+1 .