Fun with repunit divisors

Posted on November 11, 2011 by Brent

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 1111\dots 111, 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:

\begin{array}{rcl} 11 & = & 11\\ 111 & = & 3 \times 37\\ 1111 & = & 11 \times 101\\ 11111 & = & 41 \times 271\\ 111111 & = & 3 \times 7 \times 11 \times 13 \times 37\\ 1111111 & = & 239 \times 4649\\ 11111111 & = & 11 \times 73 \times 101 \times 137\\ 111111111 & = & 3 \times 3 \times 37 \times 333667\\ 1111111111 & = & 11 \times 41 \times 271 \times 9091\\ 11111111111 & = & 21649 \times 513239\\ 111111111111 & = & 3 \times 7 \times 11 \times 13 \times 37 \times 101 \times 9901\\ 1111111111111 & = & 53 \times 79 \times 265371653\\ 11111111111111 & = & 11 \times 239 \times 4649 \times 909091\\ 111111111111111 & = & 3 \times 31 \times 37 \times 41 \times 271 \times 2906161\\ 1111111111111111 & = & 11 \times 17 \times 73 \times 101 \times 137 \times 5882353\\ 11111111111111111 & = & 2071723 \times 5363222357\\ 111111111111111111 & = & 3 \times 3 \times 7 \times 11 \times 13 \times 19 \times 37 \times 52579 \times 333667\\ 1111111111111111111 & = & 1111111111111111111\\ 11111111111111111111 & = & 11 \times 41 \times 101 \times 271 \times 3541 \times 9091 \times 27961 \end{array}

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:

  1. Compute a repunit which is divisible by 2011 (you’ll probably want to use a computer!).
  2. Prove that every prime other than 2 or 5 is actually a divisor of infinitely many repunits.
  3. Prove that every integer which is not divisible by 2 or 5 is a divisor of some repunit.
  4. Generalize all of the above to repunits in bases other than 10.
  5. 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!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, challenges, modular arithmetic, number theory, primes and tagged , , . Bookmark the permalink.

16 Responses to Fun with repunit divisors

  2. John Baker says:
    November 11, 2011 at 1:31 pm

    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:
    http://www.jsoftware.com/jwiki/FrontPage

    • Brent says:
      November 11, 2011 at 5:00 pm

      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).

  3. Matt Gardner Spencer says:
    November 11, 2011 at 10:28 pm

    ** (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

    • Brent says:
      November 12, 2011 at 10:47 pm

      Ah, nifty. I have some conjectures from a few minutes of computational fiddling but haven’t sat down to prove anything yet…

  4. Fergal Daly says:
    November 12, 2011 at 7:48 pm

    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?

    • Brent says:
      November 12, 2011 at 10:46 pm

      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?

      • Fergal Daly says:
        November 13, 2011 at 1:24 am

        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.

        • Fergal Daly says:
          November 13, 2011 at 1:30 am

          Actually, the proof works just fine for p < 10.

        • Brent says:
          November 13, 2011 at 1:55 am

          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.

          • Fergal Daly says:
            November 13, 2011 at 2:06 am

            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.

  5. David Radcliffe says:
    November 13, 2011 at 1:40 am

    It follows from Fermat’s Little Theorem that (10^{2010} - 1)/9 is divisible by 2011, but you would probably want to use a computer to find the smallest repunit that is divisible by 2011.

  6. Pingback: Fun with repunit divisors: proofs | The Math Less Traveled

  7. Pingback: Fun with repunit divisors: more solutions | The Math Less Traveled

  8. Pingback: NO SUCH LUCK or Numerology for Idiots « Mathspig Blog

Comments are closed.