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 ones as . Suppose is a prime other than or , and consider the remainders when repunits are divided by . Since there are infinitely many repunits and only possible remainders, by the Pigeonhole Principle there must be some remainder which is repeated, that is, there must be two distinct numbers and (let’s say ) such that
Bringing over to the left-hand side and simplifying gives
Since we can factor out , giving
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 is neither nor , so it does not share any factors with . Hence, dividing both sides by gives us
Look! A repunit divisible by !
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 which is not divisible by some prime ,
So we can apply this directly to conclude that is divisible by for any primes other than , , or (note: why not ?). In other words, such always divide the repunit with ones. To complete the proof we simply note that is divisible by .
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.