## Fun with repunit divisors: more solutions

In Fun with repunit divisors I posed the following challenge:

Prove that every prime other than 2 or 5 is a divisor of some repunit. In other words, if you make a list of the prime factorizations of repunits, every prime other than 2 or 5 will show up eventually.

My previous post explained two different proofs. At the end of “Fun with repunit divisors” I also posed a series of follow-up challenges; here are solutions to those.

1. Compute a repunit which is divisible by 2011 (you’ll probably want to use a computer!).

As we now know from the second proof (using Fermat’s Little Theorem), the repunit with $2010$ ones must be divisible by $2011$. So I guess a computer is not really necessary after all! However, what if we want to compute the smallest repunit which is divisible by $2011$? In that case we can compute $1 \bmod {2011}$, $11 \bmod {2011}$, $111 \bmod {2011}$, … until we get zero. However, we don’t have to actually compute a bigger and bigger repunit each time! Each repunit is related to the previous one by an application of the function $f(x) = 10x + 1$. So it suffices to keep only the remainder $\pmod {2011}$ at each step, and apply $f(x) = 10x + 1$ to each remainder to get the next (reducing $\pmod {2011}$ when needed). For example, we start out by computing $1$, $11$, $111$, $1111$, but at the next step we can reduce $11111 \bmod {2011}$ to get $1056$. Then we compute $(1056 \cdot 10 + 1) \bmod {2011} = 10561 \bmod {2011} = 506$, then $5061 \bmod{2011} = 1039$, and so on. Iterating this process on a computer is very fast, and in a fraction of a second we find that $(10^{670} - 1)/9$ is the smallest repunit divisible by $2011$. For example, I computed this using Haskell by defining

 f p x = (10*x + 1) mod p smallestRep p = (+1) . length . takeWhile (/= 0) . iterate (f p) \$ 1 

2. Prove that every prime other than 2 or 5 is actually a divisor of infinitely many repunits.

Proof: Note that multiplying, say, $111$ by $1001$ gives $111111$; multiplying by $1001001$ gives $111111111$, and so on. In general, we can see that the repunit with $m$ digits always evenly divides the repunit with $n$ digits whenever $m$ evenly divides $n$. So if $p$ is a divisor of $(10^n - 1)/9$ then it is also a divisor of $(10^{kn} - 1)/9$ for all $k \geq 1$.

3. Prove that every integer which is not divisible by 2 or 5 is a divisor of some repunit.

Proof: suppose $n$ has the prime factorization $n = p_1 p_2 \dots p_k$. We know that each $p_i$ is a divisor of some repunit $(10^{j_i} - 1)/9$. Then, by the argument above, $n$ must be a divisor of $(10^{j_1 j_2 \dots j_k} - 1)/9$. As a simple example, $231 = 3 \cdot 7 \cdot 11$; $3$ divides $111 = (10^3 - 1)/9$, $7$ divides $111111 = (10^6 - 1)/9$, and $11 = (10^2 - 1)/9$ is a repunit itself. Hence $231$ must be a divisor of $(10^{36} - 1)/9$, since $36 = 2 \times 3 \times 6$. (Actually, we can make this a bit more precise in order to find a much smaller repunit that $231$ must evenly divide. Can you see how?)

4. Generalize all of the above to repunits in bases other than 10.

In base $b$, we can define a repunit of length $n$ to be $111\dots 1_{b} = b^{n-1} + b^{n-2} + \dots + 1$. Everything above is still true as long as we replace the special excluded primes $2$ and $5$ with whichever primes show up in the prime factorization of the base $b$.

5. What’s so special about repunits here? Can you generalize to other sorts of numbers?

I’ll leave this one open for the time being! There are probably lots of interesting ways you could answer this question. 