Write a proof that for every positive integer n, there exist i and j with 1 ≤ i < j ≤ n + 1, such that n is a divisor(must be a factor of) of $66 . . . 6$(j digits) $ - 66 . . . 6 $(i digits).
I tried to use the php to based on the fact that there are n+1 ways to pick an integer for i and j each and there are n-1 remainders possible. After that I am stuck and do not know how to proceed? Any help and/or solutions?
On
I agree that Laska and Robert Shore have established the answer, but I decided to put a version with more detail for those who are having trouble following:
Consider the case n=1:
In this special case, 1≤i<j≤n+1 means that i=1 and j=2. Robert Shore asks us to consider the set of integers 6 and 66 (since n=1, there are only n+1=2 integers to consider). Since 6 mod 1 = 0 and 66 mod 1 = 0, there is no surprise that 66-6 mod 1 = 0 as well. This is trivial since every integer is divisible by 1; cases for n=2, n=3, and n=6 are equally trivial, since 6 is always divisible by n. Similarly, for cases n=4, n=5, the numbers in question always have the same mod (6 mod 4 = 2, 66 mod 4 = 2, etc).
Consider the case n=7:
In this case, we are asked to consider the integers 6, 66, 666, 6666, 66666, 666666, 6666666, and 66666666 (since we need to consider n+1=8 integers). Since x mod n can only have n possible outcomes, we know that we'll get an answer more than once:
Notice that even if we had gotten all of the possible x mod 7 answers (0..6), the 8th answer would have had to have been in the previous answer set. In this case, we got lucky and it started over the integer before that. Since there are always two values that have the same remainder mod 7, we use those to select i and j, i<j. In this case:
$(6666666 - 6) \text{ mod } 7 = 6666660 \text{ mod } 7 = 0$
which is a given, since
$(6666666 - 6) \text{ mod } 7 = (6666666 \text{ mod } 7) - (6 \text{ mod } 7) = 6 - 6 = 0$
Consider the general case n:
Laska and Robert Shore have already pointed out to us that we'll be considering n+1 integers (since j≤n+1) and that x mod n can only have n potential outcomes (from 0..n-1), so we will definitely see an overlap with two integers having the same remainder (this is the pigeonhole principle -- we have n pigeonholes and n+1 things to put in them, so we are promised at least one pigeonhole will get two items).
Therefore, no matter how large of a number we pick for n, we will see results like for n=7 (or trivially, like n=1 or n=4) where we can easily pick integers i and j based on where the overlap occurs.
Let's clean up Laska's comment.
Consider the $n+1$ integers $6, 66, 666, \ldots, \underbrace{66\ldots 6}_{n+1 \text{ digits}}$. There are $n+1$ of these numbers. There are $n$ possible residues $\pmod n: 0, 1, 2, \ldots, n-1$. Therefore, by the pigeonhole principle two distinct integers within our collection, with $1 \leq i \lt j \leq n+1$ digits, respectively, must have the same residue. Their difference is therefore divisible by $n$.