Recurring decimals in prime fractions

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