IMO 2002 SL N3

Origin: MON | Category: Number Theory

Problem

Let p1, p2, . . . , pn be distinct primes greater than 3. Show that 2p1p2\cdot\cdot\cdotpn + 1 has at least 4n divisors.

Solution

We observe that if a, b are coprime odd numbers, then gcd(2a+1, 2b+1) = 3. In fact, this g.c.d. divides gcd(22a−1, 22b−1) = 2gcd(2a,2b)−1 = 22−1 = 3, while 3 obviously divides both 2a + 1 and 2b + 1. In particular, if 3 ∤b, then 32 ∤2b +1, so 2a +1 and (2b +1)/3 are coprime; consequently 2ab +1 (being divisible by 2a + 1, 2b + 1) is divisible by (2a+1)(2b+1) . Now we prove the desired result by induction on n. For n = 1, 2p1 + 1 is divisible by 3 and exceeds 32, so it has at least 4 divisors. Assume that 2a+1 = 2p1\cdot\cdot\cdotpn−1 +1 has at least 4n−1 divisors and consider N = 2ab+1 = 2p1\cdot\cdot\cdotpn + 1 (where b = pn). As above, 2a + 1 and 2b+1 are coprime, and thus Q = (2a + 1)(2b + 1)/3 has at least 2 \cdot 4n−1 divisors. Moreover, N is divisible by Q and is greater than Q2 (indeed, N > 2ab > 22a22b > Q2 if a, b \geq5). Then N has at least twice as many divisors as Q (because for every d | Q both d and N/d are divisors of N), which counts up to 4n divisors, as required. Remark. With some knowledge of cyclotomic polynomials, one can show that 2p1\cdot\cdot\cdotpn + 1 has at least 22n−1 divisors, far exceeding 4n.