(adsbygoogle = window.adsbygoogle || []).push({}); 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!!!

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Pure math: Order question

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

**Physics Forums | Science Articles, Homework Help, Discussion**