# A Problem of Divisibility by 5^{n}

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

Prove that for every positive integer n there exists an ^{n} all of whose digits are odd.

### References

- 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} all of whose digits are odd.

The proof is by induction. The property is obviously true for ^{1}.

Assume that _{1}a_{2}...a_{n} = 5^{n }·M_{i}'s are odd. Consider the numbers

N_{1} = 1a_{1}a_{2}...a_{n} = 1·10^{n} + 5^{n }·M = 5^{n}(1·2^{n} + M),

N_{3} = 3a_{1}a_{2}...a_{n} = 3·10^{n} + 5^{n }·M = 5^{n}(3·2^{n} + M),

N_{5} = 5a_{1}a_{2}...a_{n} = 5·10^{n} + 5^{n }·M = 5^{n}(5·2^{n} + M),

N_{7} = 7a_{1}a_{2}...a_{n} = 7·10^{n} + 5^{n }·M = 5^{n}(7·2^{n} + M),

N_{9} = 9a_{1}a_{2}...a_{n} = 9·10^{n} + 5^{n }·M = 5^{n}(9·2^{n} + M).

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

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

Copyright © 1996-2018 Alexander Bogomolny