Raíz primitiva módulo n

En aritmética modular , un número $g$ es una raíz primitiva módulo $n$ si todo número coprimo $de$ $n$ es congruente con una potencia de $g$ módulo $n$ . Es decir, $g$ es una raíz primitiva módulo $n$ si para todo entero coprimo de $n$ $existe$ algún entero $k$ para el cual $g$ ^$k$ ≡ $a$ (mod $n$ ). Tal valor $k$ se llama índice o logaritmo discreto de $a$ a la base $g$ módulo $n$ . Entonces $g$ es una raíz primitiva módulo $n$ si y solo si $g$ es un generador del grupo multiplicativo de enteros módulo $n$ .

Gauss definió las raíces primitivas en el artículo 57 de las Disquisitiones Arithmeticae (1801), donde le dio crédito a Euler por haber acuñado el término. En el artículo 56 afirmó que Lambert y Euler los conocían, pero fue el primero en demostrar rigurosamente que existen raíces primitivas para una $n$ prima . De hecho, las Disquisitiones contienen dos pruebas: la del artículo 54 es una prueba de existencia no constructiva , mientras que la prueba del artículo 55 es constructiva .

Aquí vemos que el período de 3 ^$k$ módulo 7 es 6. Los restos en el período, que son 3, 2, 6, 4, 5, 1, forman un reordenamiento de todos los restos distintos de cero módulo 7, lo que implica que 3 es de hecho un raíz primitiva módulo 7. Esto se deriva del hecho de que una secuencia ( $g$ ^$k$ módulo $n$ ) siempre se repite después de algún valor de $k$ , ya que el módulo $n$ produce un número finito de valores. Si $g$ es una raíz primitiva módulo $n$ y $n$ es primo, entonces el período de repetición es $n$ − 1. Se ha demostrado que las permutaciones creadas de esta manera (y sus desplazamientos circulares) sonArreglos de Costas .

Si $n$ es un número entero positivo, los números enteros entre 0 y $n$ − 1 que son coprimos de $n$ (o de manera equivalente, las clases de congruencia coprimos de $n$ ) forman un grupo , con el módulo de multiplicación $n$ como operación; se denota por ${\ estilo de visualización \ mathbb {Z}}$ ^×
_$norte$, y se denomina grupo de unidades módulo $n$ , o grupo de clases primitivas módulo $n$ . Como se explica en el artículo grupo multiplicativo de enteros módulo $n$ , este grupo multiplicativo ( ${\ estilo de visualización \ mathbb {Z}}$ ^×
_$norte$) es cíclico si y solo si $n$ es igual a 2, 4, $p k$ o 2 $p k$ donde $p k$ es una potencia de un número primo impar . ^[2]^[3]^[4] Cuando (y solo cuando) este grupo ${\ estilo de visualización \ mathbb {Z}}$ ^×
_$norte$es cíclico, un generador de este grupo cíclico se llama raíz primitiva módulo $n$ ^[5] (o en un lenguaje más completo raíz primitiva de la unidad módulo $n$ , enfatizando su papel como una solución fundamental de las raíces de las ecuaciones polinómicas unitarias X^$metro$
− 1 en el anillo _$n$ ), o simplemente un elemento primitivo de ${\ estilo de visualización \ mathbb {Z}}$ ${\ estilo de visualización \ mathbb {Z}}$ ^×
_$norte$.

Cuando ${\ estilo de visualización \ mathbb {Z}}$ ^×
_$norte$es no cíclico, tales elementos primitivos mod $n$ no existen. En cambio, cada componente primo de $n$ tiene sus propias raíces subprimitivas (ver $15$ en los ejemplos a continuación).

Para cualquier $n$ (sea o no ${\ estilo de visualización \ mathbb {Z}}$ ^×
_$norte$es cíclico), el orden de ${\ estilo de visualización \ mathbb {Z}}$ ^×
_$norte$viene dada por la función totient de Euler $φ$ ( $n$ ) (secuencia A000010 en la OEIS ). Y luego, el teorema de Euler dice que $a$ ^{$φ$ ( $n$ )} ≡ 1 (mod $n$ ) para todo $a$ coprimo de $n$ ; la potencia más baja de $a$ que es congruente con 1 módulo $n$ se denomina orden multiplicativo de $a$ módulo $n$ . En particular, para que a sea $una$ raíz primitiva módulo $n$ , $φ$ ( $n$ ) tiene que ser la potencia más pequeña de $a$ que sea congruente con 1 módulo $n$ .