Recurring decimals in prime fractions

**Oxymoron** · Apr2-06, 01:56 AM

When I write out the decimal expansion of

where

is a prime, it is always a recurring decimal with a period

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

for some primes. And in fact, for all primes

, $LaTeX Code: 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

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

so long as

.

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

$LaTeX Code: per\\left(\\frac{1}{p}\\times\\frac{1}{q}\\right) = \\infty$

whenever

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.

**shmoe** · Apr2-06, 09:02 AM

Originally Posted by Oxymoron

Some prime reciprocals, such as 1/7, 1/17, and 1/19 have periods which is one less that the prime. That is, for some primes. And in fact, for all primes , $LaTeX Code: per(1/p)\\,|\\,(p-1)$ . These are all interesting but there is something which I cant 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).

Originally Posted by Oxymoron

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

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

so long as .

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

Originally Posted by Oxymoron

$LaTeX Code: 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** · Apr3-06, 08:35 AM

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** · Apr3-06, 08:41 AM

Originally Posted by Oxymoron

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** · Apr3-06, 09:02 AM

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:

$LaTeX Code: 10^r \\equiv 1(\\mod p)$

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

$LaTeX Code: 10^s \\equiv 1(\\mod q)$

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

$LaTeX Code: 10^t \\equiv 1(\\mod pq)$

...

**Oxymoron** · Apr3-06, 09:21 AM

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

, that is,

for some integer $LaTeX Code: 1\\geq m < 10^r$ . Then

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

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

$LaTeX Code: \\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

$LaTeX Code: 10^r \\equiv 1(\\mod p)$

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

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

**Oxymoron** · Apr3-06, 09:25 AM

Which should mean that

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

**shmoe** · Apr3-06, 09:51 AM

Originally Posted by Oxymoron

Which should mean that

$LaTeX Code: \\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** · Apr3-06, 09:57 AM

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 dont know why I wrote that.

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

$LaTeX Code: \\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

$LaTeX Code: \\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

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

**shmoe** · Apr3-06, 10:06 AM

Originally Posted by Oxymoron

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

Originally Posted by Oxymoron

$LaTeX Code: \\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** · Apr3-06, 10:09 AM

For example

1/7. Find $LaTeX Code: \\mbox{ord}_7(10)$

$LaTeX Code: 10^2 \\equiv 2(7)$
$LaTeX Code: 10^3 \\equiv 6(7)$
$LaTeX Code: 10^4 \\equiv 4(7)$
$LaTeX Code: 10^5 \\equiv 5(7)$
$LaTeX Code: 10^6 \\equiv 1(7)$

and we have exhausted mod 7. So infact,

$LaTeX Code: \\mbox{ord}_7(10) = 6$

p=17. Find $LaTeX Code: \\mbox{ord}_17(10)$ .

$LaTeX Code: 10^2 \\equiv 15(17)$
$LaTeX Code: 10^4 = 15^2 \\equiv (-2)^2 \\equiv 4(17)$
$LaTeX Code: 10^8 = 4^2 \\equiv 16(17)$

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

Now find $LaTeX Code: \\mbox{ord}_{7\\cdot 17}(10)$

$LaTeX Code: \\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** · Apr3-06, 10:39 AM

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** · Apr3-06, 10:50 AM

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

**Oxymoron** · Apr3-06, 10:55 AM

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** · Apr3-06, 11:06 AM

Originally Posted by Oxymoron

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

Nope. You maybe mistyped?

Originally Posted by Oxymoron

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** · Apr3-06, 11:08 AM

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

$LaTeX Code: 10^t \\equiv 1(\\mod 7)$

and

$LaTeX Code: 10^t \\equiv 1(\\mod 17)$