4
$\begingroup$

Possible Duplicate:
Proof that a natural number multiplied by some integer results in a number with only one and zero as digits
Why (directly!) does every number divide 9, 99, 999, … or 10, 100, 1000, …, or their product?

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

  • 0
    yet another: http://math.stackexchange.com/questions/83932/proof-that-a-natural-number-multiplied-by-some-integer-results-in-a-number-with/83936#839362012-11-01

1 Answers 1

1

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$

  • 0
    I've found$a$much more elegant solution in Arthur Engel's _Problem Solving Strategies_. It goes something like this: For any $n$ co-prime with 10, take $11$, $111$, $1111$, until $11...11$(n+1) digits. Take their remainders mod n. If any of them is $0$, we're done or else it lies between $1$ and $(n-1)$. By Pigeonhole Principle, two of the remainders must be same. Then the difference of of their corresponding repunits(of the form 111..1000..00) is$a$multiple of $n$. And since $n$ is co-prime with 10, removing the zeroes doesn't matter. Hence we get a repunit multiple of $n$.2012-11-03