Repeating Decimals

Date: 05/14/97 at 15:26:13
From: Tom Engvall
Subject: length of rep. sequence of decimals

When converting a fraction, such as 3/7, to decimals, a repeating 
sequence of digits appears in the result. 

(1) Can the length of this sequence ever exceed the value in the 
denominator? 

(2) If the length of this sequence is less than the denominator, is it 
always an integer factor of the denominator minus one? 

Example: 3/7 = .428571428571... , length = 6. 

Date: 05/14/97 at 16:10:37
From: Doctor Wilkinson
Subject: Re: length of rep. sequence of decimals

As it turns out, the length of the sequence that repeats cannot exceed 
the value of the denominator. If you think about the process of
converting the fraction m/n to a decimal, at each stage you divide by 
n and get a remainder. Since the remainders are all less than n, 
within n steps you must have the same remainder appearing twice, at 
which point the sequence of digits begins to repeat.

The length of this repeating sequence, however, is not always an 
integer factor of the denominator minus one.  For example, 1/70 
gives you a repeating sequence of length 6, but 6 is not a divisor 
of 70 - 1.  But there is a grain of truth there.  You may want to 
think about it some more.

-Doctor Wilkinson,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 05/14/97 at 16:33:58
From: Doctor Rob
Subject: Re: length of rep. sequence of decimals

This is a very good question, which leads into all sorts of 
interesting mathematics, part of a subject called number theory.

(1) No, it cannot. You can prove this yourself by doing long division
of the numerator by the denominator, and looking at the sequence of
remainders.  They are never zero unless the denominator is a power of 
2 times a power of 5 (when the decimal terminates), and they are all 
less than the denominator. There are D-1 possible values. As soon as 
one of these values repeats, so does its successor, and all the 
remaining ones, so the remainders in the repeating part are all 
different. Thus there cannot be more than D-1 of them.

(2) Not quite. If the denominator D is a prime number, it is always 
an integer factor of D-1. This is a corollary of Lagrange's Theorem 
from group theory. What you are asking is what the smallest power e 
of 10 might be such that D divides 10^e - 1 evenly. The set of 
integers between 1 and D-1 which have no common factor with D are 
closed under multiplication modulo D (multiply the integers, divide by 
D, and keep only the remainder). They form a group, and so Lagrange's 
Theorem applies. It says that the order (e in this case) of any group 
element (10 in this case) divides the order of the group (D-1 here).

If the denominator D is not prime, this probably isn't true, although
you can find examples where it still is.  In general, it is false.

  1/21 = 0.047619047619047619..., period 6, but 6 doesn't divide 20.
  1/27 = 0.037037037037037037..., period 3, but 3 doesn't divide 26.

If you guess that the period is somehow connected to the prime factors
of the denominator D, you are right. The connection is somewhat
complicated, however. It involves something called the Euler phi
function and the Carmichael lambda function.

Write D = p(1)^e(1)*p(2)^e(2)*...*p(k)^e(k) as the product of powers 
of distinct primes.  Then:

   phi(D) = D*(1-1/p(1))*(1-1/p(2))*...*(1-1/p(k))
          = p(1)^(e(1)-1)*(p(1)-1)*p(2)^(e(2)-1)*(p(2)-1)*...*
              p(k)^(e(k)-1)*(p(k)-1)

This is the number of positive whole numbers no greater than D having
no common factor with D. The set of these numbers is closed under
multiplication modulo D (as above), and in fact forms a group. Once
again Lagrange's Theorem tells us that the order of 10 (the period of
the decimal 1/D) divides the number of elements in the group, phi(D).

When D = 21 = 3*7, phi(D) = 2*6 = 12, so the period must divide 12.
When D = 27 = 3^3, phi(D) = 3^2*(3-1) = 18, so the period must 
divide 18.

This is true, but one can actually do better.  For odd integers, the
Carmichael lambda function is defined by:

   lambda(D) = L.C.M.[p(1)^(e(1)-1)*(p(1)-1), p(2)^(e(2)-1)*(p(2)-1), 
... p(k)^(e(k)-1)*(p(k)-1)]

Here L.C.M. means the Least Common Multiple, which you have met when
adding fractions, where it is called the Least Common Denominator.
It turns out that the period must divide lambda(D), which is often a
smaller divisor of phi(D).

When D = 21 = 3*7, lambda(D) = LCM[2, 6] = 6, so the period must 
divide 6, so we have done better.  When D = 27 = 3^3, lambda(D) = 
LCM[18] = 18 = phi(n), so we haven't done better.

For a really big example, when D = 3^2*7*11*13 = 9009, lambda(D) =
LCM[3*2, 6, 10, 12] = 60, so the period of 1/9009 must divide 60.

By the way, if the denominator is divisible by 2 or 5, to compute the
period just throw all those prime factors away, and deal with what is
left.  The period will remain the same.

Probably this was more than you ever wanted to know. If you are
interested, there is much more to learn here. An elementary book on
number theory would be a source of more information.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/