# Primes dividing $11, 111, 1111, …$

How can I prove that every prime except 2 and 5 divide infinitely many of the following integers $11, 111, 1111, …$ ?

#### Solutions Collecting From Web of "Primes dividing $11, 111, 1111, …$"

Hint: Use Fermat’s little theorem to conclude that $10^{n(p-1)} – 1$ is divisible by $p$ for every prime $p$ other than $2, 5$.

Define the infinite sequence $S =s_2, s_3, s_4 \dots$ as $11, 111, 1111, \dots$.

Consider all $s_i$ modulo a prime $p$ other than 2 or 5. By the pigeonhole principle, there must be a residue $r$ such that infinite $s_i$ are congruent to it. Let $s_a$ be the smallest such element of $S$.

Let $s_b$ be one of the infinite set of elements of $S$ with residue $r$ that are greater than $s_a$. Their difference, $s_b – s_a$ is divisible by $p$. It has the form $11\dots1100\dots000 = s_{b-a} \cdot 10^{a}$. Since $p$ is neither 2 nor 5, $p$ must divide $s_{b-a}$. Since there is an infinite set of $s_b > s_a$ with residue $r$, there must also be an infinite set of $s_{b-a}$ divisible by $p$.

The decimal expresion of $1/p$ is periodic, and it can be expressed as
$$\frac n{99\ldots9}$$

Therefore, if $p\neq 3$, $p$ divides $\underbrace{11\ldots1}$. And if $p=3$, $p$ divides $111$.

It is enough to find a number $111…1$ (n digits) divisible by p in whose case all number $1111….1$ formed by $nk$ digits is clearly multiple of $p$ also.

For $p\ne2,5$ all powers $10^r$ with $r=1,2,…..,p-1$ are distinct because if $10^r\equiv10^{r+k}\equiv 0 (mod\space p)$ with $0<k<p-1$ then $10^k\equiv0 (mod\space p)$ so $p=2,5$. On the other hand,the sum of $p-1$ distinct elements $1+10+10^2+10^3+….+10^{p-2}$ must be equal to $0$ modulo $p$ by a known property of finite fields.

Consequently for p given the number $111….1$ having $p-1$ digits is divisible by $p$.

Example with $12$ digits: $$\frac{111111111111}{13}=8547008547$$ And the same goes for all $111…..1$ with $12k$ digits.

Let $R(k)$ be the number represented as $k$ copies of “$1$”, so $R(k) = \sum_{i=0}^{k-1}10^i$ and note that $9R(k) = 10^k-1$

For simplicity consider the case of $p=3$ first: Since the digit sum of $R(k)$ is $k$, we know that for every $k$ such that $3\mid k$ then also $3 \mid R(k)$, so the claim is proven for $p=3$.

Now for other primes $p \not\in \{2,3,5\}$, consider that since $\gcd(p,10)=1$, by Fermat’s little theorem we have $10^{p-1}\equiv 1 \bmod p$ and thus $10^{k(p-1)}\equiv 1 \bmod p$ for all $k\in \mathbb N$. Thus $p \mid (10^{k(p-1)}-1)$ giving $p \mid 9R(k(p-1))$ and since $\gcd(9,p)=1$ we have $p \mid R(k(p-1))$ as required.