Cyclic Groups: Exploring Z_n under Addition

1. The Algebraic Properties of $({\mathbb{Z}}_n,+)$

Before we can call something a "cyclic group," we first need to understand why it's a "group." A group is a set combined with an operation that satisfies four basic properties. Let's verify them for $({\mathbb{Z}}_n,+)$, the set $\{0,1,\dots ,n-1\}$ with the operation of addition modulo $n$.

1. Closure: If you take any two elements $a,b\in {\mathbb{Z}}_n$, is $a+b(\mathrm{mod}n)$ also in ${\mathbb{Z}}_n$?

   • Yes. The operation of addition modulo $n$ is specifically designed to produce a result that is one of the integers from $0$ to $n-1$.

2. Associativity: For any $a,b,c\in {\mathbb{Z}}_n$, is $(a+b)+c\equiv a+(b+c)(\mathrm{mod}n)$?

   • Yes. Standard integer addition is associative. Since modular addition is just integer addition followed by taking a remainder, this property is inherited. For instance, in ${\mathbb{Z}}_8$, $(3+5)+6=8+6\equiv 0+6=6$ and $3+(5+6)=3+11\equiv 3+3=6$.

3. Identity Element: Is there an element $e\in {\mathbb{Z}}_n$ such that $a+e=a$ for all $a\in {\mathbb{Z}}_n$?

   • Yes, the element $0$ acts as the identity. For any $a$, $a+0=a$, and $0+a=a$.

4. Inverse Element: For each element $a\in {\mathbb{Z}}_n$, can we find an element $b\in {\mathbb{Z}}_n$ such that $a+b=0$?

   • Yes. For $a=0$, its inverse is $0$. For any non-zero $a$, its additive inverse is $\mathbf{n}-\mathbf{a}$. For example, in ${\mathbb{Z}}_{10}$, the inverse of 3 is $10-3=7$, because $3+7=10\equiv 0(\mathrm{mod}10)$.

Since $({\mathbb{Z}}_n,+)$ satisfies these four fundamental properties, it is officially a group. We will explore these axioms in much more detail in the next module. For now, we've checked off the first part of our goal.

2. What Makes a Group "Cyclic"?

Now for the main idea: what does it mean for a group to be cyclic? Informally, it means the entire group can be generated by starting with just one element and repeatedly applying the group's operation.

In an additive group like $({\mathbb{Z}}_n,+)$, this means repeatedly adding a single element to itself. This element is called a generator.

For example, let's see which elements can generate ${\mathbb{Z}}_6=\{0,1,2,3,4,5\}$.

• Start with 1:

  • $1$
  • $1+1=2$
  • $1+1+1=3$
  • $...=4$
  • $...=5$
  • $...=6\equiv 0$
    By repeatedly adding 1, we generated every element: $\{1,2,3,4,5,0\}$. So, 1 is a generator of ${\mathbb{Z}}_6$.

• Start with 2:

  • $2$
  • $2+2=4$
  • $2+2+2=6\equiv 0$
  • $2+2+2+2=8\equiv 2$ (we've looped back)
    We only generated the set $\{0,2,4\}$. So, 2 is not a generator.

A group is called cyclic if it has at least one generator. Since we found that 1 is a generator for ${\mathbb{Z}}_6$, we can say that ${\mathbb{Z}}_6$ is a cyclic group.

The following video provides a clear, visual demonstration of this process for ${\mathbb{Z}}_6$ and gives the formal definition of a cyclic group.

3. Verifying that ${\mathbb{Z}}_n$ is Always Cyclic

The video showed that ${\mathbb{Z}}_6$ is cyclic. What about ${\mathbb{Z}}_n$ for any $n$? To verify that ${\mathbb{Z}}_n$ is always a cyclic group, we just need to prove that it always has at least one generator.

Consider the element 1. By adding 1 to itself repeatedly, we get:
$1,1+1=2,1+1+1=3,\dots ,n-1,n\equiv 0$
This process generates every single element of ${\mathbb{Z}}_n$ before cycling back to 0. Therefore, 1 is a generator for every ${\mathbb{Z}}_n$.

Since we can always find a generator (namely, 1), we can conclude that $({\mathbb{Z}}_n,+)$ is a cyclic group for any positive integer $n$. This directly addresses today's learning outcome.

The following reading formalizes these definitions and confirms our conclusion.

4. Finding All Generators of ${\mathbb{Z}}_n$

We know 1 is always a generator. And from the ${\mathbb{Z}}_6$ example, we saw that 5 is also a generator, but 2, 3, and 4 are not. There is a simple and elegant rule to determine which elements generate ${\mathbb{Z}}_n$.

An element $k\in {\mathbb{Z}}_n$ is a generator of ${\mathbb{Z}}_n$ if and only if $k$ is relatively prime to $n$. In other words, if $\gcd (k,n)=1$.

This is a nice application of the number theory concepts we started the course with. Let's check this for ${\mathbb{Z}}_6$:

• $\gcd (1,6)=1⟹1$ is a generator.
• $\gcd (2,6)=2⟹2$ is not a generator.
• $\gcd (3,6)=3⟹3$ is not a generator.
• $\gcd (4,6)=2⟹4$ is not a generator.
• $\gcd (5,6)=1⟹5$ is a generator.

This perfectly matches what we observed! This rule provides a quick way to find all generators for any ${\mathbb{Z}}_n$.

Now, put this rule into practice.

Conclusion

In this lesson, we investigated the additive structure of the integers modulo $n$. We confirmed that $({\mathbb{Z}}_n,+)$ has all the necessary properties to be called a group and, more specifically, a cyclic group.

Key Takeaways:

• The structure $({\mathbb{Z}}_n,+)$ is a group because it satisfies the properties of closure, associativity, identity, and inverses.
• A group is cyclic if all its elements can be produced by repeatedly applying the group operation to a single element, called a generator.
• For any $n$, $({\mathbb{Z}}_n,+)$ is a cyclic group because the element 1 is always a generator.
• An element $k\in {\mathbb{Z}}_n$ is a generator if and only if $\gcd (k,n)=1$.

Preview of the Next Lesson:
We have now thoroughly explored the additive side of ${\mathbb{Z}}_n$. Next, we will turn our attention to the multiplicative operation. We will ask: which elements in ${\mathbb{Z}}_n$ have a multiplicative inverse? The set of these elements forms another, very important group called the group of units, U(n). This will be our first look at a group whose operation is multiplication.