Encuentre un generador del grupo multiplicativo de $\mathbb{Z}/23\mathbb{Z}$ como grupo cíclico

Question

Necesito encontrar un generador del grupo multiplicativo de $\mathbb{Z}/23\mathbb{Z}$ como grupo cíclico.

Desde $\mathbb{Z}/23\mathbb{Z}$ sólo tiene $23$ elementos y orden $(x)$ donde $x$ es un generador debe dividir $23$ Entonces, ¿significa esto que el generador sólo puede ser $1$ o $23$ ? ¿O me he equivocado de idea?

Sería de gran ayuda si alguien puede dar la solución a este problema, no encuentro pistas muy útiles.

Answer 1

Como se ha señalado en los comentarios, $\mathbb{F}_{23} = \mathbb{Z}/23$ tiene $22$ elementos, y es un grupo cíclico. Como el orden de cualquier elemento de ese grupo debe dividir $22$ todos los pedidos deben ser $1$ , $2$ , $11$ o $22$ . Se busca un elemento de orden $22$ . Para encontrarlos, sólo hay que calcular el segundo y $11^{\mathrm{th}}$ potencias de cada elemento módulo 23; cuando ninguno es $1$ Has encontrado un elemento de orden $22$ .

Answer 2

He aquí un método que aprovecha el orden del grupo y el hecho de que una raíz primitiva no es un residuo cuadrático (también se puede utilizar la reciprocidad cuadrática para encontrar los no-residuos, lo que sería bastante rápido en este caso).

El grupo cíclico de orden $22$ tiene un elemento de orden $1$ , una de orden $2$ , diez de orden $11$ (todos los cuales son cuadrados, o equivalentemente residuos cuadráticos) y los diez restantes de orden $22$ .

Los residuos cuadráticos módulo $23$ son $1,4,9,16,2,13,3,18,12,8,6$ y todos ellos tienen orden impar en el grupo multiplicativo, correspondiente a los elementos de orden $1$ y $11$ . Sólo hay un elemento de orden $2$ - a saber $-1\equiv 22$ . El resto son raíces primitivas.

Answer 3

Estos son no generadores:

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

Answer 4

Una prima $p$ de la forma $p = 2q+1$ para otro primo $q$ permite una serie de atajos en el cálculo de un generador para el grupo multiplicativo de $\mathbb{Z}/p\mathbb{Z}.$ Ese grupo multiplicativo tiene orden $2q,$ por lo que todos sus elementos tienen orden $1,2,q$ o $2q$ .

Si excluimos $1$ y $-1$ , todos los demás elementos tienen un orden $q$ o $2q$ . Si tenemos la mala suerte de elegir un elemento $x$ que tiene orden multiplicativo $q$ entonces $\{x^{i} : 1 \leq i \leq q-1 \}$ contiene todos los elementos de orden $q$ Así que si evitamos estos y $\pm 1,$ encontraremos un generador.

Si (o tal vez cuando) conoces los residuos cuadráticos, cuando $p$ tiene esta forma y $q >2$ vemos que $p \equiv 3 \pmod{4}$ Por lo tanto, como se ha señalado en otras respuestas y comentarios, siempre que evitemos los residuos cuadráticos (y $\pm 1$ ) encontraremos un generador: un primo impar $r \equiv 1 \pmod{4}$ es un residuo cuadrático (mod $p$ ) si y sólo si $p$ es un residuo cuadrático (mod $r$ ), y una prima impar $r \equiv 3 \pmod{4}$ es un residuo cuadrático (mod $p$ ) si y sólo si $p$ es un no-residuo cuadrático (mod $r$ ).

Además, $2$ es un residuo cuadrático (mod $p$ ) si y sólo si $q \equiv 3$ (mod $4$ ) cuando $p$ tiene esta forma. En su caso, esto significa que $2$ es un residuo cuadrático (como ya han notado otros), por lo que el cálculo de las potencias de $2$ (mod $23$ ) le dará todos los residuos cuadráticos (mod $23$ ), es decir, todos los elementos de orden $11$ .