Does the Order of a Number Modulo pq Equal the LCM of the Orders Modulo p and q?

[ploppers]

Homework Statement

For any two integers m and n, let lcm(m; n) be the least common
multiple of m and n, i.e., the smallest non-negative integer d such that m|d
and n|d.
Prove that if p and q are distinct odd primes, and a is not divisible by
either p or q, we have
ordpq(a) = lcm(ordp(a); ordq(a)):
(Hint: Use the Chinese Remainder Theorem.)

Homework Equations

Congruency equations:
- a^k " 1 (mod m) iff ordm(a)|k
- a = bq + r (division algorithm)
- Chinese remainder theorem (not exactly sure how to decribe this, but I think it's only useful in the fact that we can combine p and q into pq since they are coprime)

The Attempt at a Solution

I denoted k and r as ordp(a) and ordq(a). This means
a^k " 1 (mod p) and a^r " 1 (mod q)
since p and q are coprime, we can use the chinese remainder theorem and say that a solution exists in the form a^y = 1 (mod pq).

I wrote them out in division algorithm form and tried to find the y from the system, but was unsuccessful. I don't know how to relate the lcm with the value of y either.

I do know that intuitively the answer makes some sort of sense because when k and r multiply together, it would create a value, a^kr, that would be modulus one for both q and p.

gcd(a^kr, q) = 1, gcd(a^kr, q) implies (?) gcd(a^kr, pq)?

again, I feel as if some of my assumptions may have been wrong, and I still do not know how to relate the LCM. THanks!

 

[mighty2000]

Thank you for sharing your thoughts and progress on this problem. It seems like you are on the right track in using the Chinese Remainder Theorem to combine the congruency equations for p and q. Here are some suggestions for how to proceed:

1. Start by writing out the division algorithm form for p and q, as you did. This will give you two sets of congruency equations:
- a^k " 1 (mod p) and a^r " 1 (mod q)
- a^k = p*q + m and a^r = p*q + n, where m and n are some integers

2. Use the fact that a^y = 1 (mod pq) to combine these equations. This means that a^y " 1 (mod p) and a^y " 1 (mod q). Use this to rewrite the congruency equations in terms of y:
- a^y " 1 (mod p) and a^y " 1 (mod q)
- a^y = p*q + m' and a^y = p*q + n', where m' and n' are some integers

3. Now, use the fact that p and q are distinct odd primes to show that y must be a multiple of both k and r. This is where the Chinese Remainder Theorem comes in handy. Since p and q are coprime, the solutions to a^y = 1 (mod p) and a^y = 1 (mod q) can be combined using the Chinese Remainder Theorem to give a solution for a^y = 1 (mod pq). This solution will be a multiple of both k and r, meaning that y must be a multiple of both k and r.

4. Finally, use the definition of ordpq(a) to show that ordpq(a) must be the least common multiple of k and r. This is because ordpq(a) is the smallest positive integer y such that a^y " 1 (mod pq), and we have just shown that y must be a multiple of both k and r.

I hope this helps. Good luck with your proof! Remember to be careful with the use of the Chinese Remainder Theorem and make sure to justify all steps in your proof.