# What are the generators of $\mathbb{Z}_n$?

This article says that the generators of $\mathbb{Z}_n$ are the elements which are prime with respect to $n$.

For instance, the generators of $\mathbb{Z}_7$ would be $\{\overline0,\overline1,\overline2,\overline3,\overline4,\overline5,\overline6\}$.

Why can $\overline1$ and $\overline0$ not generate the whole group? $\overline1+\overline1=\overline{1+1}=\overline2$, etc.

• $\bar 0$ is never a generator of $\mathbb Z_n$. – Pece Aug 9 '13 at 10:55
• What generates $\overline0$ then? – fierydemon Aug 9 '13 at 10:56
• The subgroup $\{\bar 0\}$ of $\mathbb Z_n$. – Pece Aug 9 '13 at 10:57
• Sorry I guess adding $\overline1$ $n$ times does. – fierydemon Aug 9 '13 at 10:58
• @Ayush: Just by the way, the subscript should go outside the \mathbb font. Compare \mathbb{Z_n} which produces $$\Huge\mathbb{Z_n}$$ with \mathbb{Z}_n which produces $$\Huge\mathbb{Z}_n$$ There are no lowercase letters in the \mathbb font, and even if there were, it wouldn't change the fact that only the Z is supposed to be in the \mathbb font, while the n is supposed to look the way it normally does. – Zev Chonoles Aug 9 '13 at 11:04

You probably misunderstood the statement. It does not say that a set of generators is given by all elements prime to $n$. It says that any element prime to $n$ will generate the group. In particular, you are right that $\overline 1$ will be a generator. Note the $0$ is not prime to $n$ and $\overline 0$ is not a generator.

You are correct that the set $\{\overline{0},\overline{1}\}$ generates the group $\mathbb{Z}/n\mathbb{Z}$.

However, that's not what the question is about. The issue is which elements of $\mathbb{Z}/n\mathbb{Z}$ generate the entire group on their own - in other words, for which integers $k$ does the set $\{\overline{k}\}\subset\mathbb{Z}/n\mathbb{Z}$ generate all of $\mathbb{Z}/n\mathbb{Z}$? The answer to that is "the integers $k$ that are relatively prime to $n$".

Be careful, $\overline0$ is never a generator ($0$ is not prime with $7$). You are right that $\overline1$ is always a generator of $\mathbb Z_n$, as it is always prime with $n$.

You don't need $\overline0$, since you can reach it with $\overline1$ in this way: $\overline1+\overline1+\dots+\overline1$ (n times) $=\overline n=\overline 0$.

• Yes I noticed that a little later. Thanks! – fierydemon Aug 9 '13 at 10:59

The element $\overline{1}$ generates the group $\mathbb Z_n$ but not the element $\overline{0}$.

Notice that the element $\overline{k}$ generates the group $\mathbb Z_n$ if there's $p$ such that $$p\overline{k}=\overline{1}\iff pk\equiv 1 \mod n\iff pk+qn=1\iff k\wedge n=1$$

• Is $k\wedge n$ supposed to be a notation for the gcd of $k$ and $n$? – Tomas Aug 9 '13 at 12:23
• Yes it is and it is a commonly used notation. – user63181 Aug 9 '13 at 12:42
• Good to know... – Tomas Aug 9 '13 at 12:43