Repeating DecimalsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/