Introducción

Este capítulo continúa nuestro estudio de la teoría de grupos explorando los subgrupos y los generadores. El concepto de elemento primitivo se introducirá al final. Asumimos que ya estás familiarizado con la definición de un grupo. Si necesitas un repaso, echa un vistazo a este artículo.

Para desarrollar la intuición, comenzamos con los grupos aditivos, que son sencillos y ayudan a clarificar conceptos centrales como los subgrupos y los generadores.

Luego pasamos a los grupos multiplicativos de enteros módulo $n$. Los enteros en sí mismos, bajo la multiplicación, no forman un grupo: solo el $1$ y el $-1$ tienen inversos multiplicativos en $\mathbb{Z}$, por lo que los axiomas de grupo fallan. Para solucionar esto, consideramos la multiplicación módulo $n$, enfocándonos en los enteros menores que $n$ que son coprimos con este. Estos enteros coprimos sí tienen inversos multiplicativos módulo $n$, y juntos forman un grupo bien definido. Esta construcción juega un papel central en la teoría de números y es fundamental para muchos sistemas criptográficos.

Coprimos: Dos números son coprimos si su Máximo Común Divisor (MCD) es 1.

Ejemplo 1: 8 y 15 son coprimos porque
Factores de 8: 1, 2, 4, 8
Factores de 15: 1, 3, 5, 15
Factor común: 1
El mcd es 1.

Ejemplo 2: 12 y 18 NO son coprimos porque
Factores de 12: 1, 2, 3, 4, 6, 12
Factores de 18: 1, 2, 3, 6, 9, 18
Factor común: 1, 2, 3, 6
El mcd es 6.

Finalmente, examinamos los generadores: elementos que pueden producir un grupo o subgrupo entero a través de la multiplicación repetida. Comprender los generadores revela importantes estructuras de subgrupos, especialmente cuando $n$ es primo, y destaca su papel crítico en las aplicaciones criptográficas.

1. Grupos Aditivos

Los grupos aditivos usan la adición (a menudo módulo algún número) como operación, siendo el elemento identidad el $0$ y el inverso de un elemento $a$ el $-a$, lo que hace que su estructura sea relativamente sencilla. Sumerjámonos en ejemplos para ver cómo funcionan.

1.1 Ejemplo: $(\mathbb{Z}_6, +)$

Para calentar, considera $\mathbb{Z}_6 = \{0, 1, 2, 3, 4, 5\}$ bajo la adición. Comienza con la clausura:

Cada resultado está en $\{0, 1, 2, 3, 4, 5\}$, por lo que se cumple la clausura. Comprueba las otras propiedades:

• Asociatividad: La agrupación no cambia el resultado:
  • $(2 + 3) + 4 = 5 + 4 = 9 \equiv 3 \pmod{6}$,
  • $2 + (3 + 4) = 2 + (7 \equiv 1) = 3$.
• Identidad: El $0$ funciona como el elemento identidad, ya que $3 + 0 = 3$ (ver la primera fila o columna de la tabla).
• Inversos: Cada elemento tiene un par que suma $0 \pmod{6}$:

Por lo tanto, $(\mathbb{Z}_6, +)$ es un grupo con orden (el número de elementos en un conjunto) $|\mathbb{Z}_6| = 6$.

Ejercicio 1.1: Comprueba si $(\mathbb{Z}_{9}, +)$ es un grupo.

Pista: Intenta construir la tabla de adición como hicimos para $\mathbb{Z}_6$.

Hacer esto a mano puede ser un poco tedioso, así que aquí tienes un script de Python que generará la tabla de adición completa para cualquier $\mathbb{Z}_n$:

Copy

def print_addition_table(mod):
    header = ["+ mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))
    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row + col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))


# Try it with Z_9
print_addition_table(9)

Seguimiento: Después de analizar $\mathbb{Z}_9$, intenta generar la tabla para $\mathbb{Z}_{10}$. ¿Puedes determinar si $(\mathbb{Z}_{10}, +)$ también es un grupo?

Por lo tanto, $(\mathbb{Z}_n, +)$ es un grupo de orden $n$. Los grupos finitos como este son clave en la aritmética modular y la criptografía. A continuación, dirigimos nuestra atención a cómo ciertos elementos y subconjuntos dentro de un grupo pueden revelar una estructura más profunda—a través de subgrupos y generadores.

