Suppose a = positive integer and gcd(a, 10) = 1. Prove that a divides infinitely many repunits.

Question

Consider $S_{n} = 11...11$ where $1$ is listed $n$ times. Prove that $a$ divides $S_n$ for infinitely many values of $n$.

Also consider $S_{n} = {10^{n} - 1 \over 9}$

Examples:

$S_{2} = 11, S_{3} = 111, S_{4} = 1111, S_{5} = 11111, ... etc.$

Please advise on my proof so far:

given $gcd(a,10) = 1 \implies gcd(9a, 10) = 1$

WTS: $S_{n} = {10^{n} - 1 \over 9} \equiv 0 \pmod a$ is infinite.

$10^{n} - 1 \equiv 0 \pmod {9a}$

I do not know where to go from here.

Answer 1

Hint:

Use Little Fermat's theorem in $\Bbb Z_a$; if $3\not\mid a$, you should have it. If $3\mid a$ consider the number $S_{9n}$.

Answer 2

Because of $$\gcd(9a,10)=1$$ we have $$10^{\varphi(9a)}\equiv 1\mod 9a$$ (Euler's theorem) which means $$9a\mid 10^{\varphi(9a)}-1$$ and therefore $$a\mid \frac{10^{\varphi(9a)}-1}{9}$$ which is a rep-unit.

If we replace the exponent $\varphi(9a)$ by an arbitary multiple of it, the congruence still holds, so there are infinite many possible exponents.

Answer 3

Consider the set of the first $a$ repunits $R=\{1,11,111,\dots,(10^a-1)/9\}$, and assume initially that none of them is divisible by $a$.

There are $a$ different repunits in $R$, which, when divided by $a$, each have remainders in $\{1,2,\dots,a-1\}$. By the pigeonhole principle at least two of the remainders are equal. The positive difference of these two repunits with equal remainders must be divisible by $a$. Denote these two repunits $S_b$ and $S_c$ with $b>c$.

$S_b-S_c=11\dots11 -11\dots11=11\dots1100\dots00=11\dots11\cdot10^m=S_d\cdot10^m$ for some $d,m\in\mathbb{N}$.
(Example: $1111111-111=1111000=1111\cdot10^3=S_4\cdot10^3$.)

We are given that $\gcd(a,10)=1$, so $a$ cannot divide $10^m$ and must therefore divide $S_d$, but $S_b\in R$ and $S_d$ is a repunit that is shorter than $S_b$ so $S_d\in R$ and $a|S_d$. This contradicts our original assumption, so $a$ must divide at least one of the first $a$ repunits.

This proves that we can find at least one $S_n$ such that $a|S_n$. Finally, we can note that for all $k\in\mathbb{N}, S_n|S_{kn}$ so we can find infinitely many repunits $S_n$ such that $a|S_n$.