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?
Best Answer
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.