6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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/…. $\endgroup$ – Dietrich Burde May 30 '14 at 13:38
  • 2
    $\begingroup$ 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! $\endgroup$ – Derek Holt May 30 '14 at 13:46
  • $\begingroup$ You are looking for a primitive root modulo $23$. One valid choice is $x = 10$. $\endgroup$ – Omnomnomnom May 30 '14 at 13:47
  • 1
    $\begingroup$ Note that $x^{11} = x \cdot x^2 \cdot ((x^2)^2)^2$ $\endgroup$ – Omnomnomnom May 30 '14 at 13:50
  • 1
    $\begingroup$ 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 = ?$ $\endgroup$ – Derek Holt May 30 '14 at 13:51
8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$
$\endgroup$
  • 1
    $\begingroup$ Welcome to Math.SE! If you are interested in posting mathematical expressions using $\LaTeX$, have a look at the introduction to MathJax. $\endgroup$ – hardmath Sep 19 '15 at 12:11
  • $\begingroup$ 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. $\endgroup$ – RAFARALAHITSIMBA Tiaray Sep 21 '15 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.