Are Relatively Prime Elements Generators of Cyclic Groups?

[halvizo1031]

Homework Statement

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.

Homework Equations

The Attempt at a Solution

it makes sense but I am having a hard time proving this.

 

[Office_Shredder]

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

2) If k generates Z_n, then k and n are relatively coprime. This part is probably easier done by proof by contradiction

 

[halvizo1031]

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

2) If k generates Z_n, then k and n are relatively coprime. This part is probably easier done by proof by contradiction

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.