# 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. Commented Mar 2, 2017 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$. Commented Mar 2, 2017 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? Commented Mar 2, 2017 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$. Commented Mar 2, 2017 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! Commented Mar 2, 2017 at 9:55

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.

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.

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.

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.

• Is my proof wrong? Please let me know the mistake in my proof if you have downvoted my answer. Commented Dec 3, 2022 at 18:46