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.

About these ads
This entry was posted in arithmetic, iteration, modular arithmetic, number theory, primes, programming, proof, solutions and tagged . Bookmark the permalink.