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-2008 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 = a1 a2 ...an = 5n ·M , M not divisible by 5 and all ai 's are odd. Consider the numbers
N1 = 1a1 a2 ...an = 1·10n + 5n ·M = 5n (1·2n + M),3 = 3a1 a2 ...an = 3·10n + 5n ·M = 5n (3·2n + M),5 = 5a1 a2 ...an = 5·10n + 5n ·M = 5n (5·2n + M),7 = 7a1 a2 ...an = 7·10n + 5n ·M = 5n (7·2n + M),9 = 9a1 a2 ...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-2008 Alexander Bogomolny
30241222
Amazon.com Widgets
Amazon.com Widgets
