Recurring decimals in prime fractions

[Oxymoron]

When I write out the decimal expansion of 1/p where p is a prime, it is always a recurring decimal with a period per(p). I was thinking why inverting a prime number should always give a recurring decimal but could not think of a reason other than it has to be something to do with our base 10 system of counting.

Some prime reciprocals, such as 1/7, 1/17, and 1/19 have periods which is one less that the prime. That is, per(p) = p-1 for some primes. And in fact, for all primes p, per(1/p)\,|\,(p-1). These are all interesting but there is something which I can't seem to explain.

Take the prime 11. Then the period of 1/11 is 2. Take some other prime p. Then

per\left(\frac{1}{11}\times\frac{1}{7}\right) = 2per\left(\frac{1}{p}\right)

so long as p < 31.

After looking at 1/11, I started looking at other prime reciprocals, hoping to find other relationships between the periods of 1/p, 1/q and 1/pq. Unfortunately, the only thing I could find was that

per\left(\frac{1}{p}\times\frac{1}{q}\right) = \infty

whenever p=q and the period of 1/p is odd.

I was hoping for a nice clean relationship between 1/p,1/q, and 1/pq but I could not find one at all. So I tried checking the web and again, no one seems to have found any relationships. So I came here. If anyone has seen, or done any work on comparing periods of different prime reciprocals, could you please share your knowledge.

Cheers.

 

[shmoe]

Some prime reciprocals, such as 1/7, 1/17, and 1/19 have periods which is one less that the prime. That is, per(p) = p-1 for some primes. And in fact, for all primes p, per(1/p)\,|\,(p-1). These are all interesting but there is something which I can't seem to explain.

