Why repunit-factors.c is useless

by Garrett A. Wollman

Without thinking about the problem, I wrote repunit-factors.c to do trial division of repunits by repunits. Then I realised that this was pointless. Here's why.

Let a, i, j be integers >= 2. Let R(n) represent the repunit of length n in base a. It is easy to see (I won't prove it here) that R(i + j) is equal to R(i) * aj + R(j), for all i and j. From this, we have R(i + i) = R(i) * (ai + 1). Thus, R(i * j) is a multiple of R(j) for all i and j. This in turn means that for all i and j where i divides j, R(i) divides R(j).

Thus, all repunits of composite length n are divisible by any repunits with length equal to a product of the factors of n.

I don't have the mechanism to prove the converse, that is, that any repunit of prime length has no repunit factors in the same base, but it seems to be the case. I wrote a short shell script to test this conjecture experimentally:

for length in $(primes 2 10000); do
	echo $length: $(./repunit-factors $length)
done
    

While this script has not yet finished executing, it has not found any results for the first 894 primes (or alternatively, repunits up to R6967). If anyone has written an accessible proof of this, I'd like to know about it so I can link to it from here.

There's still one question: is it possible for a repunit of composite length to have repunit factors other than those generated by the factors of its length? I don't know the answer to that question either, but I suspect that the same proof would apply.


wollman@lcs.mit.edu
MIT Laboratory for Computer Science