2. Subgrupos y Generadores

2.1 Entendiendo los Subgrupos

Al estudiar grupos, a menudo encontramos subconjuntos que retienen la estructura del grupo bajo la misma operación. Estos subconjuntos especiales, llamados subgrupos, se comportan como versiones en miniatura del grupo principal. Sin embargo, no cualquier subconjunto califica—exploremos esto con ejemplos para ver qué hace a un subgrupo.

Ejemplo 2.1.1: Subgrupos en $(\mathbb{Z}, +)$

Considera $(\mathbb{Z}, +)$, el grupo de todos los enteros bajo la adición, y dos subconjuntos familiares:

• El conjunto de los enteros pares: $\{\ldots, -4, -2, 0, 2, 4, \ldots\}$
• El conjunto de los enteros impares: $\{\ldots, -3, -1, 1, 3, 5, \ldots\}$

Comprobemos los enteros pares:

• Clausura: La suma de dos números pares es par (p. ej., $-2 +4= 2$).
• Identidad: El $0$ es par y está incluido.
• Inversos: El inverso de cualquier número par también es par (p. ej., el inverso de $2$ es $-2$).
• Asociatividad: Heredada de $\mathbb{Z}$.

Los enteros pares satisfacen todas las propiedades de grupo—este es un subgrupo válido.

Ahora comprobemos los enteros impares:

• Clausura: $1 + 3= 4$, que es par—no es parte del conjunto. Por lo tanto, la clausura falla.
• Identidad: El $0$ no es impar, por lo que falta el elemento identidad.
• Inversos: Para el $1$, el $-1$ es impar—pero como la clausura y la identidad ya fallan, no es un subgrupo.

Los enteros impares bajo la adición no satisfacen los criterios de subgrupo—son solo un subconjunto, no un subgrupo.

Ejemplo 2.1.2: Subgrupos en $(\mathbb{Z}_8, +)$

Ahora toma $(\mathbb{Z}_8, +) = \{0, 1, 2, 3, 4, 5, 6, 7\}$ y prueba dos subconjuntos:

• Pares módulo 8: $\{0, 2, 4, 6\}$
• Primera mitad: $\{0, 1, 2, 3\}$

Para $\{0, 2, 4, 6\}$:

• Clausura: $2 +4= 6$, $4 +6= 10 \equiv2\pmod{8}$ (ambos en el conjunto).
• Identidad: El $0$ está presente.
• Inversos: $2 +6= 8 \equiv 0$, $4 +4= 8 \equiv 0$, $0 + 0 = 0$ (todos los pares funcionan).
• Asociatividad: Se cumple desde $\mathbb{Z}_8$.

¡Este es un subgrupo!

Para $\{0, 1, 2, 3\}$ :

• Clausura: $2+3= 5$ (no en el conjunto).
• Identidad: El $0$ está presente.
• Inversos: Para el $1$, ningún elemento en $\{0, 1, 2, 3\}$ da $0$ (p. ej., $1 +3=4\pmod{8}$).

Este falla en ser un grupo, por lo que es solo un subconjunto, no un subgrupo.

Definición: Un subconjunto $H$ de un grupo $G$ es un subgrupo si es un grupo bajo la misma operación, lo que significa que satisface la clausura, contiene la identidad, tiene inversos para todos sus elementos y hereda la asociatividad de $G$.

Ejercicio 2.1.1: Encuentra todos los subgrupos de $(\mathbb{Z}_{5}, +)$.

2.2 Generadores en Grupos Aditivos

Ahora que hemos visto los subgrupos, exploremos cómo elementos individuales pueden generarlos—o incluso a todo el grupo. Revisaremos $(\mathbb{Z}_6, +) = \{0, 1, 2, 3, 4, 5\}$, el grupo aditivo bajo la adición módulo $6$, y examinaremos qué pasa cuando sumamos repetidamente un elemento a sí mismo, como un “paseo” alrededor de los números módulo $6$.

Ejemplo 2.2.1: Generadores en $(\mathbb{Z}_6, +)$

Intento 1:

