The set of numbers {9, 99, 999, 9999, ...} has some interesting properties. One of these has to do with factorization. Take any number n that isn't divisible by 2 or by 5. You will be able to find at least one number in the set that is divisible by n. Furthermore, you won't need to look beyond the first n numbers in the set.

Prove it.

(from http://www.ocf.berkeley.edu/~wwu/riddles/)

The set {9, 99, 999, ...} can be expressed as {10^1 - 1, 10^2 - 1, 10^3 - 1, ...}

Choose any number n coprime to 10 (stated by the problem) and consider the subset {10^1 - 1, 10^2 - 1, 10^3 - 1, ..., 10^(n+1) - 1}.

There are at most n unique remainders when the elements of the subset are divided by n. But because there are n+1 elements, there are at least two elements with the same remainder.

Let 10^y - 1 and 10^x - 1 be two elements with the same remainder with y > x. Then ((10^y - 1) - (10^x - 1)) mod n = 0.

Let d=y-x. (10^y - 1) - (10^x - 1) = 10^y - 10^x = 10^x * (10^(y-x) - 1) = 10^x * (10^d - 1)

Since n is coprime to 10, n is a factor of 10^d - 1.

This proves there is some member of the set {9, 99, 999, ...} (the dth member) which has n as a factor.

Since n+1 >= y and y > d, d will never be greater than n.

This proves that the number 10^d - 1 is one of the first n terms of the set {9, 99, 999, ...}.
Edited on January 22, 2004, 1:14 pm

Posted by Brian Smith on 2003-05-08 06:26:33