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: Proving no primitive root mod mn, where m&n prime

  1. Nov 5, 2011 #1
    1. The problem statement, all variables and given/known data
    if m, n are distinct odd primes, show that the set of units mod mn has no primitive root.

    2. Relevant equations

    [ hint: phi(mn) = (m-1)(n-1) so we can show for a, a unit mod mn, a((m-1)(n-1))/2 = 1
    and a [itex]\equiv[/itex] b mod mn iff a[itex]\equiv[/itex] b mod m and a [itex]\equiv[/itex] b mod n

    3. The attempt at a solution

    Not sure where to start with this one. Im thinking its fairly fundamental to understanding congruence classes and such, but the hint is throwing me off. In particular how can I show that for a unit a, a((m-1)(n-1))/2 = 1 ?

    after that, I know that a is a primitive root mod m if ord(a) = phi(m). this would give a(m-1)(n-1) = 1. If I could get to the point in the hint, then I would have a contradiction here and could conclude that there is no primitive root mod mn. So (assuming this is the correct approach) how can I get to a((m-1)(n-1))/2 = 1?
    Last edited: Nov 5, 2011
  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