Nicely restated. I found the proof very elegant as well, but you stated it better.xouper wrote:Nice.DanishDynamite wrote:Consider 2000 different numbers all consisting of 1's. Two of these numbers will give the same modulo when divided by 1999. Hence, the difference between these two numbers will be divisible by 1999. This difference will have the form 1...10...0. Since 1999 doesn't have a common factor with a number of the type 10^n, 1999 must devide the part of the number in front of the 0's.

In other words, there exist integers m>n>0 such that

1#m is congruent to 1#n, modulo 1999

(1#m - 1#n) is congruent to (1#n - 1#n), modulo 1999

(1#m - 1#n) is congruent to 0, modulo 1999

Thus, 1999 divides (1#m - 1#n)

1999 divides (1#(m-n)) * (10^n)

Since 1999 does not divide 10^n, it must divide 1#(m-n)

QED.

Using Fermat's theorem, we know that 1998 is one possible value for (m-n).

[mode="spinaltap"] My answer goes to eleven. [/mode]

I eagerly await ceptimus's computational answer to the question whether there is a smaller value for (m-n) that will also work.

In this vein, how about having a go at my "Square of 16" puzzle?