1. Not finding help here? Sign up for a free 30min 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!

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!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proof Two Primitive Root Conditions Are Equivalent
  1. Primitive roots? (Replies: 9)

  2. Primitive roots (Replies: 1)

  3. Primitive root (Replies: 1)

Loading...