Tour:Elements of multiplicative group equal generators of additive group

This article adapts material from the main article: elements of multiplicative group equal generators of additive group

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Multiplicative group modulo n| UP: Introduction four (beginners)| NEXT: Multiplicative group modulo a prime is cyclic
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

WHAT YOU NEED TO DO:

• Carefully understand the statement below, and try proving it yourself.
• Need the proof and make sure you understand it.

Statement

Let $n$ be a positive integer, and consider the group of integers modulo n. Then, an element in this is a generator for the group of integers modulo $n$ if and only if it is an element of the multiplicative group modulo $n$.

Note that these are also the same as the elements in $\{0,1,2,\dots,n-1\}$ that are relatively prime to $n$, and the number of such elements is $\varphi(n)$.

Proof

Generator of additive group implies element of multiplicative group

If $x$ is a generator of $\mathbb{Z}/n\mathbb{Z}$, then some integer multiple of $x$ must be equal to the element $1 \in \mathbb{Z}/n\mathbb{Z}$. Thus, there exists $m$ such that $mx = 1$ in $\mathbb{Z}/n\mathbb{Z}$. Viewing $m$ as a congruence class modulo $n$, we see that $x$ is invertible modulo $n$, and hence is in the multiplicative group.

Element of multiplicative group implies generator of additive group

If $x$ is a element of the multiplicative group modulo $n$, there exists an integer $m$ such that $mx = 1 \mod n$. Thus, the cyclic subgroup containing $x$ must also contain $1$. But any subgroup containing $1$ must equal the whole group $\mathbb{Z}/n\mathbb{Z}$, so $x$ generates the whole group.

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Multiplicative group modulo n| UP: Introduction four (beginners)| NEXT: Multiplicative group modulo a prime is cyclic
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part