IMO 1972 SL 6

Origin: GDR

Problem

Show that for any n ̸\equiv0 (mod 10) there exists a multiple of n not containing the digit 0 in its decimal expansion.

Solution

Let n = 2\alpha5\betam, where \alpha = 0 or \beta = 0. These two cases are analogous, and we treat only \alpha = 0, n = 5\betam. The case m = 1 is settled by the following lemma. Lemma. For any integer \beta \geq1 there exists a multiple M\beta of 5\beta with \beta digits in decimal expansion, all different from 0. Proof. For \beta = 1, M1 = 5 works. Assume that the lemma is true for \beta = k. There is a positive integer Ck \leq5 such that Ck2k + mk \equiv 0 (mod 5), where 5kmk = Mk, i.e. Ck10k +Mk \equiv0 (mod 5k+1). Then Mk+1 = Ck10k + Mk satisfies the conditions, and proves the lemma.

In the general case, consider, the sequence 1, 10\beta, 102\beta, . . . . It contains two numbers congruent modulo (10\beta −1)m, and therefore for some k > 0, 10k\beta \equiv1 (mod (10\beta −1)m) (this is in fact a consequence of Fermat’s theorem). The number 10k\beta −1 10\beta −1 M\beta = 10(k−1)\betaM\beta + 10(k−2)\betaM\beta + \cdot \cdot \cdot + M\beta is a multiple of n = 5\betam with the required property.