Raíz primitiva módulo n

En aritmética modular, un número  é unha **raíz primitiva módulo ** se todo número  coprimo con  é congruente cunha potencia de  módulo . É dicir,  é unha *raíz primitiva módulo*  se para cada número enteiro  coprimo con , hai algún número enteiro  para o cal  ≡  (mod ). Tal valor  chámase **índice** ou **logaritmo discreto** de  para a base  módulo . Polo que  é unha *raíz primitiva módulo*  se e só se  é un xerador do grupo multiplicativo de enteiros módulo n, denotado (\mathbb{Z}/n\mathbb{Z})^\times.

Existe unha raíz primitiva se e só se *n* é 1, 2, 4, *p**k* ou 2*p**k*, onde *p* é un primo impar e . Para todos os demais valores de *n* o grupo multiplicativo de enteiros módulo *n* non é cíclico.
Isto foi probado por primeira vez por Gauss.

## Exemplo elemental 
O número 3 é unha raíz primitiva módulo 7 porque 
:
\begin{array}{rcrcrcrcrcr}
3^1 &=& 3^0 \times 3 &\equiv& 1 \times 3 &=& 3 &\equiv& 3 \pmod 7 \\
3^2 &=& 3^1 \times 3 &\equiv& 3 \times 3 &=& 9 &\equiv& 2 \pmod 7 \\
3^3 &=& 3^2 \times 3 &\equiv& 2 \times 3 &=& 6 &\equiv& 6 \pmod 7 \\
3^4 &=& 3^3 \times 3 &\equiv& 6 \times 3 &=& 18 &\equiv& 4 \pmod 7 \\
3^5 &=& 3^4 \times 3 &\equiv& 4 \times 3 &=& 12 &\equiv& 5 \pmod 7 \\
3^6 &=& 3^5 \times 3 &\equiv& 5 \times 3 &=& 15 &\equiv& 1 \pmod 7
\end{array}

Aquí vemos que o período de 3 módulo 7 é 6. Os residuos do período, que son 3, 2, 6, 4, 5, 1, forman unha permutación de todos os restos distintos de cero módulo 7. Se  é unha raíz primitiva módulo  sendo  primo, entón o período de repetición é  As permutacións creadas deste xeito (e os seus desprazamentos circulares) demostráronse como matrices de Costas.

