43rd IMO shortlist 2002/N3 solution

43rd IMO 2002 shortlist

Problem N3

If N is the product of n distinct primes, each greater than 3, show that 2^N + 1 has at least 4ⁿ divisors.

Solution
The starting point is obviously that for odd a, b, we have 2^ab + 1 = (2^a + 1)(2^a(b-1) - 2^a(b-2) + ... + 1) (*).

We show that if a, b are odd and relatively prime, then gcd(2^a + 1, 2^b + 1) = 3. Certainly 2^a = (-1)^a = -1 mod 3, so 3 divides both. Suppose k > 3 divides 2^a + 1 and 2^b + 1. Take positive integers r, s such that ra - sb = 1. Just one of r, s must be odd. Suppose r is odd. Then k divides 2^a + 1 which divides 2^ra + 1 (*). But 2^ra + 1 = 2^nb+1 + 1 = 2^b+12^(n-1)b + 1 = 2^b+1 (2^(n-1)b + 1) - (2^b+1 - 1), so k divides 2^b+1 - 1. It divides 2(2^b + 1) and hence also 3. Similarly if s is odd, then k divides 2^sb + 1 and hence 2^ra-1 + 1 = 2^a-1 (2^(r-1)a + 1) - (2^a-1 - 1). Hence k divides 2^a-1 - 1, so 2^a - 2. Also 2^a + 1, so 3.

Note that 2³ + 1 = 9, so if a is odd and not divisible by 3, then 2^a + 1 is not divisible by 9.

Now consider the case n = 1, so N = 2^p + 1. We have just shown that 3 divides N, but 9 does not. So N has a prime factor q > 3, and hence at least 4¹ factors (namely 1, 3, q, 3q).

Now we use induction on n. So let N' = pN, where N is the product of n distinct primes < the prime p. Then 2^N + 1 has at least 4ⁿ distinct factors, and 2^p + 1 has a prime factor q which does not divide 2^N + 1. Hence M = (2^N + 1)(2^p + 1)/3 has at least 2·4ⁿ distinct factors.

For any N, p > 4, we have (N - 2)(p - 2) > 2·2, so 2(N+p) < Np. But M < 2^N+p, so M² < 2^2(N+p) < 2^Np + 1 = 2^N' + 1. Now M divides 2^N' + 1, so 2^N' + 1 = M·M' for some M' > M. For each factor d of M, both d and d·M' are factors of 2^N' + 1. So we double the number of factors to get at least 4ⁿ⁺¹ factors of 2^N' + 1, which completes the induction.

43rd IMO shortlist 2002