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