# Questions about cyclic group which is generated by integer mod n.

In Integer and modular addition of Cyclic group:

For every positive integer n, the set of integers modulo n, again with the operation of addition, forms a finite cyclic group, the group Z/n. An element g is a generator of this group if g is relatively prime to n. Thus, the number of different generators is φ(n), where φ is the Euler totient function, the function that counts the number of numbers modulo n that are relatively prime to n. Every finite cyclic group is isomorphic to a group Z/n, where n is the order of the group.

I have following doubts about the above statements:
(1)

For every positive integer n, the set of integers modulo n, again with the operation of addition, forms a finite cyclic group, the group Z/n.

I am not a nitpicker, but think it should be "again with the operation of addition modulo n", right?

(2)

An element g is a generator of this group if g is relatively prime to n.

How can prove the the g and n must be coprime?

• Your "nitpick" is correct. – quasi Mar 2 '17 at 8:43
• If $g,n$ are not coprime, you can't generate $1$. Suppose $g,n$ have a common factor, $d$ say, where $d > 1$. Then any multiple of $g$ will be a multiple of $d$, and will still be a multiple of $d$ after you mod out by $n$, so you can't get $1$. – quasi Mar 2 '17 at 8:44
• @quasi Thanks for your comments? Forgive my greedy requirement, how can manifest if g and n are coprime, the g must be the generator? – Nan Xiao Mar 2 '17 at 9:24
• Suppose $g,n$ are coprime. Show that no two of the $n$ numbers $$0,g,2g,...,(n-1)g$$ are congruent mod $n$, hence they are still pairwise non-congruent when modded out by $n$. But then g generates all $n$ elements of $Z_n$. – quasi Mar 2 '17 at 9:27
• two of the n numbers are congruent mod n”? If I understand right, the n numbers mod n should generate 0, 1, ... n-1. Right? Thanks! – Nan Xiao Mar 2 '17 at 9:55

Given any number $u \in \Bbb Z$. Saying that $g$ is a generator$\mod n$ is equivalent to say $\exists x, y \in \Bbb Z: u = xg+yn$. But if $g$ and $n$ share a factor $d$ so does $u$, so values of $u$ which are not multiples of $d$ can't be reached.