In honor of today’s date (11/11/11), here’s a fun little problem (and some follow-up problems) I’ve seen posed in a few places (for example, here is a very similar problem). If I recall correctly, it was also a problem on a midterm for my number theory course in college. It’s a lovely little problem with an equally lovely solution—once you understand the solution you’ll start to see many other situations where a similar “technique” can be applied.
A number of the form , with any number of repeated ones, is called a (base-10) repunit. 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.
For example, here are the prime factorizations of the repunits up to length 20:
It’s clear that no repunit is divisible by 2 or 5 (why?), but at first sight it may seem unlikely that all the other primes are divisors of some repunit! There doesn’t seem to be a lot of rhyme or reason in the above list of factorizations.
The above problem is really the heart of the matter, but once you solve that, here are some fun follow-up problems:
- Compute a repunit which is divisible by 2011 (you’ll probably want to use a computer!).
- Prove that every prime other than 2 or 5 is actually a divisor of infinitely many repunits.
- Prove that every integer which is not divisible by 2 or 5 is a divisor of some repunit.
- Generalize all of the above to repunits in bases other than 10.
- What’s so special about repunits here? Can you generalize to other sorts of numbers?
I’ll post some solutions in a few days. Happy 11/11/11!