IMO 1997 SL 14

Origin: IND

Problem

Let b, m, n be positive integers such that b > 1 and m ̸= n. Prove that if bm −1 and bn −1 have the same prime divisors, then b + 1 is a power of 2.

Solution

We use the following nonstandard notation: (1◦) for x, y \inN, x ∼y means that x and y have the same prime divisors; (2◦) for a prime p and integers r \geq0 and x > 0, pr \parallelx means that x is divisible by pr, but not by pr+1. First, bm −1 ∼bn −1 is obviously equivalent to bm −1 ∼gcd(bm −1, bn −

1. = bd −1, where d = gcd(m, n). Setting bd = a and m = kd, we reduce

the condition of the problem to ak −1 ∼a −1. We are going to show that this implies that a + 1 is a power of 2. This will imply that d is odd (for even d, a + 1 = bd + 1 cannot be divisible by 4), and consequently b + 1, as a divisor of a + 1, is also a power of 2. But before that, we need the following important lemma (Theorem 2.126). Lemma. Let a, k be positive integers and p an odd prime. If \alpha \geq1 and \beta \geq0 are such that p\alpha \parallela −1 and p\beta \parallelk, then p\alpha+\beta \parallelak −1. Proof. We use induction on \beta. If \beta = 0, then ak−1 a−1 = ak−1+\cdot \cdot \cdot+a+1 \equivk (mod p) (because a \equiv1), and it is not divisible by p. Suppose that the lemma is true for some \beta \geq0, and let k = p\beta+1t where p ∤t. By the induction hypothesis, ak/p = ap\betat = mp\alpha+\beta + 1 for some m not divisible by p. Furthermore, ak−1 = (mp\alpha+\beta+1)p−1 = (mp\alpha+\beta)p+\cdot \cdot \cdot+ p  (mp\alpha+\beta)2+mp\alpha+\beta+1. Since p |
p 

p(p−1) , all summands except for the last one are divisible by p\alpha+\beta+2. Hence p\alpha+\beta+1 \parallelak −1, completing the induction. Now let ak −1 ∼a −1 for some a, k > 1. Suppose that p is an odd prime divisor of k, with p\beta \parallelk. Then putting X = ap\beta−1 + \cdot \cdot \cdot + a + 1 we also have (a −1)X = ap\beta −1 ∼a −1; hence each prime divisor q of X must also divide a −1. But then ai \equiv1 (mod q) for each i \inN0, which gives us X \equivp\beta (mod q). Therefore q | p\beta, i.e., q = p; hence X is a power of p. On the other hand, since p | a −1, we put p\alpha \parallela −1. From the lemma we obtain p\alpha+\beta \parallelap\beta −1, and deduce that p\beta \parallelX. But X has no prime divisors other than p, so we must have X = p\beta. This is clearly impossible, because X > p\beta for a > 1. Thus our assumption that k has an odd prime divisor leads to a contradiction: in other words, k must be a power of 2. Now ak −1 ∼a−1 implies a−1 ∼a2 −1 = (a−1)(a+ 1), and thus every prime divisor q of a + 1 must also divide a −1. Consequently q = 2, so it follows that a + 1 is a power of 2. As we explained above, this gives that b + 1 is also a power of 2. Remark. In fact, one can continue and show that k must be equal to 2. It is not possible for a4 −1 ∼a2 −1 to hold. Similarly, we must have d = 1. Therefore all possible triples (b, m, n) with m > n are (2s −1, 2, 1).