About This Site
Powers and Fractions
Notes About Squares
Repeat Length Again
Intrinsic Nature of Primes
> Other Topics
Other Topics (2)
Two Kinds of Odd
RepunitsA repunit, or repeated unit, is a number consisting entirely of 1s. I don't like the name, but it seems to be standard, so I guess I'm stuck with it. Anyway, I've never been very familiar with repunits, but they've been turning up a lot recently, and I keep forgetting which ones have which factors, so just for reference I thought I'd make a table.
There are some interesting patterns in there, but before I can explain them I'll need to remind you of a couple of things. First of all, when I was talking about fractions in base 2, I observed that repunits of composite length have nice factorizations that are really factorizations of polynomials, and suggested that it would be handy to have a digit that represents -1. Then, when I was talking about divisibility in other bases, I started using the hash mark as such a digit not to be confused with the sharp sign from Sharps and Flats.
Knowing all that, we can break the repunits into irreducible polynomial factors without even specifying what the base is!
The irreducible polynomial factors may break down further in particular bases; here's what happens in bases 10 and 2. (I've converted the base 2 results into base 10, hope that's not too confusing. For example, 111 in base 2 is the prime number 7.)
Each repunit contains exactly one new irreducible polynomial I'm not sure why that's true, but it is, and I've numbered the rows accordingly in the table.
Now I can explain the main pattern in the original table. Let's call the repunit of length n Rn, and the associated irreducible polynomial Pn. If n is divisible by some number m, then Rn is divisible by Rm because there's a nice factorization; and Rm in turn is divisible by Pm, by definition. So, the numbers that are factors of Pm in some base will be factors of Rn whenever n is a multiple of m.
Actually, that's not quite true it fails for m = 1, because Rn is never divisible by P1. And where'd that polynomial P1 come from, anyway?! Well, I was planning ahead. Suppose we define one more set of polynomials by the rule Bn = Rn ื P1; then Bn, unlike Rn, really is divisible by Pm whenever n is divisible by m; and in fact Bn is equal to the product of all such Pm. That may sound complicated, but the polynomials Bn are actually extremely simple. For example,
B5 = R5 ื P1 = (b4 + b3 + b2 + b + 1)(b - 1) = b5 - 1.
The same cancellation happens every time, so that Bn = bn - 1 for all n.
Now, the roots of Bn are roots of unity, and roots of unity lie on the unit circle in the complex plane, so when we divide Bn into the parts Pm, we're dividing the circle which is roughly why the parts Pm are called cyclotomic polynomials. (The roots of the word are cyclo-, as in cyclic, and -tomic, as in atomic, indivisible.) Just for fun, here are some pictures of the roots of Pm.
See how for example P1, P2, P3, and P6 combine to cover the sixth roots of unity?
That was fun, but let's get back to the subject of patterns. I think we've said all there is to say about the main pattern, the pattern in how the repunits break down into cyclotomic polynomials, but there are also a few patterns in how the cyclotomic polynomials break down into factors in base 10.
Finally, let me go back and clarify a couple of things. First, the idea of numbers being polynomials over some unspecified base isn't restricted to repunits and cyclotomic polynomials. For example, the number 299 is never prime, because
299 = 2b2 + 9b + 9 = (b + 3)(2b + 3),
and the number 156 is always an intermediate, because
156 = b2 + 5b + 6 = (b + 2)(b + 3) = (b + 2)#.
(See also the discussion of small factors and carries in Multiplication.)
Second, in spite of the evidence in the table, cyclotomic polynomials don't always consist of evenly-spaced 1s or evenly-spaced alternating 1s and #s against a background of 0s. Some have repeating triplets,
some have other, stranger patterns,
and some even have other digits! According to an article on cyclotomic polynomials, the first one of those occurs at 105 (for the same reason as in Number Maze!), and here it is, with X being a digit that represents -2.
History and Other Stuff
Multiplication in Base 10
@ May (2006)