Fun with repunit divisors: proofs

As promised, here are some solutions to the repunit puzzle posed in my previous post. (Stop reading now if you don’t want to see solutions yet!)

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.

Proof 1: Note that we can write the repunit containing $n$ ones as $(10^n - 1)/9$ . Suppose $p$ is a prime other than $2$ or $5$ , and consider the remainders when repunits are divided by $p$ . Since there are infinitely many repunits and only $p$ possible remainders, by the Pigeonhole Principle there must be some remainder which is repeated, that is, there must be two distinct numbers $i$ and $j$ (let’s say $i < j$ ) such that

$(10^j - 1)/9 \equiv (10^i - 1)/9 \pmod p.$

Bringing $(10^i - 1)/9$ over to the left-hand side and simplifying gives

$(10^j - 10^i)/9 \equiv 0 \pmod p.$

Since $i < j$ we can factor out $10^i$ , giving

$10^i(10^{j-i} - 1)/9 \equiv 0 \pmod p.$

Now, although it is perfectly OK to add, subtract, or multiply by the same thing on both sides of a modular equation, we have to be careful with division: it is only safe to divide both sides of a modular equation by some number which does not share any common factors with the modulus. Well, in this case we began by assuming that $p$ is neither $2$ nor $5$ , so it does not share any factors with $10^i$ . Hence, dividing both sides by $10^i$ gives us

$(10^{j-i} - 1)/9 \equiv 0 \pmod p.$

Look! A repunit divisible by $p$ !

What’s the “big idea” here? We have some sort of iterative process and want to show that some particular thing must eventually happen. If there are only a finite number of possibilities, by the Pigeonhole Principle we know the process must eventually repeat. So we look at the places where it repeats, and use those to create the thing we wanted to show.

Proof 2: Fermat’s Little Theorem states that for any number $a$ which is not divisible by some prime $p$ ,

$a^{p-1} - 1 \equiv 0 \pmod p.$

So we can apply this directly to conclude that $(10^{p-1} - 1)/9$ is divisible by $p$ for any primes other than $2$ , $3$ , or $5$ (note: why not $3$ ?). In other words, such $p$ always divide the repunit with $p-1$ ones. To complete the proof we simply note that $111$ is divisible by $3$ .

This version is much shorter but of course requires you to know Fermat’s Little Theorem! And it doesn’t give as much insight unless you already have some insight into why Fermat’s Little Theorem is true. Perhaps I could explain a proof or two of Fermat’s Little Theorem in a future post if anyone is interested.

At the end of my last post I also posed some “follow-up” challenges. I’ll post solutions to those next time.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →