Q:

Prove that every integer $n>0$ with $\gcd(n,10) = 1$ has a multiple that can be written with only the digit $9$.

Possible Duplicate:
Proof that a natural number multiplied by some integer results in a number with only one and zero as digits 

The question is as stated. I'm really stumped on it. It seems intuitively true, but I don't really know what direction to look in. I've calculated some examples for some values, but there doesn't seem to be any particular rhyme or reason to it that would suggest a constructive proof. I've thought about the possible remainders of $9\cdot\cdot\cdot9/n$, and wondered if I could show that the remainder must be $0$ for some $n$, but that hasn't taken me far. I've been poking and prodding at it from several directions, but I've gotten nowhere really. This is a real brain-teaser. Can anyone give me some helpful hints?

A:

Hint: It is easy with the appropriate machinery. By Euler's Theorem, we have
$$10^{\varphi(n)}\equiv 1\pmod{n}.$$
Thus $10^{\varphi(n)}-1$ is a multiple of $n$. 
Remark: We can do it without mentioning Euler's Theorem. Look at the remainders when $10^1$, $10^2$, $10^3$, and so on are divided by $n$. There can be no more than $n$ different remainders. It follows that there exist positive integers $a$ and $b$, with $a\lt b$, such that $10^a$ has the same remainder as $10^b$.  So $10^b-10^a$ is divisible by $n$, and therefore  $10^a(10^{b-a}-1)$ is divisible by $n$. But because $10^a$ and $n$ have no common factor greater than $1$, we conclude that $10^{b-a}-1$ is divisible by $n$. 
One could rephrase this at a more elementary level by looking at the ordinary "long division" process when we divide $1$ by $n$.

A:

By a simple Pigeonhole argument we can prove much more: if $\,n\,$ is coprime to $10\,$ then every integer with at least $\,n\,$ nonzero digits has a contiguous digit subsequence that forms an nonzero integer divisible by $\,n.\,$ Hence in your case the $\,n\,$ digit number $\,999\ldots999\,$ does the trick, i.e. some contiguous subsequence $\,99\ldots99\,$ is divisible by $\,n.$ 
Remark $ $ The remark that Andre added to his answer is in fact a special case of the above proof. It is instructive to examine this. Following the proof linked above, we examine the $\,n\!+\!1\,$ numbers $\,0,9,99,999,\ldots, 10^{n}\!-1\,$ till, by pigeonholing, we find two that are congruent mod $\,n,\,$ say $\,10^{j}\!-1\equiv 10^{k}\!-1,\,$ so $\,10^{j-k}\equiv 1\,$ by adding $1$ then cancelling $\,10^{k}$ (valid by $10$ is coprime to $\,n).\,$ Therefore, $ $ indeed, $ $ $\,n\mid10^{j-k}-1 = 999\cdots999\ $ (i.e. $\,j\!-\!k\,$ nines). The same pigeonhole argument proves that if $\,a\,$ is coprime to $\,n\,$ then there exists some integer $\,\ell\ge 1\,$ such that $\, a^\ell\equiv 1\pmod {\!n}.\,$ The least such $\,\ell\,$ is called the order of $\,a\,$ modulo $\, n,\,$ denoted $\,\ell = o_n(a).\,$ Furthermore we have $\,a^k\equiv 1\iff \ell\mid n\,\ $ [which is equivalent to $\,\ell = o_n(a)\,$].

