IMO shortlist 1997/14 solution

38th IMO 1997 shortlist

Problem 14

b > 1 and m > n. Show that if b^m - 1 and bⁿ - 1 have the same prime divisors then b + 1 is a power of 2. [For example, 7 - 1 = 2.3, 7² - 1 = 2⁴.3.]

Solution

Many thanks to Kamil Duszenko for the following solution

Consider first the case n = 1. So suppose first that a - 1 and a^m - 1 have the same prime divisors. If a prime p divides m, then a - 1 divides a^p - 1, and a^p - 1 divides a^m - 1, so a - 1 and a^p - 1 have the same prime divisors. But a^p - 1 = (a - 1) L, where L = a^p-1 + a^p-2 + ... + a + 1. So if a prime q divides L, then it must divide a^p - 1 and hence a - 1. But L = (a - 1) (a^p-2 + 2 a^p-3 + ... + p-1) + p, so any prime q dividing L and a - 1 must also divide p. So L must be a power of p, m must be a power of p, and p must divide a - 1. In other words, a = 1 mod p. Hence (a^p-2 + 2 a^p-3 + ... + p-1) = 1 + 2 + ... + p-1 = p(p-1)/2 mod p. But if p > 2, p(p-1)/2 = 0 mod p, so L = p² + p mod p². But L is a power of p, so L = p. Contradiction, since L is obviously > p (or p > 2). Hence p must be 2. Hence L = a + 1, and a + 1 is a power of 2.

Now take the general case. Suppose d is the greatest common divisor of m and n. Put m = dM, n = dN and a = b^d, so that a^M - 1 and a^N - 1 have the same prime divisors, and M, N are relatively prime. Take positive integers h, k such that hM - kN = 1, then (a^hM - 1) - (a^kN - 1) = a^hM - a^kN = a^kN(a - 1). So if s > 1 divides a^M - 1 and a^N - 1, then it also divides a^hM - 1 and a^kN - 1 and hence also a^kN(a - 1). It cannot divide a^kN, so it must divide a - 1. So the greatest common divisor of a^M - 1 and a^N - 1 must divide a - 1. But a - 1 divides both, so the greatest common divisor is a - 1. So a - 1 must also have the same prime divisors as a^M - 1. It follows from the special case that a + 1 = b^d + 1 is a power of 2. Since b > 1, b^d + 1 > 2, so b^d + 1 is certainly divisible by 4. If d is even, then odd^d = 1 mod 4 and even^d = 0 mod 4, so b^d + 1 = 2 or 1 mod 4. Hence d must be odd. Hence b + 1 divides b^d + 1, so b + 1 is also a power of 2.

38th IMO shortlist 1997