## Definición 
Se  é un enteiro positivo, os enteiros de 1 a  que son coprimos con  (ou de forma equivalente, as clases de congruencia coprimas con ) forman un grupo, coa multiplicación módulo  como a súa operación; denótase como (\mathbb{Z}/n\mathbb{Z})^\times, e chámase o grupo de unidades módulo , ou o grupo de clases primitivas módulo . Como se explica no artigo grupo multiplicativo de enteiros módulo, este grupo multiplicativo (\mathbb{Z}/n\mathbb{Z})^\times é cíclico **se e só se**  é igual a 2, 4,  ou 2 onde  é un potencia dun número primo impar. Cando (e só cando) este grupo (\mathbb{Z}/n\mathbb{Z})^\times é cíclico, un xerador deste grupo cíclico chámase **raíz primitiva módulo ** (ou en linguaxe máis completa **raíz primitiva da unidade módulo **, resaltando o seu papel como solución fundamental do polinomio de **raíces da unidade** das ecuacións polinómicas X − 1 no anel (\mathbb{Z}/n\mathbb{Z})^\times, ou simplemente un **elemento primitivo de** (\mathbb{Z}/n\mathbb{Z})^\times.

Cando (\mathbb{Z}/n\mathbb{Z})^\times non é cíclico, eses elementos primitivos mod  non existen. Pola contra, cada compoñente primo de  ten as súas propias raíces sub-primitivas (ver  nos exemplos de abaixo).

Para calquera  (sexa ou non (\mathbb{Z}/n\mathbb{Z})^\times cíclico), a orde de  (\mathbb{Z}/n\mathbb{Z})^\times vén dada pola función totiente de Euler  () . E entón, o  teorema de Euler di que  para todo  coprimo con ; a potencia máis baixa de  que é congruente con 1 módulo  chámase orde multiplicativa de  módulo . En particular, para que  sexa unha raíz primitiva módulo ,  ten que ser a potencia máis pequena de  que sexa congruente con 1 módulo .

## Exemplos 
Por exemplo, se  entón os elementos de (\mathbb{Z}/14\mathbb{Z})^\times son as clases de congruencia {1, 3, 5, 9, 11, 13}; hai  delas. Aquí temos unha táboa das súas potencias módulo 14:
  x     x, x2, x3, ... (mod 14)
  1 :   1
  3 :   3,  9, 13, 11,  5,  1 
  5 :   5, 11, 13,  9,  3,  1
  9 :   9, 11,  1
 11 :  11,  9,  1
 13 :  13,  1
A orde de 1 é 1, as ordes de 3 e 5 son 6, as ordes de 9 e 11 son 3 e a orde de 13 é 2. Así, 3 e 5 son as raíces primitivas módulo 14.

Para un segundo exemplo imos ver  Os elementos de (\mathbb{Z}/15\mathbb{Z})^\times son as clases de congruencia {1, 2, 4, 7, 8, 11, 13, 14}; hai  delas.
  x     x, x2, x3, ... (mod 15)
  1 :   1
  2 :   2,  4,  8, 1 
  4 :   4,  1
  7 :   7,  4, 13, 1
  8 :   8,  4,  2, 1
 11 :  11,  1
 13 :  13,  4,  7, 1
 14 :  14,  1

Como non hai número ningún cuxa orde sexa 8, non hai raíces primitivas módulo 15. De feito, , onde  é a función de Carmichael.     

## Táboa de raíces primitivas 
Os números n que teñen unha raíz primitiva son da forma

: n \in \{1, 2, 4, p^k, 2 \cdot p^k \; \; | \; \; 2 
: = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. 

Estes son os números n con \varphi(n) = \lambda(n), .

A seguinte táboa enumera as raíces primitivas módulo  ata n=31:

## Propiedades 
Gauss demostrou que para calquera número primo  (coa única excepción de  o produto das súas raíces primitivas é congruente con 1 módulo .

Tamén demostrou  que para calquera número primo , a suma das súas raíces primitivas é congruente con (  − 1) módulo , onde  é a función de Möbius.

Por exemplo,
:

Por exemplo, o produto destas últimas raíces primitivas é 2^6\cdot 3^4\cdot 7\cdot 11^2\cdot 13\cdot 17 = 970377408 \equiv 1 \pmod{31}, e a súa suma é 123 \equiv -1 \equiv \mu(31-1) \pmod{31} .

A conxectura de Artin sobre as raíces primitivas afirma que un enteiro dado  que non é nin un cadrado perfecto nin -1 é unha raíz primitiva módulo infinitamente moitos primos.

## Procurando raíces primitivas 
Non se coñece unha fórmula xeral simple para calcular raíces primitivas módulo  .   No entanto, hai métodos para localizar unha raíz primitiva que son máis rápidos que simplemente probar todos os candidatos. Se a orde multiplicativa (o seu expoñente) dun número  módulo  é igual a \varphi(n) (a orde de (\mathbb{Z}/n\mathbb{Z})^\times), entón é unha raíz primitiva. De feito, a inversa é verdade: se  é unha raíz primitiva módulo , entón a orde multiplicativa de  é \varphi(n) = \lambda(n). Podemos usalo para probar un candidato  para ver se é primitivo.

Para n > 1 primeiro, calcular \varphi(n). Despois determinar os diferentes factores primos de \varphi(n), digamos 1 ,... , . Finalmente, calcular

: g^{\varphi(n)/p_i}\bmod n \qquad\mbox{ para } i=1,\ldots,k

usando un algoritmo rápido para a exponenciación modular como a exponenciación por cadrado. Un número  para o que estes  resultados son todos diferentes de 1 é unha raíz primitiva.

O número de raíces primitivas módulo , se as hai, é igual a 

: \varphi\left(\varphi(n)\right)

xa que, en xeral, un grupo cíclico con  elementos ten \varphi(r) xeradores.

Para  primo, isto é igual a \varphi(n-1), e posto que n / \varphi(n-1) \in O(\log\log n) os xeradores son moi comúns entre {2, ...,  &#x2212; 1} e, polo tanto, é relativamente fácil atopar un. 

Se  é unha raíz primitiva módulo , entón  é tamén unha raíz primitiva módulo todas as potencias  a menos que  −1 ≡ 1 (mod 2); nese caso temos que   +  si o é. 

Se  é unha raíz primitiva módulo , entón  é tamén unha raíz primitiva módulo todas as potencias menores de .

Se  é unha raíz primitiva módulo , entón  ou  +  (o que sexa impar) é unha raíz primitiva módulo 2. 

Atopar raíces primitivas módulo  tamén é equivalente a atopar as raíces do ( − 1) polinomio ciclotómico módulo .

## Notas 
## Véxase tamén 
### Bibliografía 
* 

* 

*

*

*

*

*
### Outros artigos 
* Caracter de Dirichlet
* Teorema de Wilson
* Residuo cadrático
* Raíz da unidade módulo n
* Conxectura de Artin sobre raíces primitivas
### Ligazóns externas 
* 
*
*