Find a generator of the multiplicative group of $\mathbb{Z}/23\mathbb{Z}$ as a cyclic group

Question

I need to find a generator of the multiplicative group of $\mathbb{Z}/23\mathbb{Z}$ as a cyclic group.

Since $\mathbb{Z}/23\mathbb{Z}$ only has $23$ elements and ord$(x)$ where $x$ is a generator must divide $23$, then does this mean the generator can only be $1$ or $23$? Or have I got the wrong idea?

It would help if someone can provide the solution to this problem, I don't find hints very useful.

Answer 1

As has been pointed out in the comments, $\mathbb{F}_{23} = \mathbb{Z}/23$ has $22$ elements, and is a cyclic group. Since the order of any element in that group must divide $22$, all orders must be $1$, $2$, $11$, or $22$. You are looking for an element of order $22$. To find them, you need only compute the second and $11^{\mathrm{th}}$ powers of each element modulo 23; when neither is $1$, you have found an element of order $22$.

Answer 2

Here is a method which exploits the order of the group and the fact that a primitive root is not a quadratic residue (you can also use quadratic reciprocity to find non-residues, which would be quite quick here).

The cyclic group of order $22$ has one element of order $1$, one of order $2$, ten of order $11$ (all of which are squares, or equivalently quadratic residues) and the remaining ten of order $22$.

The quadratic residues modulo $23$ are $1,4,9,16,2,13,3,18,12,8,6$ and these all have odd order in the multiplicative group, corresponding to the elements of order $1$ and $11$. There is just one element of order $2$ - namely $-1\equiv 22$. The remainder are primitive roots.

Answer 3

A prime $p$ of the form $p = 2q+1$ for another prime $q$ allows a number of shortcuts in calculating a generator for the multiplicative group of $\mathbb{Z}/p\mathbb{Z}.$ That multiplicative group has order $2q,$ so all of its elements have order $1,2,q$ or $2q$.

If we exclude $1$ and $-1$, every other element has order $q$ or $2q$. If we are unlucky enough to choose an element $x$ which has multiplicative order $q$, then $\{x^{i} : 1 \leq i \leq q-1 \}$ contains all the elements of order $q$, so if we avoid these and $\pm 1,$ we will find a generator.

If (or perhaps when) you know about quadratic residues, when $p$ has this form and $q >2$, we see that $p \equiv 3 \pmod{4}$, so, as has been noted in other answers and comments, as long as we avoid quadratic residues (and $\pm 1$) we will find a generator: an odd prime $r \equiv 1 \pmod{4}$ is a quadratic residue (mod $p$) if and only if $p$ is a quadratic residue (mod $r$), and an odd prime $r \equiv 3 \pmod{4}$ is a quadratic residue (mod $p$) if and only if $p$ is a quadratic non-residue (mod $r$).

Furthermore, $2$ is a quadratic residue (mod $p$) if and only if $q \equiv 3$ (mod $4$) when $p$ has this form. In your case, this means that $2$ is a quadratic residue (as others have already noticed), so computing the powers of $2$ (mod $23$) will give you all quadratic residues (mod $23$), that is, all elements of order $11$.

Answer 4

These are not generators:

• 2 because $2^{11} \bmod 23 =1$
• 3 because $3^{11} \bmod 23 =1$
• 4 because $4^{11} \bmod 23 =1$
• 6 because $6^{11} \bmod 23 =1$
• 8 because $8^{11} \bmod 23 =1$
• 9 because $9^{11} \bmod 23 =1$
• 12 because $12^{11} \bmod 23 =1$
• 13 because $13^{11} \bmod 23 =1$
• 16 because $16^{11} \bmod 23 =1$
• 18 because $18^{11} \bmod 23 =1$
• 22 because $22^{2} \bmod 23 =1$