1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recurring decimals in prime fractions

  1. Apr 2, 2006 #1
    When I write out the decimal expansion of [itex]1/p[/itex] where [itex]p[/itex] is a prime, it is always a recurring decimal with a period [itex]per(p)[/itex]. 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, [itex]per(p) = p-1[/itex] for some primes. And in fact, for all primes [itex]p[/itex], [itex]per(1/p)\,|\,(p-1)[/itex]. 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

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

    so long as [itex]p < 31[/itex].

    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

    [tex]per\left(\frac{1}{p}\times\frac{1}{q}\right) = \infty[/tex]

    whenever [itex]p=q[/itex] 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. jcsd
  3. Apr 2, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Apr 3, 2006 #3
    What is n here? Does n = pq?
     
    Last edited: Apr 3, 2006
  5. Apr 3, 2006 #4

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  6. Apr 3, 2006 #5
    That got me thinking...

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

    [tex]10^r \equiv 1(\mod p)[/tex]

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

    [tex]10^s \equiv 1(\mod q)[/tex]

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

    [tex]10^t \equiv 1(\mod pq)[/tex]

    ...
     
  7. Apr 3, 2006 #6
    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 [itex]10^r-1[/itex], that is, [itex]nm = 10^r - 1[/itex] for some integer [itex]1\geq m < 10^r[/itex]. Then

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

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

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

    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

    [tex]10^r \equiv 1(\mod p)[/tex]

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

    So the period of 1/p is the order of 10(mod p).
     
    Last edited: Apr 3, 2006
  8. Apr 3, 2006 #7
    Which should mean that

    [tex]\mbox{per}\left(\frac{1}{pq}\right) = \mbox{ord}_{p+q}(10)[/tex]
     
  9. Apr 3, 2006 #8

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  10. Apr 3, 2006 #9
    Of course, pq, nor p+q, I dont know why I wrote that. :confused:

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

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

    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

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

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

    [tex]\mbox{per}(1/pq) = \mbox{ord}_{pq}(10)[/tex]
     
    Last edited: Apr 3, 2006
  11. Apr 3, 2006 #10

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Apr 3, 2006 #11
    For example

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

    [tex]10^2 \equiv 2(7)[/tex]
    [tex]10^3 \equiv 6(7)[/tex]
    [tex]10^4 \equiv 4(7)[/tex]
    [tex]10^5 \equiv 5(7)[/tex]
    [tex]10^6 \equiv 1(7)[/tex]

    and we have exhausted mod 7. So infact,

    [tex]\mbox{ord}_7(10) = 6[/tex]

    p=17. Find [itex]\mbox{ord}_17(10)[/itex].

    [tex]10^2 \equiv 15(17)[/tex]
    [tex]10^4 = 15^2 \equiv (-2)^2 \equiv 4(17)[/tex]
    [tex]10^8 = 4^2 \equiv 16(17)[/tex]

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

    Now find [itex]\mbox{ord}_{7\cdot 17}(10)[/itex]

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

    But is there a quicker way of doing this other than working them all out?
     
    Last edited: Apr 3, 2006
  13. Apr 3, 2006 #12

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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).
     
  14. Apr 3, 2006 #13
    But surely t cant take on two values at the same time?
     
  15. Apr 3, 2006 #14
    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
  16. Apr 3, 2006 #15

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  17. Apr 3, 2006 #16
    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

    [tex]10^t \equiv 1(\mod 7)[/tex]

    and

    [tex]10^t \equiv 1(\mod 17)[/tex]
     
  18. Apr 3, 2006 #17
    Which makes it that

    [tex]\mbox{lcm}(6,16) \mbox{ divides } 10^t[/tex]
     
  19. Apr 3, 2006 #18

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  20. Apr 3, 2006 #19
    Ahah! of course! of course! (I was lucky getting the right answer from incorrect calculations).

    So finally we have that if

    [tex]\mbox{ord}_{pq}(10) = t[/tex]

    then

    [tex]t = \mbox{lcm}(p-1,q-1)[/tex]
     
  21. Apr 3, 2006 #20
    and since

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

    we have

    [tex]\mbox{per}(1/pq) = \mbox{lcm}(p-1,q-1)[/tex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Recurring decimals in prime fractions
  1. Decimal expansion (Replies: 1)

Loading...