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.