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

Question

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?

Answer 1

One way to see it is that if $\lvert g\rvert =n$, then $\lvert g^k\rvert =n/(n,k)$.

Here I gave a proof.

Answer 2

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.

Answer 3

Number (2) is a consequence of the Bézout Identity, which states that any linear combination of two integers is a multiple of the greatest common divisors of those integers, as Marc has already stated. In particular, there exists a linear combination of them that is equal to the GCD

Thus given two integers $g$ and $n$, coprimes, there exists a linear combination $xg + yn$ such that $xg + yn = \gcd(g,n) = 1$.

This means that $xy + gn \equiv 1 (\text{mod } n)$. Reorganizing, we obtain

$$ xy \equiv 1 + (-y)n \equiv 1 (\text{mod } n) $$

An element $k \in \mathbb{Z}_n$ can then be written $kxg$, which is a multiple of $g$. So $g$ is a generator of $\mathbb{Z}_n$.

As to (1), as others have pointed out, you're correct.

Answer 4

It's easy to prove:

Say g is a generator, then if you increase g by k times is a kg. We know that i and (i+in)%n are same. So increasing it by n/gcd(g, n) yields the same.

Also the order of such generator should be n/gcd(n, g). So if it has to become a generator it has to have n/gcd(n, g) be equal to n. That means gcd(n, g)=1 => n and g are coprime.