Help on proving that every natural number co-prime with 10 is a factor of a repunit [duplicate]

Let $n$ be a natural number co-prime with 10, and $m$, another natural number consisting entirely of $1$'s. How do you show that that for every $n$, there exists an $m$ such that $n$ divides $m$?

marked as duplicate by Micah, Emily, Phira, Chris Eagle, Gerry MyersonNov 2 '12 at 11:55

• You should state your question as a question, not an order. You should also state what you have tried and what exactly is giving you trouble. Especially since this is most likely a homework. – tomasz Nov 1 '12 at 17:02
• Hint: A repunit is of the form $\frac{10^k-1}{10-1}$. First do the case of $\gcd(n,9) = 1$. How can you guarantee a $k$ exists such that $n|(10^k-1)$? – dinoboy Nov 1 '12 at 17:06
• Related: math.stackexchange.com/q/4758 – Jonas Meyer Nov 1 '12 at 17:09
• – lab bhattacharjee Nov 1 '12 at 17:20
• @tomasz I proceeded just like dinoboy said, i.e, wrote $9n+1=10^k$. Obviously this is easy to prove for the multiples of $3$ but what about the others. I'd really appreciate help. This problem's been bugging me for a while now. – sayantankhan Nov 1 '12 at 17:35

Consider the fraction $\frac{1}{n}$. Since $n$ is coprime to $10$, the fraction is a purely repeating fraction with period $k$. Denote the repeating block by $r$. Then taking $9$ copies of $r$ appended with itself (i.e. $x=\underbrace{rr\cdots r}_{9\ \text{times}}$) we have that $x$ is necessarily divisible by $9$. Therefore $$\frac{1}{n} = 0.x\overline{x} \implies \frac{10^{9k}}{n} - x = \frac{1}{n}$$ This then gives $$10^{9k} - 1 = xn \implies \frac{10^{9k} - 1}{9} = \frac{x}{9}n$$
• @dinoboy The proof of repeating decimals that I know is based on the order of $10$ modulo $n$. What is the proof you are thinking of? – EuYu Nov 1 '12 at 18:50
• @dinoboy I'm not sure I follow. The fact that $10$ has an order modulo $n$ comes simply from the fact that $n$ and $10$ are coprime. I've never even heard of repunits being used to prove that order exists. – EuYu Nov 1 '12 at 19:06