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!
Here’s a somewhat similar problem.
Yes, that’s where I saw it! Thanks!
I enjoyed this post. Your “repunit” table can be generated by the following J sentences
repunits=. ‘x’ ,~&.> (2 + i. 19) #&.> ‘1’
repunits ,. q:@”. &.> repunits
For more about the J programming language see:
Neat, thanks! I do like J, I have actually written about it before. I actually generated the table using a bit of Haskell (I can show it if you’re interested but would have to reconstruct it, since I just did it as a one-off thing in an interpreter and didn’t save it).
** (you’ll probably want to use a computer!).**
I’ll say. It looks to me as if you need to go back to 1881 before you find a year which is a factor of 111…111 with fewer than 20 digits.
As another potentially neat question, what is the connection between repunits, primes and the sequence that can be found at http://oeis.org/A001913
Ah, nifty. I have some conjectures from a few minutes of computational fiddling but haven’t sat down to prove anything yet…
Re: Compute a repunit which is divisible by 2011 (you’ll probably want to use a computer!)
Is this not trivial from what you learn while proving that all the primes occur?
I’m not sure what your point is. Whether it is trivial probably depends on your definition of “trivial”, and on your method of proof, and on your facility with getting a computer to do the requisite computation. But even if it is trivial, so what?
By “trivial”, I mean that computation can be done by anyone who can count to 2011, not that I’m a genius or anything. So the “so what” is that there is definitely no computer needed.
Perhaps we have different proofs. In fact, my proof only works nicely for p > 10 (or whatever base you’re working in), which makes me think we do.
Actually, the proof works just fine for p < 10.
Well, I actually know two proofs: one leads to a very quick solution but requires the knowledge of some number theory. The other proof works on “first principles” but leads to a much longer computation. I was assuming most readers would find the second one.
I think I did it the number theory way but from first principles (which is not hard). Looking at the factorisations you list leads to that.
While I was doing it, I realised that the argument was familiar to me and then spotted the connection to the well known theorem.
It follows from Fermat’s Little Theorem that is divisible by 2011, but you would probably want to use a computer to find the smallest repunit that is divisible by 2011.
Pingback: Fun with repunit divisors: proofs | The Math Less Traveled
Pingback: Fun with repunit divisors: more solutions | The Math Less Traveled
Pingback: NO SUCH LUCK or Numerology for Idiots « Mathspig Blog