• $1$
• $1 + 1 = 2$
• $2 + 1 = 3$
• $3 + 1 = 4$
• $4 + 1 = 5$
• $5 + 1 = 6 \equiv 0 \pmod{6}$

Esto da $\{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$. Sumar $1$ repetidamente recorre el grupo entero.

Intento 2:

• $2$
• $2 + 2 = 4$
• $4 + 2 = 6 \equiv 0 \pmod{6}$
• $0 + 2 = 2$

Esto da $\{0, 2, 4\}$—solo la mitad del grupo.

Intento 3:

• $3$
• $3 + 3 = 6 \equiv 0 \pmod{6}$
• $0 + 3 = 3$

Esto da $\{0, 3\}$, ¡aún más pequeño!

Intento 5:

• $5$
• $5 + 5 = 10 \equiv 4 \pmod{6}$
• $4 + 5 = 9 \equiv 3 \pmod{6}$
• $3 + 5 = 8 \equiv 2 \pmod{6}$
• $2 + 5 = 7 \equiv 1 \pmod{6}$
• $1 + 5 = 6 \equiv 0 \pmod{6}$

Esto da $\{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$, cubriéndolo todo, igual que el $1$.

Ejercicio 2.2.1: En $(\mathbb{Z}_9, +)$, ¿qué elementos generan el $\mathbb{Z}_9$ entero? ¿Qué elementos generan subgrupos propios?

2.2.2 Subgrupos Generados por Elementos

Ahora considera cualquier grupo $G$ con una operación binaria (como la adición o la multiplicación), y sea $g$ un elemento de $G$. Al aplicar repetidamente la operación de grupo a $g$, podemos formar el conjunto de elementos que genera. Este conjunto se denota $\langle g \rangle$ y se llama el subgrupo cíclico generado por $g$.

Por ejemplo en grupos aditivos:

Para muchos elementos, $\langle g \rangle$ es un subgrupo propio. Pero cuando $\langle g \rangle = G$, decimos que $g$ es un generador de $G$, y que $G$ es un grupo cíclico.
Como se muestra en el Ejemplo 2.2.1, calculamos los subgrupos generados por elementos en $(\mathbb{Z}_6, +) = \{0, 1, 2, 3, 4, 5\}$ bajo la adición módulo 6. Los subgrupos generados por cada elemento son los siguientes:

• $\langle 0 \rangle = \{0\}$ (subgrupo propio)
• $\langle 1 \rangle = \{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$
• $\langle 2 \rangle = \{0, 2, 4\}$ (subgrupo propio)
• $\langle 3 \rangle = \{0, 3\}$ (subgrupo propio)
• $\langle 4 \rangle = \{0, 4, 2\}$ (subgrupo propio)
• $\langle 5 \rangle = \{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$

Los elementos $1$ y $5$ generan el grupo entero $\mathbb{Z}_6$, convirtiéndolos en generadores, mientras que $0$, $2$, $3$ y $4$ generan subgrupos propios.

Ejemplo 2.2.3: Generadores en $(\mathbb{Z}_5, +)$

Ahora prueba $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$ bajo la adición módulo 5:

• $\langle1\rangle = \{0, 1, 2, 3, 4\}=\mathbb{Z}_5$
• $\langle2\rangle =\{2, 4, 6 \equiv 1 \pmod 5 , 8 \equiv 3 \pmod 5\} =\{1,2,3,4\}=\mathbb{Z}_5$
• $\langle3\rangle= \{3, 6 \equiv 1 \pmod 5, 9 \equiv 4\pmod 5 , 7 \equiv 2\pmod 5 \}=\{1,2,3,4\}=\mathbb{Z}_5$
• $\langle4\rangle =\{4, 8 \equiv 3 \pmod 5, 12 \equiv 2\pmod 5 , 16 \equiv 1\pmod 5 \}=\{1,2,3,4\}=\mathbb{Z}_5$

Cada elemento distinto de cero es un generador.

Esto sucede porque $\gcd(g, 5) = 1$ para todo $g \neq 0$, y el $5$ es primo.

Conclusión: En $(\mathbb{Z}_n, +)$, un elemento $g$ genera el grupo entero si y solo si $\gcd(g, n) = 1$. Para un $n$ primo, todos los elementos distintos de cero son generadores. Para un $n$ compuesto, solo algunos elementos califican.

2.3 Código: Explorando Generadores Aditivos en $(\mathbb{Z}_n, +)$

Copy
def additive_closure(a, n):
    """Generates {0, a, 2a, 3a, ...} mod n until it repeats."""
    result = []
    current = 0
    while current not in result:
        result.append(current)
        current = (current + a) % n
    return sorted(result)  # Sorted for readability

# Show generated sets in (Z_6 , +)
print("Z_6:")
for a in range(6):
    print(f"Generated by {a}: {additive_closure(a, 6)}")

# Show generated sets in (Z_5, +)
print("\nZ_5:")
for a in range(5):
    print(f"Generated by {a}: {additive_closure(a, 5)}")

Salida:

Copy
(Z_6, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4, 5]
Generated by 2: [0, 2, 4]
Generated by 3: [0, 3]
Generated by 4: [0, 2, 4]
Generated by 5: [0, 1, 2, 3, 4, 5]

(Z_5, +):
Generated by 0: [0]
Generated by 1: [0, 1, 2, 3, 4]
Generated by 2: [0, 1, 2, 3, 4]
Generated by 3: [0, 1, 2, 3, 4]
Generated by 4: [0, 1, 2, 3, 4]

Habiendo explorado los grupos aditivos, ahora pasamos a sus contrapartes multiplicativas.

3. Grupos Multiplicativos

Los grupos multiplicativos operan bajo la multiplicación (a menudo módulo algún número), siendo el elemento identidad el $1$, aunque encontrar inversos puede tener más matices, especialmente en entornos finitos. Para ilustrar esto, examinaremos un ejemplo concreto usando la multiplicación módulo $7$.

3.1 Ejemplo:

Considera $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$:

• Se cumple la clausura, p. ej., $2 \times5= 10 \equiv 3$, está en el conjunto.
• Identidad: El elemento identidad es el $1$, pero esto falla para el $0$, que no tiene inverso;
• Inversos: Cada elemento distinto de cero tiene un inverso:
  • $1 \times1= 1$
  • $2 \times4= 8 \equiv1\pmod{7}$
  • $3 \times5= 15 \equiv1\pmod{7}$
  • $4 \times2= 8 \equiv1\pmod{7}$
  • $5 \times3= 15 \equiv1\pmod{7}$
  • $6 \times6= 36 \equiv1\pmod{7}$

Dado que el $0$ no tiene inverso, $(\mathbb{Z}_7, \times)$ no es un grupo. Pero si eliminamos el $0$ y consideramos solo los elementos distintos de cero — es decir, $\mathbb{Z}_7 \setminus \{0\} = \{1, 2, 3, 4, 5, 6\}$ — obtenemos un grupo bajo la multiplicación. Este conjunto a menudo se denota como $\mathbb{Z}_7^*$ y es un grupo de orden 6.

Puedes usar este código para generar la tabla de multiplicación para cualquier módulo $n$:

Copy
def print_multiplication_table(mod):
    header = ["× mod " + str(mod)] + list(range(mod))
    print(" | ".join(str(h).rjust(4) for h in header))
    print("-" * (6 * (mod + 1)))

    for row in range(mod):
        line = [str(row).rjust(4)]
        for col in range(mod):
            value = row * col
            result = value % mod
            if value >= mod:
                line.append(f"{value} ≡ {result}".rjust(6))
            else:
                line.append(str(result).rjust(6))
        print(" | ".join(line))

print_multiplication_table(5)

3.2 Ejemplo: $(\mathbb{Z}_6\setminus \{0\}, \times),$ No Es un Grupo

Ahora probemos el conjunto $\{1, 2, 3, 4, 5\}$ bajo la multiplicación mod 6.

Ahora tenemos un problema más fundamental: algunas multiplicaciones dan como resultado 0, que no es parte del conjunto. Por lo tanto, este conjunto y operador binario no están cerrados, así que no es un grupo.

3.3 Ejemplo: $(\mathbb{Z}_8\setminus\{0\}, \times)$

Como otro ejemplo, consideremos ahora la multiplicación en $\mathbb{Z}_8\setminus\{0\} = \{1, 2, 3, 4, 5, 6, 7\}$:

Solo los elementos $\{1, 3, 5, 7\}$—aquellos que son coprimos con 8—tienen inversos multiplicativos módulo 8:

• $1 \times1= 1 \pmod 8$
• $3 \times3= 9 \equiv 1 \pmod 8$
• $5 \times5= 25 \equiv 1 \pmod 8$
• $7 \times7= 49 \equiv 1 \pmod 8$

Los elementos restantes, $\{2, 4, 6\}$, comparten todos un factor común con 8 y, por lo tanto, no tienen inversos. Así, $\mathbb{Z}_8 \setminus \{0\}$ no es un grupo bajo la multiplicación.

3.4. ¿Qué es $\mathbb{Z}_n^*$?

El conjunto $\mathbb{Z}_n^*$ se define formalmente como:

Es decir, $\mathbb{Z}_n^*$ consiste en todos los elementos en $\mathbb{Z}_n$ que tienen un inverso multiplicativo módulo $n$.

• Cuando $n$ es primo, cada elemento distinto de cero es invertible, por lo que:
  

  $$\mathbb{Z}_n^* = \mathbb{Z}_n \setminus \{0\}$$

• Cuando $n$ es compuesto, solo los elementos coprimos con $n$ son invertibles. Por ejemplo:

  • $\mathbb{Z}_6^* = \{1, 5\}$
  • $\mathbb{Z}_8^* = \{1, 3, 5, 7\}$

En ambos casos, $\mathbb{Z}_n^*$ forma un grupo bajo la multiplicación. Sin embargo, el conjunto completo $\mathbb{Z}_n \setminus \{0\}$ no siempre forma un grupo—a menos que $n$ sea primo.

Anteriormente, usamos $\mathbb{Z}_n \setminus \{0\}$ para demostrar por qué la ausencia de inversos (y la presencia de divisores de cero) rompe la estructura de grupo cuando $n$ es compuesto. Esta distinción es más que técnica: juega un papel central en la comprensión de la aritmética modular, los algoritmos criptográficos y la teoría de números.

En la siguiente sección, exploraremos cómo cambia la estructura de $\mathbb{Z}_n^*$ cuando $n$ es primo.

3.5 Por Qué Funcionan los Módulos Primos

Estos fallos motivan los módulos primos. En $\{1,2,\ldots, p-1\}$, donde $p$ es primo, cada elemento tiene un inverso. De hecho, esto está garantizado por un resultado clásico de la teoría de números.

Considera el patrón para $\{1, 2, \ldots, n-1\}$ módulo $n$:

• Si $n$ no es primo, no es un grupo debido a los divisores de cero y los inversos faltantes (p. ej., $n = 6, 8$).
• Si $n$ es primo, es un grupo.

3.6 Código de Python para Calcular el Inverso

Uno de los métodos más simples y eficientes es usar la función integrada de Python pow(a, -1, p) para calcular inversos modulares. Entre bastidores, esto funciona debido a un famoso resultado de la teoría de números llamado pequeño teorema de Fermat, que garantiza que existe un inverso y nos dice:

cuando el módulo $p$ es un número primo y $a$ no es divisible por $p$.

Aquí tienes un ejemplo:

Copy
def mod_inverse(a, p):  
    return pow(a, -1, p)

# Test for Z_7^*
def test_inverses(p):
    print(f"Testing inverses modulo {p}:")
    for a in range(1, p):
        inv = mod_inverse(a, p)
        print(f"Inverse of {a} mod {p} is {inv} (check: {a} * {inv} = {a * inv % p})")

if __name__ == "__main__":
    p = 7
    test_inverses(p)

Salida:

Copy
Testing inverses modulo 7:
Inverse of 1 mod 7 is 1 (check: 1 * 1 = 1)
Inverse of 2 mod 7 is 4 (check: 2 * 4 = 1)
Inverse of 3 mod 7 is 5 (check: 3 * 5 = 1)
Inverse of 4 mod 7 is 2 (check: 4 * 2 = 1)
Inverse of 5 mod 7 is 3 (check: 5 * 3 = 1)
Inverse of 6 mod 7 is 6 (check: 6 * 6 = 1)

3.7 Ejercicios

Ejercicios de Matemáticas:

1. Encuentra el inverso modular (si existe) para lo siguiente, usando la función pow(a, -1, n) de Python o una calculadora. Para módulos primos, opcionalmente puedes usar el pequeño teorema de Fermat:

   • $3^{-1} \mod 11$
   • $7^{-1} \mod 26$
   • $4^{-1} \mod 15$

2. ¿Para qué valores de $a$ en $\mathbb{Z}_{12}^*$ existe el inverso modular?

Ejercicios de Programación:

1. Escribe una función list_all_inverses(n) que devuelva un diccionario con todos los elementos en $\mathbb{Z}_n^*$ junto con sus inversos (si existen).

2. Escribe un programa que tome la entrada del usuario a y n, y compruebe si existe un inverso modular. Si es así, imprime el inverso. Pruébalo con diferentes valores y observa qué descubres.

3. Reto: Elige algunos números primos pequeños p y escribe un programa que compruebe si pow(a, p - 1, p) == 1 para todos los a en {1, 2, ..., p - 1}. ¿Se cumple esto para cada a? ¿Qué pasa si p no es primo?

4. Generadores en Grupos Multiplicativos

Ahora dirigimos nuestra atención a los generadores en los grupos multiplicativos. Para desarrollar la intuición, comenzamos con ejemplos concretos en $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5, 6\}$, explorando cómo elementos individuales pueden generar el grupo completo—o solo una parte de él—a través de la multiplicación repetida.

Ejemplo 4.1: $(\mathbb{Z}_7^*, \times)$

Intento 3:

• $3^1 = 3$
• $3^2 = 9 \equiv 2 \pmod{7}$
• $3^3 = 27 \equiv 6 \pmod{7}$
• $3^4 = 81 \equiv 4 \pmod{7}$
• $3^5 = 243 \equiv 5 \pmod{7}$
• $3^6 = 729 \equiv 1 \pmod{7}$

$\langle 3 \rangle = \{1, 2, 3, 4, 5, 6\} = \mathbb{Z}_7^*$. El elemento $3$ es un generador.

Intento 2:

• $2^1 = 2$
• $2^2 = 4$
• $2^3 = 8 \equiv 1 \pmod{7}$

$\langle 2 \rangle = \{1, 2, 4\}$, un subgrupo, no el grupo completo.

Prueba con Otros Elementos:

• $4$: $4, 16 \equiv 2, 8 \equiv 1$ $\Rightarrow \{1, 2, 4\}$
• $5$: $5, 25 \equiv 4, 20 \equiv 6, 30 \equiv 2, 10 \equiv 3, 15 \equiv 1$ $\Rightarrow \mathbb{Z}_7^*$
• $6$: $6, 36 \equiv 1$ $\Rightarrow \{1, 6\}$

Resumen:

4.1 Elementos Primitivos

Como vemos, en el grupo aditivo $(\mathbb{Z}_p, +)$, donde $p$ es primo, se garantiza que cada elemento distinto de cero es un generador. Es decir, sumar repetidamente cualquier elemento distinto de cero eventualmente recorrerá todos los elementos del grupo. Sin embargo, en los grupos multiplicativos $(\mathbb{Z}_p^*, \times)$, solo algunos elementos son generadores—estos se llaman elementos primitivos. Este contraste resalta una diferencia fundamental: los grupos aditivos sobre primos son siempre cíclicos con todos los elementos distintos de cero como generadores, mientras que los grupos multiplicativos sobre primos son cíclicos pero tienen solo un subconjunto de elementos que sirven como generadores.

Definición: Un elemento $g \in \mathbb{Z}_p^*$ es un elemento primitivo si

$$\langle g \rangle = \{g^1, g^2, \ldots, g^{p-1}\} \pmod{p} = \mathbb{Z}_p^*.$$

Toma, por ejemplo, $\mathbb{Z}_7^*$: $3$ y $5$ son elementos primitivos, mientras que $2$, $4$ y $6$ no lo son.

Un resultado fundamental en la teoría de números garantiza que para cualquier primo $p$, el grupo $\mathbb{Z}_p^*$ es cíclico, lo que significa que siempre contiene al menos un elemento primitivo. Esto contrasta con el grupo aditivo $(\mathbb{Z}_p, +)$, donde cada elemento distinto de cero genera el grupo completo.

Ejemplo 4.1.1: $\mathbb{Z}_5^* = \{1, 2, 3, 4\}$

• Elemento 2:
  

  $$\begin{align*} 2^1 &= 2 \pmod{5}, \\ 2^2 &= 4 \pmod{5}, \\ 2^3 &= 8 \equiv 3 \pmod{5}, \\ 2^4 &= 16 \equiv 1 \pmod{5} \end{align*}$$
  
  $\langle 2 \rangle = \{1, 2, 3, 4\} = \mathbb{Z}_5^*$, por lo que $2$ es un elemento primitivo.

• Elemento 3:
  

  $$\begin{align*} 3^1 &= 3 \pmod{5}, \\ 3^2 &= 9 \equiv 4 \pmod{5}, \\ 3^3 &= 27 \equiv 2 \pmod{5}, \\ 3^4 &= 81 \equiv 1 \pmod{5} \end{align*}$$
  
  $\langle 3 \rangle = \{1, 2, 3, 4\} = \mathbb{Z}_5^*$, por lo que $3$ también es un elemento primitivo.

Ejemplo 4.1.2: $\mathbb{Z}_{11}^* = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$

• Elemento 2:
  

  $$\begin{align*} 2^1 &= 2 \pmod{11}, \\ 2^2 &= 4 \pmod{11}, \\ 2^3 &= 8 \pmod{11}, \\ 2^4 &= 16 \equiv 5 \pmod{11}, \\ 2^5 &= 10 \pmod{11}, \\ 2^6 &= 20 \equiv 9 \pmod{11}, \\ 2^7 &= 18 \equiv 7 \pmod{11}, \\ 2^8 &= 14 \equiv 3 \pmod{11}, \\ 2^9 &= 6 \pmod{11}, \\ 2^{10} &= 12 \equiv 1 \pmod{11} \end{align*}$$
  
  $\langle 2 \rangle = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} = \mathbb{Z}_{11}^*$, por lo que $2$ es un elemento primitivo.

• Elemento 3:
  

  $$\begin{align*} 3^1 &= 3 \pmod{11}, \\ 3^2 &= 9 \pmod{11}, \\ 3^3 &= 27 \equiv 5 \pmod{11}, \\ 3^4 &= 15 \equiv 4 \pmod{11}, \\ 3^5 &= 12 \equiv 1 \pmod{11} \end{align*}$$
  
  $\langle 3 \rangle = \{1, 3, 4, 5, 9\}$, un subgrupo, no el grupo completo.

Ejemplo 4.1.3: $\mathbb{Z}_{17}^*$

• Elemento 3:
  

  $$\begin{align*} 3^1 &= 3 \pmod{17}, \\ 3^2 &= 9 \pmod{17}, \\ 3^3 &= 27 \equiv 10 \pmod{17}, \\ 3^4 &= 81 \equiv 13 \pmod{17}, \\ 3^5 &= 243 \equiv 5 \pmod{17}, \\ 3^6 &= 729 \equiv 15 \pmod{17}, \\ 3^7 &= 2187 \equiv 11 \pmod{17}, \\ 3^8 &= 6561 \equiv 16 \pmod{17}, \\ 3^9 &= 19683 \equiv 14 \pmod{17}, \\ 3^{10} &= 59049 \equiv 8 \pmod{17}, \\ 3^{11} &= 177147 \equiv 7 \pmod{17}, \\ 3^{12} &= 531441 \equiv 4 \pmod{17}, \\ 3^{13} &= 1594323 \equiv 12 \pmod{17}, \\ 3^{14} &= 4782969 \equiv 2 \pmod{17}, \\ 3^{15} &= 14348907 \equiv 6 \pmod{17}, \\ 3^{16} &= 43046721 \equiv 1 \pmod{17} \end{align*}$$

  $\langle 3 \rangle = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\} = \mathbb{Z}_{17}^*$, orden $16$ (grupo completo). Por lo tanto, $3$ es un elemento primitivo de $\mathbb{Z}_{17}^*$.