1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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: Pure math: Order question

  1. Feb 3, 2009 #1
    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!!!
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted