Is there a term that is divisible by $67$, in the sequence $10, 110, 1110, 11110, ...$

Question

Consider the sequence $10, 110, 1110, 11110, 111110, ...$

Here the $n$ the term $a_n=\sum \limits_{k=1}^n\left(10^k\right)$

Is there a term which is divisible by $67$ ?

How can we show that?

Answer 1

Take $68$ numbers: $$\underbrace{10, 110, 1110,..,11111110}_{68 \text{ terms of the sequence}}$$ Consider the residues which these numbers leave when divided by $67$. By the pigeonhole principle there are two numbers with the same residues, and thus their difference is divisible by $67$: $$\underbrace{11111110}_{m \text{ digits}}-\underbrace{11111110}_{l \text{ digits}}=11..1100..00=\underbrace{11111110}_{s \text{ digits}} \cdot 10^k \cong 0 (\mod 67)$$ $$\gcd(10^k,67)=1 \Rightarrow 67| 11..110$$

Answer 2

Using Fermat's little theorem, $$10^{\phi(m)}-1\equiv0\pmod m$$ for $(m,10)=1$

Now if $(m,9)=1\iff(m,3)=1,$ $$\dfrac{10^{\phi(m)}-1}{10-1}\equiv0\pmod m$$

Finally $\underbrace{11\cdots11}_{n \text{ digits}}=\dfrac{10^n-1}9$

Here, $m=67$

Alternatively, use Pigeonhole principle

Answer 3

Here is a curious way to figure it out without using Fermat's little theorem.

What is $\frac{1}{67}$ in decimal? Well we can perform long division. At each step you carry over a remainder, which is multiplied by $10$. Note that the remainder is never $0$, otherwise the decimal expansion ends, which is not possible since $67$ times the rightmost digit cannot produce a $0$. So the remainder must be from $1$ to $66$, and eventually the remainder will repeat itself since the decimal expansion goes on forever. Thus its digits would eventually repeat too!

Let us say that one of the remainders that repeats is $r$, and let $x$ be the string of digits that appear in the decimal expansion immediately after getting a remainder of $r$ and before getting the next remainder of $r$. Let $n$ be the number of digits in $x$. We can see that $r \times 1\underbrace{00\cdots0}_{\text{$n$ zeroes}}$ is a multiple of $67$ plus the next remainder of $r$. Therefore $r \times ( 1\underbrace{00\cdots0}_{\text{$n$ zeroes}} - 1) = r \times \underbrace{99\cdots9}_{\text{$n$ nines}} = r \times 9 \times \underbrace{11\cdots1}_{\text{$n$ ones}}$ is a multiple of $67$.

But $r \times 9$ is not divisible by $67$, so $\underbrace{11\cdots1}_{\text{$n$ ones}}$ must be divisible by $67$ since $67$ is prime (by Euclid's lemma).