These, and the relation you want for 1/pq, can be explained by the relation between the period of 1/n and the order of 10 mod n (you're interested in the case gcd(10,n)=1 here, though the other case is worth looking at).

Take the prime 11. Then the period of 1/11 is 2. Take some other prime p. Then

per\left(\frac{1}{11}\times\frac{1}{7}\right) = 2per\left(\frac{1}{p}\right)

so long as p < 31.

This isn't true, the period of 1/7 is 6, the period of 1/77 is also 6.

per\left(\frac{1}{p}\times\frac{1}{q}\right) = \infty

infinity? This can't be true either, it will always be finite as 1/pq is a rational number, and hence its decimal either terminates or repeats.

 

[Oxymoron]

Posted by Shmoe

These, and the relation you want for 1/pq, can be explained by the relation between the period of 1/n and the order of 10 mod n (you're interested in the case gcd(10,n)=1 here, though the other case is worth looking at).

What is n here? Does n = pq?

 

[shmoe]

What is n here? Does n = pq?

Sure, if you like. It doesn't have to be the product of 2 primes though, there's a nice relation between the period of a number n with gcd(10,n)=1 and the order of 10 mod n.

 

[Oxymoron]

Posted by Shmoe

Sure, if you like. It doesn't have to be the product of 2 primes though, there's a nice relation between the period of a number n with gcd(10,n)=1 and the order of 10 mod n.

That got me thinking...

The period of 1/p is the order of 10(mod p) right? so we have a congruence relation:

10^r \equiv 1(\mod p)

The period of 1/q is the order of 10(mod q). So:

10^s \equiv 1(\mod q)

And the period of 1/pq is the order of 10(mod pq). So:

10^t \equiv 1(\mod pq)

...

 

[Oxymoron]

No matter what prime p we take, p is always relatively prime to 10 (since p has no divisors anyway). Take a prime. Then suppose that p divides 10^r-1, that is, nm = 10^r - 1 for some integer 1\geq m < 10^r. Then

\frac{1}{n} = \frac{m}{10^r-1} = m(10^{-r} + 10^{-2r} + \dots)

If our integer m = a+0 + 10a_1 + 10^2a_2 + \dots 10^{r-2}a_{r-2} + 10^{r-1}a_{r-1} for decimal digits a_0,\dots,a_{r-1}, then the decimal expansion of 1/p will be

\frac{1}{p} = 0.a_{r-1}a_{r-2}\dots a_1a_0a_{d-1}a_{d-2}\dots a_1a_0\dots

which will repeat with a period that will always divide r.

Then the period of 1/p is the smallest r such that p divides 10^r-1. In other words, the period of 1/p is the smallest d such that

10^r \equiv 1(\mod p)

But this is the definition of \mbox{ord}_p(10).

So the period of 1/p is the order of 10(mod p).

 

[Oxymoron]

Which should mean that

\mbox{per}\left(\frac{1}{pq}\right) = \mbox{ord}_{p+q}(10)

 

[shmoe]

Which should mean that

\mbox{per}\left(\frac{1}{pq}\right) = \mbox{ord}_{p+q}(10)

Should be the order of 10 mod pq, not p+q. Now do you know how to find the oder of 10 mod pq from the orders mod p and mod q?

 

[Oxymoron]

Posted by Shmoe

Should be the order of 10 mod pq, not p+q. Now do you know how to find the oder of 10 mod pq from the orders mod p and mod q?

Of course, pq, nor p+q, I don't know why I wrote that.

I think I may know, although I kind of jumped at that conclusion without properly running through it.

\mbox{per}(1/p)\times\mbox{per}(1/q)

is the order of 10(mod pq). If you let n = pq (although I may now understand what you mean by this, n can be any integer so long as it is relatively prime to 10?) then

\mbox{per}(1/p)\times\mbox{per}(1/q) = \mbox{per}(1/n)

which is equal to the order of 10(mod n) = 10(mod pq). Which is the same thing as

\mbox{per}(1/pq) = \mbox{ord}_{pq}(10)

 

[shmoe]

(although I may now understand what you mean by this, n can be any integer so long as it is relatively prime to 10?)

Yes. If it's not relatively prime, then it's a terminating decimal.

\mbox{per}(1/p)\times\mbox{per}(1/q) = \mbox{per}(1/n)

Remember th 1/7 and 1/11 example? The period of 1/11 was 2, the period of 1/7 was 6, the period of 1/77 was 6, so it's not the product of the periods.

Try a few more examples to see if you can spot a relationship. You might want to think in terms of the order of 10 mod p and q here. Specifically if r is the order of 10 mod p and 10^t=1 mod p then r divides t. Also, if 10^t=1 mod pq then 10^t=1 mod p.

 

[Oxymoron]

For example

1/7. Find \mbox{ord}_7(10)

10^2 \equiv 2(7)
10^3 \equiv 6(7)
10^4 \equiv 4(7)
10^5 \equiv 5(7)
10^6 \equiv 1(7)

and we have exhausted mod 7. So infact,

\mbox{ord}_7(10) = 6

p=17. Find \mbox{ord}_17(10).

10^2 \equiv 15(17)
10^4 = 15^2 \equiv (-2)^2 \equiv 4(17)
10^8 = 4^2 \equiv 16(17)

Thus we can see that \mbox{ord}_{17}(10) is not 1,2,4, or 8. But we must remember that \mbox{ord}_{17}(10) divides \phi(17) = 16. The divisors of 16 are 1,2,4,8, and 16. Therefore \mbox{ord}_{17}(10) = 16.

Now find \mbox{ord}_{7\cdot 17}(10)

\mbox{ord}_{7\cdot 17}(10) \Rightarrow 10^{rs} \equiv 1(7\cdot 17)

But is there a quicker way of doing this other than working them all out?

 

[shmoe]

Suppose the order of 10 mod 7*17 is t. Then 10^t=1 mod 7*17. So we have both:

10^t=1 mod 7
10^t=1 mod 17

What does this tell you about t compared to 6 and 16 (the orders of 10 mod 7 and 17).

 

[Oxymoron]

But surely t can't take on two values at the same time?

 

[Oxymoron]

So 7 divides t-1 and 17 divides t-1. So 6 divides t and 16 divides t. So t=48 works but t=48 = lcm(6,16).

 

[shmoe]

So 7 divides t-1 and 17 divides t-1.

Nope. You maybe mistyped?

So 6 divides t and 16 divides t.

Which shows lcm(6,16) divides t. You should also be able to show t divides lcm(6,16), then you'd have equality. Of course showing 10^48=1 mod 7*17 directly would work as well, but you can prove this lcm relation in general.

 

[Oxymoron]

Nope. You maybe mistyped?

Yeah, I meant to write

7 divides 10^t - 1 and 17 divides 10^t -1

=>

6 divides 10^t and 16 divides 10^t

which just comes from the definition of

10^t \equiv 1(\mod 7)

and

10^t \equiv 1(\mod 17)

 

[Oxymoron]

Which makes it that

\mbox{lcm}(6,16) \mbox{ divides } 10^t

 

[shmoe]

Yeah, I meant to write

7 divides 10^t - 1 and 17 divides 10^t -1

=>

6 divides 10^t and 16 divides 10^t

7 divides 10^t - 1 implies 6 divides t, not 10^t (as 6 is the order of 10 mod 7). Similiar for 16, which is why we have lcm(6,16) divides t.

 

[Oxymoron]

Ahah! of course! of course! (I was lucky getting the right answer from incorrect calculations).

So finally we have that if

\mbox{ord}_{pq}(10) = t

then

t = \mbox{lcm}(p-1,q-1)

 

[Oxymoron]

and since

\mbox{ord}_{pq}(10) = \mbox{per}(1/pq)

we have

\mbox{per}(1/pq) = \mbox{lcm}(p-1,q-1)

 

[Oxymoron]

What about

\mbox{per}\left(\frac{1}{p^2}\right)?

we have

10^t = 1(mod p^2)

=>

p^2 - 1 divides t

where t = \mbox{ord}_{p^2}(10)

 

[shmoe]

\mbox{per}(1/pq) = \mbox{lcm}(p-1,q-1)

This was luck again! It works for the p=7 and q=17 case, but what if p=7 and q=11?

 

[Oxymoron]

What!? How can it work for my random choice of prime numbers but not for another choice? Noooo!

 

[Oxymoron]

Maybe not all is lost...

 

[Oxymoron]

7 and 17 where peculiar because the period of 1/7 was 7-1, and the period of 1/17 was 17-1. So Ill take a stab in the dark an proclaim:

\mbox{per}(1/pq) = \mbox{lcm}(\mbox{per}(1/p),\mbox{per}(1/q))

 

[shmoe]

7 and 17 where peculiar because the period of 1/7 was 7-1, and the period of 1/17 was 17-1. So Ill take a stab in the dark an proclaim:

\mbox{per}(1/pq) = \mbox{lcm}(\mbox{per}(1/p),\mbox{per}(1/q))

Ding, ding, ding! We have a winner (note here the assumption that gcd(p,q)=1). The order of 10 being the lcm of the other orders is the easiest way to think about this, and the easiest way to prove it.

 

[Oxymoron]

Yay!



I also came up with something for the period of 1/p^2.

Let \mbox{ord}_{p^2}(10) = t

Then

10^t \equiv 1(\mod p^2)
=>
p^2\,|\,t-1
=>
p^2-1\,|\,t

Then p^2-1 divides t. But p^2-1 is always an even number for all primes p. So t is even, since t=\lambda(p^2-1) for some lambda.


But then the period 1/3*1/3 = 1/9 = 0.11111 has a period of 1 which is not even. Argh.

 

[shmoe]

The group of units mod p^2 has order phi(p^2)=p*(p-1). The order of 10 mod p^2 will divide this. Remember Euler's theorem?

 

[Oxymoron]

When I was working through the proof of the first one with you, it worked because when we did

10^t = 1(mod 7) => 7 | 10^t - 1 => (7-1) | t

and luckily (7-1) happened to be the period of 1/7.

But say we had 11...then

10^t = 1(mod 11) => 11 | 10^t - 1 => (11-1) | t

and now (11-1) is NOT the period of 11.

So if I had been working with say 3 and 11, I would not have discovered the lcm bit! This is why I can't work out the period of 1/p^2.

 

[Oxymoron]

So when I got to the step

10^t \equiv 1(\mod p)
10^t \equiv 1(\mod q)

=>

p\,|\,t-1
q\,|\,t-1

but now I can't simply say

p-1 | t => per(1/p) | t

because p-1 is the period of 1/p (like I did when p=7,q=11), because p-1 is NOT the period of arbitrary primes. So wha

 

[shmoe]

So when I got to the step

10^t \equiv 1(\mod p)
10^t \equiv 1(\mod q)

=>

p\,|\,t-1
q\,|\,t-1

You've typed this sort of implication enough times I'm getting concerned it's not a typo. 10^t=1 mod p does not in anyway mean p divides t-1. You do however know that the order of 10 mod p will divide t if 10^t=1 mod p. In other words, if you raise 10 to an exponent and get 1, then this exponent is a multiple of the order. You also know the order of 10 mod p will divide p-1, the order of the group of units mod p is just p-1 (in general it's phi(n)).

 

[Oxymoron]

Excellent. So I was lucky that the period of 1/7 equalled 7-1 AND phi(7) = 7-1. That was where I was getting confused.

So for 1/pq we could have written

per(1/pq) = lcm(phi(p),phi(q))

 

[shmoe]

Excellent. So I was lucky that the period of 1/7 equalled 7-1 AND phi(7) = 7-1. That was where I was getting confused.

So for 1/pq we could have written

per(1/pq) = lcm(phi(p),phi(q))

This isn't correct- it's the 'luck' mistake that you just mentioned. You don't necessarily have per(1/p) equal to phi(p). You know per(1/p) divides phi(p) since per(1/p) equals the order of 10 mod p, but that's all you can say.

 

[Oxymoron]

So to answer the question which was "what can we say about the period pf 1/pq?" is exactly that, we can only "say". There is no exact formula for it.

We can say the period of 1/p divides phi(p) and the period of 1/q divides phi(q) because the period of 1/p is the order of 10 mod p (and for q), like you just said. So we can say that the period of 1/pq is a divisor of phi(pq).

 

[shmoe]

Yes, but you can also say something about per(1/pq) in terms of per(1/p) and per(1/q), namely per(1/pq) = lcm(per(1/p),per(1/q))

 

[Oxymoron]

And with per(1/p^2) we can say that it too is a divisor of phi(p^2). Which, as you have already said, means that per(1/p^2) divides p*(p-1)

 

[Oxymoron]

Posted by Shmoe

Yes, but you can also say something about per(1/pq) in terms of per(1/p) and per(1/q), namely per(1/pq) = lcm(per(1/p),per(1/q))

I thought we came to the conclusion that this wasnt true. It was because per(1/7) happened to equal phi(7), and per(1/17) happened to equal phi(17). Now you are saying that it was correct.

 

[shmoe]

I thought we came to the conclusion that this wasnt true. It was because per(1/7) happened to equal phi(7), and per(1/17) happened to equal phi(17). Now you are saying that it was correct.

lcm(phi(p),phi(q)) and lcm(per(1/p),per(1/q)) are not always the same. Look back to posts 25/26.

 

[Oxymoron]

SUMMARY:

1. The period of 1/pq equals the order of 10 mod pq.
2. Let t=ord_(pq)(10).
3. By definition of order, we must have 10^t=1(mod pq).
4. This implies two linear congruences
a) 10^t = 1(mod p)
b) 10^t = 1(mod q)
5. We know that t divides ord_p(10) <=> 10^t=1(mod p)
6. We know that t divides ord_q(10) <=> 10^t=1(mod q)
7. We also know that ord_p(10) divides p-1 (or in other words phi(p)).
8. From 4a and 4b we know that if t divides two different numbers then it must divide their lowest common multiple. That is, t must divide lcm(ord_p(10),ord_q(10)).
9. Which means that t divides lcm(phi(p),phi(q)).

