A Problem of Divisibility by 5n

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

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

Solution

References

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

|Contact| |Front page| |Contents| |Arithmetic| |Math induction|

Copyright © 1996-2018 Alexander Bogomolny

Prove that for every positive integer n there exists an n-digit number divisible by 5n 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 51.

Assume that N = a1a2...an = 5·M, M not divisible by 5 and all ai's are odd. Consider the numbers

N1 = 1a1a2...an = 1·10n + 5·M = 5n(1·2n + M),
N3 = 3a1a2...an = 3·10n + 5·M = 5n(3·2n + M),
N5 = 5a1a2...an = 5·10n + 5·M = 5n(5·2n + M),
N7 = 7a1a2...an = 7·10n + 5·M = 5n(7·2n + M),
N9 = 9a1a2...an = 9·10n + 5·M = 5n(9·2n + M).

The multiples 1·2n + M, 3·2n + M, ..., 9·2n + 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 5n·5 = 5n+1.

|Contact| |Front page| |Contents| |Generalizations| |Arithmetic| |Math induction|

Copyright © 1996-2018 Alexander Bogomolny

71493406