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 .

Existe unha raíz primitiva se e só se n é 1, 2, 4, pk ou 2pk, 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 

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 , 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  é 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  é 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 , ou simplemente un elemento primitivo de .

Cando  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  cíclico), a orde de   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  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  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  que teñen unha raíz primitiva son da forma


 = {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}. .

Estes son os números  con  .

A seguinte táboa enumera as raíces primitivas módulo  ata :
raíces primitivas módulo orde  (OEIS: A000010)expoñente (OEIS: A002322)101121113222432252, 344652273, 56684292, 566103, 744112, 6, 7, 810101242132, 6, 7, 111212143, 56615841684173, 5, 6, 7, 10, 11, 12, 141616185, 1166192, 3, 10, 13, 14, 151818208421126227, 13, 17, 191010235, 7, 10, 11, 14, 15, 17, 19, 20, 2122222482252, 3, 8, 12, 13, 17, 22, 232020267, 11, 15, 191212272, 5, 11, 14, 20, 23181828126292, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 2728283084313, 11, 12, 13, 17, 21, 22, 243030

 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,
{|
|-
| = 3, || (2) = −1. || A raíz primitiva é 2.
|-
| = 5, || (4) = 0. || As raíces primitivas son  2 e 3.
|-
| = 7, || (6) = 1. || As raíces primitivas son  3 e 5.
|-
| = 31, ||(30) = −1. || As raíces primitivas son   3, 11, 12, 13, 17, 21, 22 e 24.
|}

Por exemplo, o produto destas últimas raíces primitivas é , e a súa suma é  .

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  (a orde de ), entón é unha raíz primitiva. De feito, a inversa é verdade: se  é unha raíz primitiva módulo , entón a orde multiplicativa de  é  Podemos usalo para probar un candidato  para ver se é primitivo.

Para  primeiro, calcular  Despois determinar os diferentes factores primos de , digamos 1 ,... , . Finalmente, calcular



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 



xa que, en xeral, un grupo cíclico con  elementos ten  xeradores.

Para  primo, isto é igual a , e posto que  os xeradores son moi comúns entre {2, ...,  − 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 




Categoría:Teoría de números
Categoría:Wikipedia:Páxinas con traducións non revisadas