Calculating Length of Repetend of ReciprocalsDate: 10/26/2004 at 08:02:48 From: Henry Subject: repetend in reciprocals of odd numbers greater than 5 Is there any way of finding out the number of digits in the period of a reciprocal without doing the long division for 1/n? I am not interested in the digits themselves, just in how many there are. For example, for 1/999983 the answer would be 999982. The length of the repetend (period) of the reciprocal can be used to determine whether the number is prime, although there are pseudoprimes. However, by changing the base number from 10 to another one, the pseudoprimes fail, while the real prime numbers don't. If we let 'd' be the length of the repetend, n modulus d will always be 1 for a prime number, regardless of the base used. Also, if 'd' is an even number, the d/2 remainder of 1/n will be always be equal to n-1 for a prime number. I'm not a student. I am a 67 year old retired computer programmer that loves numbers. Thanks. Date: 10/26/2004 at 10:18:00 From: Doctor Vogler Subject: Re: repetend in reciprocals of odd numbers greater than 5 Hi Henry, Thanks for writing to Dr. Math. We love numbers too. Since you speak of other bases, I will try to write my answer in greater generality, so I will assume that you want to write 1/n in base b. Now, if n divides b^k for some positive integer k, then 1/n will be a terminating decimal. (Do you see why?) For example, even though 2 and 5 are prime, 1/2 = 0.500000 1/5 = 0.200000. So 5 does not have 4 digits that repeat, only 0. Now, you *could* say that it repeats the 4 digits 0000. More on this anon. Now suppose that 1/n repeats. Let's suppose that it repeats d digits. That means that 1/n and (b^d)/n will eventually have all of the same digits. In other words, we can shift them both left by k digits, so that (b^k)(b^d)/n - (b^k)/n is an integer. That means that n divides the number (b^k) * (b^d - 1). In fact, if n divides that number, then the number of digits that 1/n will repeat will be a DIVISOR of d. And so we want to find the SMALLEST number d such that n divides (b^k) * (b^d - 1) for some integer k. Now I'm going to relate this to a different problem that you might be able to find solved already. Perhaps you know something about modular arithmetic. It is a fascinating and very useful technique. If the b^k factor weren't there, then finding the smallest number d such that n divides b^d - 1 would be the same thing as asking: What is the order of b mod n? There are algorithms and programs available that do exactly this. Instead of saying what they are and how to do it, I will refer you to a text book on number theory and modular arithmetic, or an algorithms book such as Henri Cohen's very useful "A Course in Computational Algebraic Number Theory," and I will refer you to his free math program on the internet, at http://pari.math.u-bordeaux.fr/ called Pari (written for UNIX, but there is also a Windows executable available in the Downloads section). It can do many things, and to find the order of b mod n, you just ask: znorder(Mod(b,n)). Getting back to our problem, we almost have a good answer to your question, except for that b^k factor that I just blithely ignored. If you try a few numbers, then you'll probably find that it usually doesn't matter. So we should ask: When does it matter? Or when does it not? The answer is really quite simple. If n and b are relatively prime, then n and b^k are relatively prime, so that n divides (b^k)(b^d - 1) if and only if n divides (b^d - 1). In other words, if n and b are relatively prime, then all we have to do is get the order of b mod n. And that's d! What happens if n and b have a common factor? Recall that I already stated: If n divides b^k for some integer k, then 1/n terminates. How do you know if n divides b^k for some k without trying every integer k? Well, you look at the factorization of n and b. If n has any prime divisors that appear in b, then you just throw them away! Or you look at the GCD of n and b (since it is easier to calculate a GCD than to factor a large number). If the GCD is g, then n divides (b^k)(b^d - 1) for some integer k if and only if n/g divides (b^k)(b^d - 1) for some (different) integer k. So you just keep dividing n by the GCD of n and b until n is relatively prime to b. Then you are reduced to the previous case, where n and b are relatively prime, and d is the order of b mod n. So let's try this: Try 1/2400 in decimal. First we factor 2400 and 10 2400 = 2^5 * 3 * 5^2 10 = 2 * 5. So we throw out the 2's and 5's and find that the length of the "repetend" (as you called it) of 1/2400 is the same as the length of the repetend of 1/3, which is 1. In fact, 1/2400 = 0.0004166666666666666.... Try 1/84 in decimal. Again, we factor 84 = 2^2 * 21. Note that we really don't need to factor 84 completely; we only need to pull out the factors of 2 and 5 (that also divide the base 10). So now we need the order of 10 mod 21. So we ask Pari, znorder(Mod(10,21)) and it tells us 6. In fact, 1/84 = 0.01190476190476190476190.... After these examples, let's go back to some of the rest of what you said: You said that if n is prime, then the repetend always has length n-1. First you need to make an exception: If n is prime, AND n does not divide the base b, then the repetend of 1/n always has length n-1. Now since n and b must be relatively prime, this is similar to Fermat's Little Theorem, which says that the order of b mod n, where n is prime and does not divide b, is a factor of n-1. Is it always n-1? It turns out that it is not. For example, the order of 10 mod 13 is 6 (not 12), and 1/13 = 0.07692307692307692307692307.... In fact, your idea for detecting primes comes down to the classic Fermat Pseudoprimality Test, which is to ask if b^(n-1) = 1 (mod n). If it isn't, then n isn't prime. But sometimes it holds even if n is not prime. I believe this is what you were saying about pseudoprimes. I hope this has been interesting and useful to you. If you have any more questions about this, please write back, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 10/28/2004 at 08:17:52 From: Henry Subject: repetend in reciprocals of odd numbers greater than 5 Dear Dr. Vogler: Thank you for your prompt answer. I learned a couple of things from it. However, I believe that I did not make myself completely clear on my question and thus your answer might have been a little different. I know that for some prime numbers (about 37%), the length of the repetend of 1/n is n-1. I believe they are called Long Primes. For all others, such as 13 (d=6, at base 10) the length of the repetend is less than n-1, but always a divisor of n-1. In other words, n mod d = 1. You said in your answer that there are algorithms that will calculate the value of d for 1/n at base b, which is exactly my question: How do we calculate the length (d) of the repetend of 1/n at base b, other than by doing the long division for 1/n? Can you supply me with a text description of one of the algorithms, with a couple of examples? It's good to know that the Pari program is available, but my interest is in the algorithms themselves (at least one of them). I thank you very much for your help. Henry Date: 10/28/2004 at 11:31:19 From: Doctor Vogler Subject: Re: repetend in reciprocals of odd numbers greater than 5 Hi Henry, All such algorithms are going to be couched in terms of If b and n are relatively prime, find the order of b mod n. So we address this question. First we have Fermat's Little Theorem, If n is prime and does not divide b, then b^(n-1) = 1 (mod n). And then there is Euler's very useful generalization to this theorem: If b and n are relatively prime, then b^phi(n) = 1 (mod n). The Euler phi function is simple to calculate if you know the prime factorization of n, for phi(p1^a1 * p2^a2 * ... * pk^ak) = (p1-1)*p1^(a1-1) * (p2-1)*p2^(a2-1) * ... * (pk-1)*pk^(ak-1) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk). From Euler's theorem, we know that the order of b mod n is a divisor of phi(n). Now if d is the order of b mod n, and d is not phi(n), then phi(n)/d is some divisor of phi(n) and has some prime factor p (which is, therefore, also a factor of phi(n)). That means that d divides phi(n)/p, so that b^(phi(n)/p) = 1 (mod n). Get ready; here is the algorithm: First we start with d = phi(n), and then we check if this is correct. We factorize d (if we can factorize n, then this is generally easy), and make a list of all of the prime factors of d. For each prime factor p of d, we check b^(d/p) (mod n). If we don't get 1 mod n, then we keep going. But if we *do* get 1 mod n, then that means that the order of b mod n divides d/p, so we divide d by p, and then we start over by factorizing d again (actually this is just removing the factor p from the factorization we already got) and trying all of the prime factors again. If none of the prime factors p give us b^(d/p) = 1 (mod n), then d must be the true order of b mod n. The last bit of this algorithm is knowing how to compute b^k (mod n). There are actually efficient ways to do this, and they go under the name of "modular exponentiation." The two most popular are sometimes called the left-right and the right-left algorithms, but they both do essentially the same thing. You start with b mod n, and then you square it and reduce mod n. Then you square that and reduce mod n. And you repeat to get a collection of numbers b (mod n) b^2 (mod n) b^4 (mod n) b^8 (mod n) b^16 (mod n) ... each of which is smaller than n. Then you multiply together the appropriate ones so that the exponents add up to k. In other words, you look at k in binary and for each "1" bit you multiply the corresponding power of b. You reduce after each multiplication, and that way the numbers never get any bigger than n^2. The two algorithms only differ by whether you start with the high bits of k or the low bits. The right-left algorithm is a little simpler. Is that enough information to find the order you want? I'll do an example for you. Let's find the length of the repetend of 1/81 in decimal. So b=10 and n=81. So first we factorize n 81 = 3^4 and take d = phi(n) d = 2 * 3^3 = 54. So then the prime factors of d are 2 and 3. We start with p=2 and check 10^(d/p) = 10^27 (mod 81) = (10^16 * 10^8 * 10^2 * 10) (mod 81) = (64 * 73 * 19 * 10) (mod 81) = 1 (mod 81), so we divide d by 2 and get d = 3^3 = 27. Now the only prime factor of d is 3, so we take p=3 and check 10^(d/p) = 10^9 (mod 81) = (10^8 * 10) (mod 81) = (73 * 10) (mod 81) = 1 (mod 81), so we divide d by 3 and get d = 3^2 = 9. Again, we take p=3 and check 10^(d/p) = 10^3 (mod 81) = (10^2 * 10) (mod 81) = (19 * 10) (mod 81) = 28 (mod 81), which is not 1, and we have checked all of the prime factors of d, so the order of 10 mod 81 is d=9. And, indeed, 1/81 = 0.012345679012345679012345679012345679.... - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 10/28/2004 at 16:45:26 From: Henry Subject: repetend in reciprocals of odd numbers greater than 5 Hello again Doctor Vogler, Thanks again for your prompt and informative reply. You say that the Euler phi function is simple to calculate if we know the prime factorization of n. What do we do, if we not only don't know the prime factorization of n (or if n is a prime number), but if the reason why we want to know d is to use it to determine whether n is prime or not, and if not prime, to use it to find at least one of its factors. For example, the d of 91 at base 10 is 6. Since 91 mod 6 = 1, we don't know whether 91 is prime or not. Also, since the 3rd remainder of 1/91 (the d/2 remainder) is 90 or n-1, we still don't know if 91 is prime or not. However, 6+1 (7) is a factor of 91. So, by checking whether d+1 happens to be a factor of n, we find that for 91, it is, and thus 91 is not prime. Another example, the d of 21 at base 10 is also 6. Since 21 mod 6 is not 1, we know that 21 is not prime. However, we can go further and find one of its factors: d+1 (7). I have a feeling that there is no answer to my question now that I have defined it and its purpose in more detail. But, I hope that I am wrong. Please let me know. Thank you very much for your time and your patience. Date: 10/28/2004 at 17:31:46 From: Doctor Vogler Subject: Re: repetend in reciprocals of odd numbers greater than 5 Henry, I'm sorry to tell you that, unless you can come up with a really clever way of answering your questions that is completely different from how I did, then this is a terrible and extremely inefficient method to factorize n or to tell if n is prime. You're much better off using factorization algorithms (like the Pollard p-1 algorithm) and primality tests to accomplish this. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 10/28/2004 at 20:20:20 From: Henry Subject: Thank you (repetend in reciprocals of odd numbers greater than 5) Hi Doctor Vogler, I was afraid of that. I hope I didn't get you upset. You have been very informative, patient and kind with me. Thanks again for your help. You gave me a lot of good information. Best wishes. Henry Date: 10/29/2004 at 16:54:15 From: Doctor Vogler Subject: Re: Thank you (repetend in reciprocals of odd numbers greater than 5) I'm not upset. I suppose I should back away from my statement one step, however, and repeat what I said in my first email: Your idea for detecting primes comes down to the classic Fermat Pseudoprimality Test, which is to ask if b^(n-1) = 1 (mod n). If it isn't, then n isn't prime. But sometimes it holds even if n is not prime. I believe this is what you were saying about pseudoprimes. This is the most that you can get out of the repetend length technique unless you have a completely different way of computing that length. And long division is much, MUCH slower than factoring n. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/