IMO 1993 SL 19

Origin: ROM

Problem

Let a, b, n be positive integers, b > 1 and bn −1 | a. Show that the representation of the number a in the base b contains at least n digits different from zero.

Solution

Let s be the minimum number of nonzero digits that can appear in the b- adic representation of any number divisible by bn −1. Among all numbers divisible by bn −1 and having s nonzero digits in base b, we choose the number A with the minimum sum of digits. Let A = a1bn1 + \cdot \cdot \cdot + asbns, where 0 < ai \leqb −1 and n1 > n2 > \cdot \cdot \cdot > ns. First, suppose that ni \equivnj (mod n), i ̸= j. Consider the number B = A −aibni −ajbnj + (ai + aj)bnj+kn, with k chosen large enough so that nj + kn > n1: this number is divisible by bn −1 as well. But if ai + aj < b, then B has s −1 digits in base b, which is impossible; on the other hand, ai + aj \geqb is also impossible, for otherwise B would have sum of digits less for b−1 than that of A (because B would have digits 1 and ai+aj −b in the positions nj +kn+1, nj +kn). Therefore ni ̸\equivnj if i ̸= j. Let ni \equivri, where ri \in{0, 1, . . ., n −1} are distinct. The number C = a1br1 + \cdot \cdot \cdot + asbrs also has s digits and is divisible by bn −1. But since C < bn, the only possibility is C = bn −1 which has exactly n digits in base b. It follows that s = n.