Let form a cyclic group of order . Where is the principle primitive n-th root of unity. Show that also generates if and only if . (Hint: If that is and are relatively prime then 1 can be written as a linear combination of and .)

My attempt: Need to prove

(Contradiction) Assume generates , that is form the cyclic group . Suppose , Then I get stuck here and can't get my algebraic manipulations to lead me to a discernible contradiction.

For this implication I'm guessing we'll have to use the hint, but I'm not sure how it could prove useful. I used the hint to get: , for some integers . Then . So I have . But does that tell me that is a generator of , for some ?

Any suggestions would be appreciated. Thanks in advance.