A Problem of Divisibility by 5ⁿ

Here is a problem from the 32^nd USAMO (2003) olympiad:

Prove that for every positive integer n there exists an n-digit number divisible by 5ⁿ all of whose digits are odd.

Solution

References

T. Andreescu and Z. Feng, 32nd United States of America Mathematical Olympiad, Math Magazine, Vol. 77, No. 2, April 2004, pp. 165-168

Prove that for every positive integer n there exists an n-digit number divisible by 5ⁿ all of whose digits are odd.

The proof is by induction. The property is obviously true for n = 1: 5 (a single odd digit number) is divisible by 5¹.

Assume that N = a₁a₂...a_n = 5ⁿ·M, M not divisible by 5 and all a_i's are odd. Consider the numbers

N₁ = 1a₁a₂...a_n = 1·10ⁿ + 5ⁿ·M = 5ⁿ(1·2ⁿ + M),
N₃ = 3a₁a₂...a_n = 3·10ⁿ + 5ⁿ·M = 5ⁿ(3·2ⁿ + M),
N₅ = 5a₁a₂...a_n = 5·10ⁿ + 5ⁿ·M = 5ⁿ(5·2ⁿ + M),
N₇ = 7a₁a₂...a_n = 7·10ⁿ + 5ⁿ·M = 5ⁿ(7·2ⁿ + M),
N₉ = 9a₁a₂...a_n = 9·10ⁿ + 5ⁿ·M = 5ⁿ(9·2ⁿ + M).

The multiples 1·2ⁿ + M, 3·2ⁿ + M, ..., 9·2ⁿ + M all have different remainders when divided by 5. (Otherwise, the difference of some two of them would be divisible by 5, which is obviously not true.) It follows that one of them is divisible by 5; the corresponding number N is then divisible by 5ⁿ·5 = 5ⁿ⁺¹.

72389909

A Problem of Divisibility by 5n

References

A Problem of Divisibility by 5ⁿ