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.
- 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
ones must be divisible by
. 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
? In that case we can compute
,
,
, … 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
. So it suffices to keep only the remainder
at each step, and apply
to each remainder to get the next (reducing
when needed). For example, we start out by computing
,
,
,
, but at the next step we can reduce
to get
. Then we compute
, then
, and so on. Iterating this process on a computer is very fast, and in a fraction of a second we find that
is the smallest repunit divisible by
. 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
- Prove that every prime other than 2 or 5 is actually a divisor of infinitely many repunits.
Proof: Note that multiplying, say,
by
gives
; multiplying by
gives
, and so on. In general, we can see that the repunit with
digits always evenly divides the repunit with
digits whenever
evenly divides
. So if
is a divisor of
then it is also a divisor of
for all
.
- Prove that every integer which is not divisible by 2 or 5 is a divisor of some repunit.
Proof: suppose
has the prime factorization
. We know that each
is a divisor of some repunit
. Then, by the argument above,
must be a divisor of
. As a simple example,
;
divides
,
divides
, and
is a repunit itself. Hence
must be a divisor of
, since
. (Actually, we can make this a bit more precise in order to find a much smaller repunit that
must evenly divide. Can you see how?)
- Generalize all of the above to repunits in bases other than 10.
In base
, we can define a repunit of length
to be
. Everything above is still true as long as we replace the special excluded primes
and
with whichever primes show up in the prime factorization of the base
.
- 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.