15th Chinese 2000 Problem B2 Find all positive integers n for which we can find one or more integers m 1 , ... , m k each at least 4 such that (1) n = m 1 m 2 ... m k , (2) n = 2 M - 1, where M = (m 1 - 1)(m 2 - 1) ... (m k - 1)/2 k . Solution
: the only solution is n = m 1 = 7 = 2 3 - 1. By (2), n is odd, so all the m i are odd. Put n i = (m i - 1)/2, so M = n 1 n 2 ... n k and each n i ≥ 2. The basic idea is to show that in almost all cases 2 M - 1 > (2n 1 + 1)(2n 2 + 1) ... (2n k + 1). Put f(a) = (2 a - 1)/(2a + 1). We have 2 ab - 1 > (2 a - 1)(2 b - 1). Also, if 2 a - 1 > k(2a + 1) for some k > 1, then 2 a+1 - 2 > 4ka + 2k, so 2 a+1 - 1 > 4ka + 2k + 1 > k( 2(a + 1) + 1) (for a > 1) and hence 2 b - 1 > k(2b + 1) for all b > a. In other words f(a) is an increasing function. We have: m 2 3 4 5 6 2 m -1 3 7 15 31 63 2m+1 5 7 9 11 13 f(a) ≥ 5/3 for all a >= 4. The only value of a > 1 for which f(a)  2, then (2 M - 1)/ ∏(2n i +1) > ∏f(n i ) ≥ 1. So at least one of the n i must be 2. We have 2 2·2·2 - 1 = 255 > 125 = (2·2 + 1)(2·2 + 1)(2·2 + 1), so there cannot be more than two n i . We have 2 2 - 1 = 3/5 (2·2 + 1) and 2 2.2 - 1 = 15 = 3/5 (2·2 + 1)(2·2 + 1). But f(b) > 5/3 for b > 4, so we cannot have any n i > 4. 2 3·3 - 1 = 511 > 5/3 (2·3 + 1)(2·3 + 1), so we cannot have more than one n i = 3. Similarly, 2 4.4 - 1 is much larger than 5/3 (2·4 + 1)(2·4 + 1), so we cannot have more than one n i = 4. Thus the only possibilities for the n i are: 2; 2, 2; 3; 4; 2, 3; 2, 4; 2, 2, 3; 2, 2, 4. Checking each of these in turn, we get: 2: 2 2 - 1 = 3, (2·2 + 1) = 5, fail 2, 2: 2 4 - 1 = 15, (2·2 + 1)(2·2 + 1) = 25, fail 3: 2 3 - 1 = 7, (2·3 + 1) = 7, success 4: 2 4 - 1 = 15, (2·4 + 1) = 9, fail 2, 3: 2 6 - 1 = 63, (2·2 + 1)(2·3 + 1) = 35, fail. 2, 4: 2 8 - 1 = 255, (2·2 + 1)(2·4 + 1) = 45, fail 2, 2, 3: 2 12 - 1 = 4095, (2·2 + 1)(2·2 + 1)(2·3 + 1) = 175, fail 2, 2, 4: 2 16 - 1 is larger than (2·2 + 1)(2·2 + 1)(2·4 + 1) = 225, fail. 15th Chinese 2000 © John Scholes jscholes@kalva.demon.co.uk 5 June 2002