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: Proof Two Primitive Root Conditions Are Equivalent

  1. Mar 30, 2010 #1
    1. The problem statement, all variables and given/known data
    Let n be a nonzero integer and let a be an integer with gcd(a, n) = 1. We have two equivalent conditions which characterize primitive roots:
    (i) a is primitive modulo n if the order of a is [tex]\phi[/tex](n).
    (ii) a is primitive modulo n if for every element b with gcd(b, n) = 1 we have b [tex]\equiv[/tex] a[tex]^{j}[/tex] mod n for some nonnegative integer j.
    Write out the complete proof that condition (i) implies condition (ii). To do this, show first that the integers a[tex]^{0}[/tex], a[tex]^{1}[/tex],..., a[tex]^{\phi(n)-1}[/tex] must lie in distinct congruence classes modulo n. Then explain why this implies condition (ii).

    2. The attempt at a solution
    I'm trying to figure out how to do the first part of showing that a[tex]^{0}[/tex], a[tex]^{1}[/tex],..., a[tex]^{\phi(n)-1}[/tex] must lie in distinct congruence classes modulo n. I realize that because the numbers are relatively prime has to do something with it. How is the a number taken to a power related to a number it's relatively prime to? I don't necessarily even want the full answer for the question, just more a push in the right direction. I guess of course the full answer wouldn't be bad either though. Maybe with spoiler tags around it would be good? Thanks!
     
  2. jcsd
  3. Mar 30, 2010 #2
    If the order of a is k=[tex]\phi[/tex](n), {a[tex]^{i}[/tex] | i=1,2,..,k} is a reduced residue system mod n. If gcd(b, n) = 1 , b is congruent to some element in the
    reduced residue system mod n & hence to a power of a.
     
  4. Mar 31, 2010 #3
    Why? Thanks!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook