aruba
|
|
response 76 of 81:
| 
Jun 19 19:15 UTC 2002 |
There's an interesting application to repeating decimals. (Try this if you
really want to amaze people at parties - I've tried it - it works!)
You can generalize the fact that 1, 2, ..., p-1 form a multiplicative group
for any prime p to say that for any integer n, the positive integers which
are less than n and relatively prime to n form a group (mod n). The size
of that group is called phi(n), the "Euler phi function". For instance,
n numbers m < n with gcd(m,n) = 1 phi(n)
- ------------------------------- ------
2 1 1
3 1,2 2
4 1,3 2
5 1,2,3,4 4
8 1,3,5,7 4
9 1,2,4,5,7,8 6
12 1,5,7,11 4
18 1,5,7,11,13,17 6
21 1,2,4,5,8,10,11,13,16,17,19,20 12
60 1,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59 16
Question: how long is the repeating decimal for 1/n? Well, of course, it
goes on forever, but what I mean is, how many digits repeat? For
instance, I'll say that:
length(.111111 ...) = 1
length(.373737 ...) = 2
length(.024024 ...) = 3,
etc. We've all seen this method of writing a repeating decimal as a
fraction:
X = .579579579...
1000X = 579.579579...
----- ------------- (subtract top from bottom)
999X = 579
==> X = 579/999.
More generally, if the decimal representation of X is a string S of k
digits repeated, then X = S/(10^k-1).
So suppose you're going the other direction; you know X=1/n (for the
moment assume n is relatively prime to 10), and you want to know
the length k of its repeating decimal. Well, k will be the smallest
number such that you can write 1/n as S/(10^k-1), for some S. But that
implies that S*n = 10^k-1, so actually k is the smallest integer such that
n divides 10^k-1, i.e., k is "the order of 10 (mod n)".
Now 10 is a member of the group above, so we know that its order must
divide the order of the group, namely, phi(n). So:
/---------------------------------------------------------------------\
| If n is relatively prime to 10 and k is the length of the repeating |
| decimal for 1/n, then k divides phi(n). |
\---------------------------------------------------------------------/
There's actually a pretty simple way of calculating phi, if you know the
prime factorization of n. If n = p1^k1 * p2^k2 *** pr^kr, then
phi(n) = n(1 - 1/p1)(1 - 1/p2)...(1-1/pr).
So, for instance, the prime factors of 21 are 3 and 7, so
phi(21) = 21 * (2/3) * (6/7) = 12.
That means that the length of the repeating decimal for 1/21 is a factor
of 12 - i.e., 1, 2, 3, 4, 6, or 12.
(In actuality, the answer is 6: 1/21 = .047619 repeating).
This is as far as I've ever been able to take the analysis; maybe someone
can take it farther. (It's not hard to dispense with the case where n has
some facors in common with 10; basically, you throw out those factors
before finding phi(n)).
Note also that 10 hardly appeared in the answer; you could replace it by
any base b.
|