More on repetend lengths

In a previous post, I noted that the length of the repetend (repeating portion of the decimal expansion) of a fraction with prime denominator p is at most p-1, and in fact divides p-1. I also said:

In fact, there’s even more that can be said about non-prime denominators, as well.

This was something of a cop-out, and today I’m going to correct that! In general, suppose the denominator d can be factored as

$\displaystyle d = p_1^{a_1} p_2^{a_2} \dots p_n^{a_n},$

that is, d can be factored as the product of the prime $p_1$ to the $a_1$ power, the prime $p_2$ to the $a_2$ power, and so on. (For example, $12 = 2^2 \cdot 3^1$ .) Then it turns out that the length of the repetend of any fraction with denominator d will be a divisor of

$\displaystyle \prod_{i=1}^n p_i^{a_i - 1} (p_i - 1).$

(The $\Pi$ denotes a product; you can read about the notation here if you haven’t seen it before.) When d is prime, we can see that this just reduces to d-1 as we would expect. For each additional prime p in the factorization, we multiply by p-1; for each additional power of a prime p beyond the first, we multiply by p.

So, for example, the repetend length for fractions with denominator 221 = 13*17 should evenly divide $(13-1)(17-1) = 192$ ; and indeed, the repetend length of 1/221 is 48. As another example, the repetend length of $1/(11^3 \cdot 13) = 1/17303$ is 726, which indeed divides $11^2(11 - 1) (13 - 1) = 14520$ .

You may wonder how I know this. Well, asking for the repetend length of a fraction with denominator d amounts to asking for the smallest power of 10 whose remainder, when divided by d, is 1. Another way to say this is that we want to know the order of the element 10 in the group $U(d)$ (the group of positive integers less than and relatively prime to d under multiplication). By Lagrange’s Theorem, the order of any element of a group divides the order of the group; so the question becomes, what is the order of $U(d)$ ? The answer, as explained e.g. on p. 155 of Contemporary Abstract Algebra by Joseph Gallian (Houghton Mifflin, 2002), is the above formula.

Now, maybe that went way over your head. It certainly did if you’ve never studied any group theory. But I don’t know a simpler way to explain it! Perhaps there is a better way, and if you know of one, I’d love to hear about it in the comments. Nonetheless, this is a great example of a simple question that quickly leads into some very deep structure.

You may also wonder how on earth I know that the repetend length of 1/17303 is 726! No, I didn’t sit there and do long division; of course, I wrote a computer program. Perhaps I will post it soon.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

6 Responses to More on repetend lengths

Joshua T Corbin says:

January 28, 2009 at 6:25 pm

Here’s a great paper on what’s going on with those groups: http://www.muskingum.edu/~rdaquila/m495/art/Remainder%20Wheels-Brenton.pdf
Brent says:

January 29, 2009 at 4:46 pm

Very cool, thanks Joshua!
Pingback: Welcome to Carnival of Mathematics 48 = 6!!! « Concrete Nonsense
Jonathan says:

February 1, 2009 at 9:36 pm

Thanks,

that fills in a gap for me (I knew the ‘no longer than’ part only)
Joshua Zucker says:

May 5, 2011 at 1:48 am

I think I have an explanation that doesn’t require Lagrange’s theorem, and maybe is actually a proof of, well, not quite that theorem, but at least Fermat’s Little Theorem and Euler’s generalization.

Mod m, where m is relatively prime to 10, you know that 10 and all its powers will be relatively prime to m. So, starting with 10, look at the residues mod m of its powers. Eventually this is going to repeat. Now you have one “cycle”.

Maybe this cycle has covered everything relatively prime to m, in which case we’re done. If not, pick another number k relatively prime to m and start multiplying it repeatedly by 10.

So now we have 1, 10, …, 10^n and then k, 10k, …, 10^n k. We definitely have 10^n k leaving remainder k, and because of the relative primetude of these guys, I think we can show that no earlier term can equal k.

Now either we’re done, or find another number relatively prime to m and start multiplying it by 10. And so on.

Ultimately we have partitioned all the numbers relatively prime to m into some number of sets with n elements each (since 10^n = 1 mod m), so n must be a divisor of m.

I guess this amounts to recapitulating the proof of Lagrange’s theorem, so maybe it’s not really anything new, but it seems like this argument could be made accessible to kids without them knowing any group theory.

It looks like the second page of http://www.ams.org/notices/201102/rtx110200302p.pdf has a reference to a 1929 article that must have done something fairly similar to what I’m describing here.
- Brent says:
  
  May 6, 2011 at 10:38 am
  
  Ah, excellent, I like it! One nitpick: a priori it’s not obvious that 1, 10, …, 10^n should come back to 1 (as opposed to repeating some other term in the sequence). Of course it’s true, but it requires an argument, namely, that if 10^j === 10^k (mod m) then we can divide out by 10^j (since 10 and m are relatively prime) to conclude that 1 === 10^(k-j) (mod m), so the sequence in fact starts repeating (with 1) at n = k-j.
  
  One thing that the proof relies on that would need to be explained is why you can divide both sides of a modular equation by something relatively prime to the modulus, but that’s not too hard.
  
  Hmm… maybe I will write this up in a post or two!

Comments are closed.