Olympiad #3

This is their Solution, does anyone have anything easier? In fact n has a factor of 9, i.e. n = 99999m explained as follows. In words, if n has a remainder after division by 9 (e.g. remainder 1 or 2) then 11111× sum of the digits of n has 5 times that remainder (e.g. remainder 5 or 5 × 2 = 10 ≡ 1). But this is a contradiction unless the remainder is 0. More formally, put σ(n) =sum of the digits of n. Then σ(n) ≡ n(mod 9) (since 10 ≡ 1(mod 9), 100 ≡ 1(mod 9), 1000 ≡ 1(mod 9), etc.) Since 11111 ≡ 5(mod 9) then n = 11111σ(n) ≡ 5n(mod 9) hence n ≡ 0(mod 9). We will show that n = 99999m for 1 ≤ m ≤ 10. If n has k digits then σ(n) ≤ 9k hence n = 11111σ(n) ≤ 99999k < 10k−1 , k > 6 where the last inequality comes from: 99999k < 105k < 10k−1 ⇐ k < 10k−6 ⇐ k > 6. In other words, for k > 6, 99999k is less than every k digit number, hence n ≤ 99999k < n which is a contradiction. Thus n = 99999m has at most 6 digits hence 1 ≤ m ≤ 10. Now it is easy to see that σ(99999m) = 45 for 1 ≤ m ≤ 10 hence n = 45 × 11111 = 499995.