Prove that if $n$ is not divisible by 5 or 2,then there exists a number consisting of ones that is divisible by $n$.

Question

Prove that if $n$ is not divisible by 5 or 2,then there exists a number consisting of ones that is divisible by $n$.

I tried something like this-

Suppose $n=a_0+a_1 10^1+a_2 10^2+...+a_k 10^k$. Now, it is not divisible by 5 or 2. So, $a_0$ not equal to 5 or 0.

I am unable to proceed after that.

Answer 1

Define $$a_n=\dfrac{10^n-1}{9}=\underbrace{111\dots 1}_{(n\text{ times})}$$and let $$r_n=a_n\mod n$$obviously $0\le r_n<n$. According to pigeonhole principle the set of $\{r_1,r_2,...,r_n,r_{n+1}\}$ consists of two equal members namely $r_i$ and $r_j$ i.e. $$\exists 0\le j\le i\le n\qquad,\qquad r_i=r_j$$therefore $$a_i-a_j=nq_i+r_i-(nq_j+r_j)=n(q_i-q_j)+r_i-r_j=n(q_i-q_j)$$therefore $$n|a_i-a_j$$also $$a_i-a_j=\dfrac{10^i-10^j}{9}=10^j\dfrac{10^{i-j}-1}{9}=10^ja_{i-j}$$since $\gcd(n,10)=1$ so $\gcd(n,10^{j})=1$ therefore $$n|a_{i-j}$$ or $$n|\underbrace{111\dots 1}_{(i-j\text{ times})}$$

Answer 2

First, we will show the statement for $n=p^{e}$ for some prime $p\neq 2, 5$ and $e\geq 1$. If we show for this case, then we can prove the original statement by factorizing $n = p_{1}^{e_{1}}\cdots p_{r}^{e^{r}}$: for each $1\leq i\leq r$, we can find $m_{i}$ such that $11\dots 1 = (10^{m_{i}}-1)/9$ is divisible by $p_{i}^{e_{i}}$. Then for $m=\mathrm{lcm}\{m_{1}, \dots, m_{r}\}$, $11\dots 1 = (10^{m}-1)/9$ is divisible by $(10^{m_{i}}-1)/9$ for each $i$, so by $p_{i}^{e_{i}}$. Hence it is divisible by $n = \prod_{i=1}^{r} p_{i}^{e_{i}}$.

Now assume $p\neq 3$ first. By Euler's theorem, we have $$ 10^{\varphi(p^{e})}\equiv 1\,(\mathrm{mod}\,{p^{e}}) $$ where $\varphi$ is a Euler's totient function. Then $11\dots 1 = (10^{\varphi(p^{e})}-1)/9$ is divisible by $p^{e}$.

For $p=3$, by Euler's theorem again, we have $$ 10^{\varphi(3^{e+2})}\equiv 1\,(\mathrm{mod}\,3^{e+2}) $$ for any $e\geq 1$. Then $11\dots 1 = (10^{\varphi(p^{e+2})}-1)/9$ is divisible by $3^{e}$.

Answer 3

Believe it or not we learned this in elementary school.

Take $n$. Convert $\frac 1n$ into a decimal. As $\gcd(10,n) = 1$ this will be an infinite repeating decimal.

Let the repeating decimal have a basic unit of $a_1a_2....a_m = K$ so that $\frac 1n = K*\sum_{j=1}^{\infty} 10^{-j*m}$.

$10^m*\frac 1n = K*\sum_{j=0}^{\infty} 10^{-j*m}=10^m*K+ K*\sum_{j=1}^{\infty} 10^{-j*m}= 10^m K - \frac 1n$.

$(10^m - 1)\frac 1n = K$ and $n = \frac {10^m-1}K$.

If $\gcd(3n) = 1$ we are done as $9 = 10-1|(10^m - 1)$ as so $n = 9*\frac {10^m-1}{10-1}*K$ and $\frac {10^m-1}{10-1}$ is a number consisting of only ones.

But if $n = 3^j*n'$ and $\gcd(n',3) = 1$ we have $n' = 9*\frac {10^m-1}{10-1}*K$ and $n = 9*3^j*K*\frac {10^m-1}{10-1}$, and we are done.

Answer 4

If $n$ is not divisible by $2$ or $5$ then $10$ belongs to the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$.

Let $k = \text{ord}(10)$ and set

$$ s \equiv \displaystyle \sum_{i=0}^{k-1} {10}^i \pmod{n}$$

Set

$$ \lambda = \frac{n}{\gcd(s,n)}$$

By the theory found here, the number

$$ \displaystyle \sum_{i=0}^{\lambda \cdot k-1} {10}^i$$

is divisible by $n$.

---

Example

If $n = 81$ then $10$ has order $9$ and

$$ s \equiv \displaystyle \sum_{i=0}^{8} {10}^i \equiv 9 \pmod{81}$$

and

$$ \lambda = \frac{81}{\gcd(9,81)} = 9$$

and so the integer

$$ \displaystyle \sum_{i=0}^{80} {10}^i $$

is divisible by $81$ and in fact

$$ \frac{\displaystyle \sum_{i=0}^{80} {10}^i}{81}=$$ $1371742112482853223593964334705075445816186556927297668038408779149519890260631$