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