Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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]
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook