The sequence 1,11,111,… and the prime factorization of its elements

I have been recently investigating the sequence 1,11,111,... I found, contrary to my initial preconception, that the elements of the sequence can have a very interesting multiplicative structure. There are for example elements of the sequence that are divisible by primes like 7 or 2003.

What I am interested in is for what numbers, other than 2 and 5 can we say that they divide no element of the sequence?

• These numbers have a name $-$ see Wikipedia's Repunit article. – TonyK Nov 11 '13 at 18:32

In fact, every number coprime with $10$ (that is, those that aren't integer multiples of $2$ and/or $5$) divides some element of that sequence. See this question.

On the other hand, it is immediately clear that no even number or integer multiple of $5$ can divide an element of that sequence.

Indeed, there are such nice properties. To start, consider the following exercise from The Art and Craft of Problem Solving by Paul Zeitz.

Example 1.2: There is an element in the sequence $7, 77, 777, \cdots$ that is divisible by $2003$.

Proof: We prove that even a stronger statement is true, in fact, one of the first $2003$ elements of the sequence is divisible by $2003$. Let us assume that the contrary is true. Then take the first $2003$ elements of the sequence and divide each of them by $2003$. As none of them is divisible by $200$, they will have have a remainder that is at least $1$ and at most $2002$. As there are $2003$ remainder (one for each of the first $2003$ elements of the sequence), and only $2002$ possible values for these remainders, it follows by the Pigeonhole Principle that there are two elements out of the first $2003$ that have the same remainder. Let us say that the $i$th and $j$th elements of the sequence $a_i$ and $a_j$, have this property, and let $i < j$. Consider the following difference: $$\underbrace {777 \cdots 7}_{j \, \text{digits}} - \underbrace {77 \cdots 7}_{i \, \text{digits}} = \underbrace {7 \cdots 7}_{j-i \, \text{sevens}}\underbrace{0 \cdots 0}_{i \, \text{zeroes}}.$$As $a_i$ and $a_j$ have the same remainder when divided by $2003$, there exist non-negative integers $k_i$, $k_j$, and $r$ so that $r \le 2002$, and $a_i = 2003k_i + r$ and $a_j = 2003k_j + r$. This shows that $a_j - a_i = 2003 \cdot (k_j - k_i)$, so in particular, $a_j-a_i$ is divisible by $2003$.

This is nice, but we need to show that there is an element in our sequence that is divisible by $2003$, and $a_j-a_i$ is not an element in our sequence. However, the centered text above is very useful.

Indeed, $a_j-a_i$ consists of $j-i$ digits equal to $7$, when $i$ digits equal to $0$. In other words, $$a_j - a_i = a_{j-1} \cdot 10^i,$$ and the proof follows as $10^i$ is relatively primes to $2003$, so $a_{j-1}$ must be divisible by $2003$.

$\blacksquare$

Can you generalize? Also, see here.

• Precisely this problem got me thinking about the series, I just threw out the 7 as I saw no use in it. Btw. I have the problem from the book Walk through combinatorics. – Adam Nov 11 '13 at 18:45
• Yep, it's in that book too! – Ahaan S. Rungta Nov 11 '13 at 18:56

As you can see in the answers to this question, a number has a multiple of the form $111...1$ if the number is not divisible by $2$ and $5$ (i.e. relatively prime to 10).

Conversely, if a number has a multiple of the form $111.11$ its multiple is not divisible by $2$ or $5$ since the last digit is $1$. Thus the number is relatively prime to $2$ and $5$.

Conclusion: A number $n$ has a multiple of the form $11111....1$ if and only if the number is relatively prime to $10$.

P.S. Another interesting property. For any prime $p \neq 2,5$ it follows from Fermat Little Theorem that

$$p|10^{p-1}-1 \,.$$

From here it follows immediately that for any prime $p \neq 2,3,5$, $p|111...1$, where there are exactly $p-1$ ones...