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
- T. Andreescu and Z. Feng, 32nd United States of America Mathematical Olympiad, Math Magazine, Vol. 77, No. 2, April 2004, pp. 165-168
Copyright © 1996-2009 Alexander Bogomolny
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 = 5n ·M, M not divisible by 5 and all ai's are odd. Consider the numbers
| |
N1 = 1a1a2...an = 1·10n + 5n ·M = 5n(1·2n + M),
N3 = 3a1a2...an = 3·10n + 5n ·M = 5n(3·2n + M),
N5 = 5a1a2...an = 5·10n + 5n ·M = 5n(5·2n + M),
N7 = 7a1a2...an = 7·10n + 5n ·M = 5n(7·2n + M),
N9 = 9a1a2...an = 9·10n + 5n ·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.
Copyright © 1996-2009 Alexander Bogomolny
|
