Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Calculating Length of Repetend of Reciprocals

Date: 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/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/