# 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) * a*^{j} + R(j), for all *i* and *j*.
From this, we have *R(i + i) = R(i) * (a*^{i} + 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