Recurring decimals in prime fractions

1. Apr 2, 2006

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 cant 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, noone 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.

Last edited: Apr 2, 2006
2. Apr 2, 2006

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).

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

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.

3. Apr 3, 2006

Oxymoron

What is n here? Does n = pq?

Last edited: Apr 3, 2006
4. Apr 3, 2006

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.

5. Apr 3, 2006

Oxymoron

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)$$

...

6. Apr 3, 2006

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).

Last edited: Apr 3, 2006
7. Apr 3, 2006

Oxymoron

Which should mean that

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

8. Apr 3, 2006

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?

9. Apr 3, 2006

Oxymoron

Of course, pq, nor p+q, I dont 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)$$

Last edited: Apr 3, 2006
10. Apr 3, 2006

shmoe

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

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.

11. Apr 3, 2006

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?

Last edited: Apr 3, 2006
12. Apr 3, 2006

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).

13. Apr 3, 2006

Oxymoron

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

14. Apr 3, 2006

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).

Last edited: Apr 3, 2006
15. Apr 3, 2006

shmoe

Nope. You maybe mistyped?

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.

16. Apr 3, 2006

Oxymoron

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)$$

17. Apr 3, 2006

Oxymoron

Which makes it that

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

18. Apr 3, 2006

shmoe

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.

19. Apr 3, 2006

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)$$

20. Apr 3, 2006

Oxymoron

and since

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

we have

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