Interesting Multiples

Consider the set of numbers {1, 11, 111, 1111, … , $\frac{10^{n+1}-1}{9}$ } where the last term has (n+1) '1's. Then by Pigeonhole principle, since there are (n+1) numbers, there exists two of them such that they have the same remainder when divided by n. Finding the difference will give you a multiple of n, and at the same time, the number is in form 111...111000...000. Thus all numbers n have this property and the answer is 1000.

$n$ can be multiplied by some power of 2 or 5, such that the exponents on the 2 and 5 are equal, making it a power of 10. If both exponents were 0, $n$ can be multiplied by 10 to make its multiple end with 0's.

If the first process didn't turn $n$ into a sequence of 1's followed by a sequence of 0's, then the number $\frac{1}{n}$ has a repeating decimal. If you multiply the part that repeats by $n$ (without its trailing zeros), you get some number of 9's (since it has to equal 1, and $0.\overline{9}$ is the only repeating decimal that equals 1)

Ex: $142857\cdot7=999999$

You can multiply $n$ by the repeating part to get a sequence of 9's followed by a sequence of 0's. Then, you can divide that multiple by 9 to get a sequence of 1's followed by a sequence of 0's.

If $n$ was originally divisible by 3, the dividing by 9 could've made the sequence of 1's followed by 0's not a multiple of $n$ . In these situations, just multiply the number of 1's in front of the 0's by 3 or 9 (27 would be unnecessary since the original multiple was only divided by 9).

Ex: $\frac{1}{51}=0.\overline{01960784313725490196078431372549}$ $51\cdot01960784313725490196078431372549=99999999999999999999999999999999$ $\frac{99999999999999999999999999999999}{9}=11111111111111111111111111111111$

$11111111111111111111111111111111$ (32 1's) is not divisible by 51, but $111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111$ (96 1's) is.

This process can turn any n into a sequence of 1's followed by a sequence of 0's.

To begin with we will only consider n which is not divisible by 2 or 5. Then let us consider the sequence $a_{1} = 1$ , $a_{2} = 11$ , ... , $a_{n+1} = \displaystyle\sum_{i=0}^{n} 10^i$ . There are $n+1$ terms in this sequence. We have 2 cases to inspect: The first case is that one of the terms in this sequence is a multiple of n . In that case we multiply this term by 10 to achieve a number which is a sequence of 1s followed by a 0 and thus satisfies our condition. In our second case, no single 1 of these terms is divisible by n . There are n possible remainders modulo n but the sequence has $n+1$ terms, so by the pigeonhole principle at least 2 terms in the sequence have the same remainder modulo n . So if we subtract the smaller term of such a pair from the larger term we will achieve a multiple of n which is a string of 1s followed by a string of 0s. Therefore if $gcd(n,10) = 1$ there is a valid multiple of n .

So say now instead that $n=2^b \times 5^c \times y$ where $gcd(y,10) = 1$ . We know that there is a multiple of y which satisfies the conditions, so if we were to multiply this multiple by $10^{ \text{ MAX} (b,c)}$ then this new number would be a string of 1s followed by a string of 0s and be a multiple of n .

Therefore in fact all positive integers (and thus trivially all negative integers) n satisfy the conditions, so the answer is $\fbox{1000}$

1/9n is rational number. So, it is possible to express 1/9n as repeating decimal. If period for this repeating decimal is p and q digit doesn't repeat, 99....9900...00 (number of 9 = p, number of 0 = q) is divisible by 9n. Therefore, 11...1100...00 is divisible by n.

Let us consider such a number $M = 111 \cdots 1000 \cdots 0 = 10^a + 10^{a+1} + \cdots + 10^b = 10^a \frac{10^{b-a+1}-1}{9}$ for some $0 \leq a < b$ . Now we claim all integers are suitable for some multiple of theirs being a number like $M$ .

Proof: For some $n$ , suppose $n=2^r 5^s P$ where $\gcd(10,P) = 1$ . Then,

• If $r > s$ , then $5^{r-s} n K= 10^r PK$ is such a number $M$ where $a=r$ and $b$ is chosen such that $10^{b-a+1} \equiv 1 \pmod{P}$ . Now this indeed can be done, as $\gcd(10,P) = 1$ , so choose $b=a-1 + \phi(P)$ (If $P$ is a multiple of $3$ , choose $b=a-1+\phi(9P)$ to account for the $9$ in the denominator also). Then $K = \frac{10^{b-a+1} - 1}{9P}$ is simply chosen and this suffices.

• Cases of $r \leq s$ are dealt similarly.

So all integers in $\{1,2,3, \cdots ,1000\}$ suffice this making the answer $\boxed{1000}$ .