How does this look?

 

[Oxymoron]

It doesn't look right at all. t divides ord_p(10) does not mean that t divides phi(p). ...(or does it?)

 

[shmoe]

5. We know that t divides ord_p(10) <=> 10^t=1(mod p)
6. We know that t divides ord_q(10) <=> 10^t=1(mod q)

These are backwards.

ord_p(10) divides t<=> 10^t=1(mod p)

7. We also know that ord_p(10) divides p-1 (or in other words phi(p)).

This is true, but not necessary. You have a phi fixation.

8. From 4a and 4b we know that if t divides two different numbers then it must divide their lowest common multiple. That is, t must divide lcm(ord_p(10),ord_q(10)).

This is backwards. You'll have ord_p(10) and ord_q(10) dividing t, and hence so does their least common multiple.

In the direction you are trying to go, you need something like (4)=>(3), which follows when p and q are distinct primes (hence relatively prime). This will let you show the order of 10 mod pq divides the order of of 10 mod p and 10 mod q, so it divides their least common multiple.

9. Which means that t divides lcm(phi(p),phi(q)).

Again true, but saying t divides lcm(per(1/p),per(1/q)) is in general stronger.

 

[Oxymoron]

Thankyou Shmoe for all your help and patience. I believe I can now write a correct solution.

 

[bdeln]

**bump**

I'm working on a similar problem, ie, I need to find the period of 1/pq if (p,q) = (p,10) = (q,10) = 1.

If the period of 1/p is r and the period of 1/q is s, then

10^r \equiv 1 (p) \mbox{ and } 10^s \equiv 1 (q).

So, let t be the period of 1/pq, ie, 10^t \equiv 1 (pq), then 10^t \equiv 1 (p) \mbox{ and } 10^t \equiv 1 (q).

Now r|t and s|t (since if the order of a mod n is k and a^t \equiv 1 (n), then k|t). This implies that \textstyle \left. \frac{rs}{\mbox{gcd}(r,s)} \right| t \Rightarrow \mbox{lcm}(r,s)|t.

I just have to show that t|\mbox{lcm}(r,s) so I can say the period of 1/pq is exactly \mbox{lcm}(r,s) and I'm done (I think). I'm a bit stuck with this last bit though. Am I on the right track here or is there some other obvious way of going about this?

Thanks for any help.