# Pure math: Order question

1. Feb 3, 2009

### ploppers

1. The problem statement, all variables and given/known data

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

2. Relevant 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)

3. 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 sence 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!!!