Why is $\langle 3 \rangle$ a generator of $(\mathbb{Z}_7^*, \cdot)$?

Question

This link here shows that $\langle 3 \rangle$ is a generator for the given group by brute force method, that is trial and error. I was curious as to how to justify this using the theorem.

According to the Corollary, Generators of $\mathbb{Z}_n$:

An integer $k$ in $\mathbb{Z}_n$ is a generator of $\mathbb{Z}_n$ if and only if $\gcd(n, k) = 1$.

Using this we know that $5$ is a generator of the group since gcd($|\mathbb{Z}_7^*|, 5) = 1$. (here $|\mathbb{Z}_7^*| = 6$, i.e, order of the group)

Although gcd($|\mathbb{Z}_7^*|, 3) = 3$.

Where am I going wrong?

Regards,

Answer 1

I think you have confused the groups $$\langle \Bbb Z_n, +\rangle\tag1$$ and $$\langle \Bbb Z_n^\ast, \cdot\rangle\tag2$$

Often when we mention a group, we leave the group operation implicit, and often it isn't confusing. This time, it was confusing.

The theorem you cited about $\gcd(n,k)=1$ is about the additive groups of line $(1)$. But your post you linked to is finding a generator of one of the multiplicative group mentioned in line $(2)$.

As you observed, in this example, the group of interest, $\langle \Bbb Z_7^\ast, \cdot\rangle$, has six elements, not seven.

In fact $\langle \Bbb Z_7^\ast, \cdot\rangle$ and $\langle \Bbb Z_6, +\rangle$ happen to be isomorphic. But the isomorphism looks like this:

\begin{array}{c||cccccc} \langle \Bbb Z_6, +\rangle & 0 & \color{darkgreen}{1} & 2 & 3 & 4 & \color{purple}5 \\ \langle \Bbb Z_7^\ast, \cdot\rangle & 1 & \color{darkgreen}3 & 2 & 6 & 4 & \color{purple}5 \\ \end{array}

As the theorem says, elements $1$ and $5$ are generators of $\langle \Bbb Z_6, +\rangle$.

But the corresponding generators of $\langle \Bbb Z_7^\ast, \cdot\rangle$ are called $3$ and $5$.

(There is a second isomorphism. Can you find it?)

For $\langle \Bbb Z_6, +\rangle$, it's easy to find generators ($1$ is always a generator) and your theorem tells us how. But finding a generator of $\langle \Bbb Z_7^\ast, \cdot\rangle$ is not simple.

Answer 2

A precise formulation of the cited statement is:

Let $k,n\in\mathbb{Z}$ with $n > 0$. The residue class of $k$ is a generator of the cyclic group $(\mathbb{Z}/n\mathbb{Z},+)$ if and only if $\gcd(k,n) = 1$.

Clearly, your multiplicative group $(\mathbb{Z}/7\mathbb{Z})^{\times} = (\mathbb{Z}/7\mathbb{Z} \setminus\{0\},\;\cdot)$ does not match the structure required in the statement.

The group is cyclic of order $6$ though. So there must exist an isomorphism $\phi : (\mathbb{Z}/6\mathbb{Z},+) \to (\mathbb{Z}/7\mathbb{Z})^\times$. Hence you could apply the statement to $(\mathbb{Z}/6\mathbb{Z},+)$ and then use the isomorphism $\phi$ to translate the result to the group $(\mathbb{Z}/7\mathbb{Z})^\times$. However, the problem is that you need an explicit isomorphism $\phi$ for the second step. Writing down such an isomorphism involves the knowledge of a generator of the cyclic group $(\mathbb{Z}/7\mathbb{Z})^\times$, and you are back at your original problem...