KGS math club/solution 9 1

Proof by contradiction.

Let S_1 = 9, S_2 = 99, etc.

Consider the first N values of the set. Since none of this (assumed) is divisible by N, they are all != 0 modulo N.

Hence, by the Dirichlet Box Principle (pigeonhole principle), some two of them S_i and S_j, where i > 1, j > 1, are congruent modulo N, so |S_i - S_j| = 0 modulo N.

Thus N divides |S_i - S_j|. But |S_i - S_j| = S_|i - j| * 10^(min(i, j)). Since N cannot divide S_|i - j|, N must not be relatively prime with 10^(min(i, j)). Then, since i >= 1 and j >= 1, N must have a common factor with 10.

But N is not divisible by 2 or by 5, so we have a contradiction.