0
$\begingroup$

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.

Thanks in advance!

$\endgroup$
  • 2
    $\begingroup$ $\bar 0$ is never a generator of $\mathbb Z_n$. $\endgroup$ – Pece Aug 9 '13 at 10:55
  • $\begingroup$ What generates $\overline0$ then? $\endgroup$ – fierydemon Aug 9 '13 at 10:56
  • $\begingroup$ The subgroup $\{\bar 0\}$ of $\mathbb Z_n$. $\endgroup$ – Pece Aug 9 '13 at 10:57
  • $\begingroup$ Sorry I guess adding $\overline1$ $n$ times does. $\endgroup$ – fierydemon Aug 9 '13 at 10:58
  • 2
    $\begingroup$ @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. $\endgroup$ – Zev Chonoles Aug 9 '13 at 11:04
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$".

$\endgroup$
2
$\begingroup$

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$.

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

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$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.