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

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?

-

## marked as duplicate by Old John, N. S., Noah Snyder, rschwieb, ArkamisNov 5 '12 at 17:12

\begin{align} 99 & = 3\cdot3\cdot11 \\ 999 & = 3\cdot3\cdot3\cdot37 \\ 9999 & = 3\cdot3\cdot101 \\ 99999 & = 3\cdot3\cdot41\cdot271 \\ 999999 & 3\cdot3\cdot7\cdot11\cdot13\cdot37 \\ 9999999 & = 3\cdot3\cdot11\cdot73\cdot101\cdot137 \end{align} The claim seems to be that every positive integer whose last digit is not $0,2,4,5,6$, or $8$ will appear in one of these factorizations. (Not as one of the prime factors, but as the product of some of them.) – Michael Hardy Nov 4 '12 at 23:09
If I can believe the software that gave me these results, then $9999999999$ is divisible by $9091$, and $999999999999$ is divisible by $9901$, and $99999999999999$ is divisible by $909091$. I'm too lazy right now to explain what pattern I'm looking at, let alone find the obvious reason why it happens. But probably there is one. – Michael Hardy Nov 4 '12 at 23:14

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$.

-
That's super slick and I might use it. I'd like to have a more intuitive understanding of why this occurs, though. Perhaps examining the proof(s) of Euler's formula will reveal to me why this works. Thanks a bunch. – limp_chimp Nov 4 '12 at 23:15
@limp_chimp: I have added an argument that does not mention Euler's Theorem. It contains an idea that is useful elsewhere. – André Nicolas Nov 4 '12 at 23:23
Thanks for that second argument; that one I can wrap my head around :) – limp_chimp Nov 5 '12 at 3:26
Note $\$ The remark added in your later edit is in fact a special case of the proof in my prior answer - see my added remark there. – Bill Dubuque Nov 5 '12 at 5:09

By a simple Pigeonhole argument one can prove much more: if $\rm\:n\:$ is coprime to $10\,$ then every integer with at least $\rm\:n\:$ digits $\ne 0$ has a contiguous digit subsequence that forms an integer $\ne 0$ divisible by $\rm\:n.\:$ Hence in your case the $\rm\,n\,$ digit number $\,999\ldots999\,$ does the trick, i.e. some subsequence $\,99\ldots99\,$ is divisible by $\rm\,n.$

Remark $\$ The remark that Andre added to his answer is in fact a special case of the above proof. It's instructive to examine this. Following the proof linked above, we examine the $\rm\:n\!+\!1\:$ numbers $\rm\:0,9,99,999,\ldots, 10^{\,n}\!-1\:$ till, by pigeonholing, we find two that are congruent mod $\rm\,n,\,$ say $\rm\:10^{\,j}\!-1\equiv 10^{\,k}\!-1,\:$ so $\rm\:10^{\,j-k}\equiv 1\:$ by adding $1$ then cancelling $\rm\,10^{\,k}$ (valid by $10$ is coprime to $\rm\,n).\:$ Therefore, indeed, $\rm\:n\mid10^{\,j-k}\!-1 = 999\cdots999\$ (i.e. $\rm\:j\!-\!k\:$ nines). The same pigeonhole argument proves that if $\rm\,a\,$ is coprime to $\rm\,n\,$ then, mod $\rm n,\,$ the order of $\rm\,a\,$ is finite $\rm\le n.$

-
Thanks, this is really great. I understand it much better now having read through your proof. This stuff is not so intuitive for me :P – limp_chimp Nov 4 '12 at 23:30