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

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.

• The multiplicative group of the field $\mathbb{F}_{23}=\mathbb{Z}/23$ has $22$ elements, not $23$. The multiplicative group $(\mathbb{Z}/23)^{\times}$ is cyclic, see here: math.stackexchange.com/questions/231610/…. – Dietrich Burde May 30 '14 at 13:38
• You are looking for $x$ with $1 \le x \le 22$ such that $x^2 \not\equiv 1 \pmod {23}$ and $x^{11} \not\equiv 1 \pmod {23}$. None of $1,2,3,4$ work! – Derek Holt May 30 '14 at 13:46
• You are looking for a primitive root modulo $23$. One valid choice is $x = 10$. – Omnomnomnom May 30 '14 at 13:47
• Note that $x^{11} = x \cdot x^2 \cdot ((x^2)^2)^2$ – Omnomnomnom May 30 '14 at 13:50
• Keep reducing mod $23$. Try $x=5$. $5^2=2$, $5^4=4$, $5^8 = 16$, $5^{11} = 5^8 \times 5^2 \times 5 = ?$ – Derek Holt May 30 '14 at 13:51

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

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.

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

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$
• Welcome to Math.SE! If you are interested in posting mathematical expressions using $\LaTeX$, have a look at the introduction to MathJax. – hardmath Sep 19 '15 at 12:11
• I manages to automatize the search of generator elements of a prime cyclic group, but I need factorisations database (list of primes number) . If any interrested i'll post the programm on my gihub. – RAFARALAHITSIMBA Tiaray Sep 21 '15 at 16:00