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!

Cyclic group properties

  1. Oct 20, 2009 #1
    1. The problem statement, all variables and given/known data
    Zn={0,1,...,n-1}. show that an element k is a generator of Zn if and only if k and n are relatively prime.

    2. Relevant equations

    3. The attempt at a solution
    it makes sense but im having a hard time proving this.
  2. jcsd
  3. Oct 20, 2009 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So you need to do two parts:
    1) If k and n are relatively prime, k generates Zn. What do you need to prove to show this?

    2) If k generates Zn, then k and n are relatively coprime. This part is probably easier done by proof by contradiction
  4. Oct 20, 2009 #3
    well i understand i need to show both ways but to be honest, this is all i have:
    ==>if m is in {0,1,...,n-1} is a generator, its order is n. Also, its order must be n/(m,n). Thus, n=n/(m,n) which implies (m,n)=1.
    <== if (m,n)=1 then the order of m is n/(m,n)=n/1=n.
    therefore, m is a generator of Zn.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Cyclic group properties
  1. Cyclic groups (Replies: 3)

  2. Cyclic groups (Replies: 1)

  3. Cyclic group (Replies: 9)

  4. Cyclic groups (Replies: 3)

  5. Cyclic group (Replies: 1)