Saltar para o conteúdo

Raiz primitiva módulo n

Origem: Wikipédia, a enciclopédia livre.

Na aritmética modular, um ramo da teoria dos números, um número é uma raiz primitiva módulo n se todo número coprimo a for congruente com uma potência de módulo . Ou seja, é uma raiz primitiva módulo se para cada inteiro coprimo com , existe um inteiro tal que . Esse valor é chamado de índice ou logaritmo discreto de para a base módulo . Observe que é uma raiz primitiva do módulo se e somente se é um gerador do grupo multiplicativo de inteiros módulo n.

Gauss definiu raízes primitivas no Artigo 57 do Disquisitiones Arithmeticae (1801), onde ele atribuiu a Euler a cunhagem do termo. No Artigo 56, ele afirmou que Lambert e Euler sabiam deles, mas ele foi o primeiro a demonstrar rigorosamente que raízes primitivas existem para um primo. Na verdade, o Disquisitiones contém duas provas: a do Artigo 54 é uma prova de existência não construtiva, enquanto a outra do Artigo 55 é construtiva.

Exemplo elementar

[editar | editar código-fonte]

O número 3 é uma raiz primitiva módulo 7[1] porque

Aqui, vemos que o período de 3k módulo 7 é 6. Os restantes no período, que são 3, 2, 6, 4, 5, 1, formam um rearranjo de todos os resíduos diferentes de zero módulo 7, implicando que 3 é de fato uma raiz primitiva módulo 7. Isso deriva do fato de que uma sequência ( módulo ) sempre se repete após algum valor de , uma vez que o módulo produz um número finito de valores. Se for uma raiz primitiva módulo e for primo, o período de repetição será . Curiosamente, as permutações criadas dessa maneira (e seus deslocamentos circulares) mostraram ser matrizes de Costas.

Se for um inteiro positivo, os inteiros entre e que são coprimos com (ou equivalentemente, as classes de congruência coprimos com ) formam um grupo, com multiplicação módulo como operação; é denotado por , e é chamado de grupo de unidades módulo , ou grupo de classes primitivas módulo . Conforme explicado no artigo grupo multiplicativo de inteiros módulo n, este grupo multiplicativo () é cíclico se e somente se for igual a , , ou , onde é uma potência de um número primo ímpar.[2][3][4] Quando (e somente quando) este grupo é cíclico, um gerador deste grupo cíclico é chamado de raiz primitiva módulo n[5] (ou em linguagem mais completa raiz primitiva de unidade módulo n, enfatizando seu papel como uma solução fundamental das raízes de unidade das equações polinomiais no anel ), ou simplesmente um elemento primitivo de . Quando é não-cíclico, tais elementos primitivos mod não existem.

Para qualquer (seja ou não cíclico), a ordem de (ou seja, o número de elementos em) é dada pela função totiente de Euler (sequência A000010 na OEIS). E então, o teorema de Euler diz que para todo coprimo com ; a menor potência de que é congruente a é chamada de ordem multiplicativa de módulo . Em particular, para ser uma raiz primitiva módulo , tem que ser a menor potência de que é congruente a .

Por exemplo, se , então os elementos de são as classes de congruência ; existem deles. Aqui está uma tabela de suas potências 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 ordem de 1 é 1, as ordens de 3 e 5 são 6, as ordens de 9 e 11 são 3 e a ordem de 13 é 2. Assim, 3 e 5 são as raízes primitivas módulo 14.

Para um segundo exemplo, seja . Os elementos de são as classes de congruência ; existem deles.

 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 não há número cuja ordem seja 8, não há raízes primitivas módulo 15. De fato, , onde é a função de Carmichael. (sequência A002322 na OEIS)

Tabela de raízes primitivas

[editar | editar código-fonte]

Números que têm uma raiz primitiva são

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, 53, 54, 58, 59, 61, 62, 67, 71, 73, 74, 79, 81, 82, 83, 86, 89, 94, 97, 98, 101, 103, 106, 107, 109, 113, 118, 121, 122, 125, 127, 131, 134, 137, 139, 142, 146, 149, ... (sequência A033948 na OEIS)

Esta é a tabela de Gauss das raízes primitivas de Disquisitiones. Ao contrário da maioria dos autores modernos, ele nem sempre escolhia a menor raiz primitiva. Em vez disso, ele escolhia 10 se for uma raiz primitiva; se não for, ele escolhia a raiz que dá 10 o menor índice e, se houver mais de uma, escolhe a menor delas. Isso não é apenas para tornar o cálculo manual mais fácil, mas é usado no § VI, onde as expansões decimais periódicas de números racionais são investigadas.

As linhas da tabela são rotuladas com as potências primas (exceto 2, 4 e 8) menor que 100; a segunda coluna é um módulo raiz primitivoa desse número. As colunas são rotuladas com os primos menores que 100. A entrada na linha p, coluna q é o índice de q módulo p para a raiz fornecida.

Por exemplo, na linha , é dado como a raiz primitiva e na coluna a entrada é . Isso significa que .

Para o índice de um número composto, some os índices de seus fatores primos.

Por exemplo, na linha , o índice de é a soma dos índices para e : . O índice de é o dobro do índice : . (Claro, como , a entrada para é ).

A tabela é simples para as potências primas ímpares. Mas as potências de 2 (16, 32 e 64) não têm raízes primitivas; em vez disso, as potências de 5 respondem por metade dos números ímpares menores que a potência de 2, e seus módulos negativos, as potências de 2 respondem pela outra metade. Todas as potências de 5 são ou ; as colunas encabeçadas por números ou contêm o índice de seu negativo. (sequência A185189 na OEIS) e (sequência A185268 na OEIS)

Por exemplo, no módulo o índice para é e , mas a entrada para é e .

Raízes primitivas e índices
(outras colunas são os índices de inteiros sob os respectivos títulos das colunas)
n raiz 2 3 5 7 11   13 17 19 23 29   31 37 41 43 47   53 59 61 67 71   73 79 83 89 97
3 2 1
5 2 1 3
7 3 2 1 5
9 2 1 * 5 4
11 2 1 8 4 7
13 6 5 8 9 7 11
16 5 * 3 1 2 1 3
17 10 10 11 7 9 13 12
19 10 17 5 2 12 6 13 8
23 10 8 20 15 21 3 12 17 5
25 2 1 7 * 5 16 19 13 18 11
27 2 1 * 5 16 13 8 15 12 11
29 10 11 27 18 20 23 2 7 15 24
31 17 12 13 20 4 29 23 1 22 21 27
32 5 * 3 1 2 5 7 4 7 6 3 0
37 5 11 34 1 28 6 13 5 25 21 15 27
41 6 26 15 22 39 3 31 33 9 36 7 28 32
43 28 39 17 5 7 6 40 16 29 20 25 32 35 18
47 10 30 18 17 38 27 3 42 29 39 43 5 24 25 37
49 10 2 13 41 * 16 9 31 35 32 24 7 38 27 36 23
53 26 25 9 31 38 46 28 42 41 39 6 45 22 33 30 8
59 10 25 32 34 44 45 28 14 22 27 4 7 41 2 13 53 28
61 10 47 42 14 23 45 20 49 22 39 25 13 33 18 41 40 51 17
64 5 * 3 1 10 5 15 12 7 14 11 8 9 14 13 12 5 1 3
67 12 29 9 39 7 61 23 8 26 20 22 43 44 19 63 64 3 54 5
71 62 58 18 14 33 43 27 7 38 5 4 13 30 55 44 17 59 29 37 11
73 5 8 6 1 33 55 59 21 62 46 35 11 64 4 51 31 53 5 58 50 44
79 29 50 71 34 19 70 74 9 10 52 1 76 23 21 47 55 7 17 75 54 33 4
81 11 25 * 35 22 1 38 15 12 5 7 14 24 29 10 13 45 53 4 20 33 48 52
83 50 3 52 81 24 72 67 4 59 16 36 32 60 38 49 69 13 20 34 53 17 43 47
89 30 72 87 18 7 4 65 82 53 31 29 57 77 67 59 34 10 45 19 32 26 68 46 27
97 10 86 2 11 53 82 83 19 27 79 47 26 41 71 44 60 14 65 32 51 25 20 42 91 18
n raiz 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

A tabela a seguir lista as raízes primitivas módulo para :

raízes primitivas módulo ordem

(OEISA000010)

raízes primitivas módulo ordem

(OEISA000010)

1 0 1 37 2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35 36
2 1 1 38 3, 13, 15, 21, 29, 33 18
3 2 2 39 24
4 3 2 40 16
5 2, 3 4 41 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35 40
6 5 2 42 12
7 3, 5 6 43 3, 5, 12, 18, 19, 20, 26, 28, 29, 30, 33, 34 42
8 4 44 20
9 2, 5 6 45 24
10 3, 7 4 46 5, 7, 11, 15, 17, 19, 21, 33, 37, 43 22
11 2, 6, 7, 8 10 47 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45 46
12 4 48 16
13 2, 6, 7, 11 12 49 3, 5, 10, 12, 17, 24, 26, 33, 38, 40, 45, 47 42
14 3, 5 6 50 3, 13, 17, 23, 27, 33, 37, 47 20
15 8 51 32
16 8 52 24
17 3, 5, 6, 7, 10, 11, 12, 14 16 53 2, 3, 5, 8, 12, 14, 18, 19, 20, 21, 22, 26, 27, 31, 32, 33, 34, 35, 39, 41, 45, 48, 50, 51 52
18 5, 11 6 54 5, 11, 23, 29, 41, 47 18
19 2, 3, 10, 13, 14, 15 18 55 40
20 8 56 24
21 12 57 36
22 7, 13, 17, 19 10 58 3, 11, 15, 19, 21, 27, 31, 37, 39, 43, 47, 55 28
23 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 22 59 2, 6, 8, 10, 11, 13, 14, 18, 23, 24, 30, 31, 32, 33, 34, 37, 38, 39, 40, 42, 43, 44, 47, 50, 52, 54, 55, 56 58
24 8 60 16
25 2, 3, 8, 12, 13, 17, 22, 23 20 61 2, 6, 7, 10, 17, 18, 26, 30, 31, 35, 43, 44, 51, 54, 55, 59 60
26 7, 11, 15, 19 12 62 3, 11, 13, 17, 21, 43, 53, 55 30
27 2, 5, 11, 14, 20, 23 18 63 36
28 12 64 32
29 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 28 65 48
30 8 66 20
31 3, 11, 12, 13, 17, 21, 22, 24 30 67 2, 7, 11, 12, 13, 18, 20, 28, 31, 32, 34, 41, 44, 46, 48, 50, 51, 57, 61, 63 66
32 16 68 32
33 20 69 44
34 3, 5, 7, 11, 23, 27, 29, 31 16 70 24
35 24 71 7, 11, 13, 21, 22, 28, 31, 33, 35, 42, 44, 47, 52, 53, 55, 56, 59, 61, 62, 63, 65, 67, 68, 69 70
36 12 72 24

A conjectura de Artin sobre as raízes primitivas afirma que um dado inteiro que não é um quadrado perfeito nem é uma raiz primitiva módulo infinitos primos.

A sequência de menores raízes primitivas módulo (que não é a mesma que a sequência de raízes primitivas na tabela de Gauss) são

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, ... (sequência A046145 na OEIS)

Para primo, elas são

1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2, ... (sequência A001918 na OEIS)

As maiores raízes primitivas módulo são

0, 1, 2, 3, 3, 5, 5, 0, 5, 7, 8, 0, 11, 5, 0, 0, 14, 11, 15, 0, 0, 19, 21, 0, 23, 19, 23, 0, 27, 0, 24, 0, 0, 31, 0, 0, 35, 33, 0, 0, 35, 0, 34, 0, 0, 43, 45, 0, 47, 47, 0, 0, 51, 47, 0, 0, 0, 55, 56, 0, 59, 55, 0, 0, 0, 0, 63, 0, 0, 0, 69, 0, 68, 69, 0, ... (sequência A046146 na OEIS)

Para primo, elas são

1, 2, 3, 5, 8, 11, 14, 15, 21, 27, 24, 35, 35, 34, 45, 51, 56, 59, 63, 69, 68, 77, 80, 86, 92, 99, 101, 104, 103, 110, 118, 128, 134, 135, 147, 146, 152, 159, 165, 171, 176, 179, 189, 188, 195, 197, 207, 214, 224, 223, ... (sequência A071894 na OEIS)

Número de raízes primitivas módulo são

1, 1, 1, 1, 2, 1, 2, 0, 2, 2, 4, 0, 4, 2, 0, 0, 8, 2, 6, 0, 0, 4, 10, 0, 8, 4, 6, 0, 12, 0, 8, 0, 0, 8, 0, 0, 12, 6, 0, 0, 16, 0, 12, 0, 0, 10, 22, 0, 12, 8, 0, 0, 24, 6, 0, 0, 0, 12, 28, 0, 16, 8, 0, 0, 0, 0, 20, 0, 0, 0, 24, 0, 24, 12, 0, ... (sequência A046144 na OEIS)

Para primo, elas são

1, 1, 2, 2, 4, 4, 8, 6, 10, 12, 8, 12, 16, 12, 22, 24, 28, 16, 20, 24, 24, 24, 40, 40, 32, 40, 32, 52, 36, 48, 36, 48, 64, 44, 72, 40, 48, 54, 82, 84, 88, 48, 72, 64, 84, 60, 48, 72, 112, 72, 112, 96, 64, 100, 128, 130, 132, 72, 88, 96, ... (sequência A008330 na OEIS)

Menor primo com raiz primitiva são

2, 3, 5, 0, 7, 11, 11, 11, 0, 17, 13, 17, 19, 17, 19, 0, 23, 29, 23, 23, 23, 31, 47, 31, 0, 29, 29, 41, 41, 41, 47, 37, 43, 41, 37, 0, 59, 47, 47, 47, 47, 59, 47, 47, 47, 67, 59, 53, 0, 53, ... (sequência A023049 na OEIS)

Menor primo (não necessariamente excedendo ) com raiz primitiva são

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, 2, 3, 2, ... (sequência A056619 na OEIS)

Fatos aritméticos

[editar | editar código-fonte]

Gauss provou[6] que para qualquer número primo (com a única exceção de ), o produto de suas raízes primitivas é congruente a módulo .

Ele também provou[7] que para qualquer número primo , a soma de suas raízes primitivas é congruente com módulo , onde é a função de Möbius.

Por exemplo,

, . A raiz primitiva é .
, . The primitive roots are and .
, . The primitive roots are and .
, . The primitive roots are , , , , , , e .
Seu produto e sua soma .
.

As somas (ou diferenças) de duas raízes primitivas somam todos os elementos do subgrupo de índice 2 de para pares e a todo o grupo quando é ímpar:

Z/n Z× + Z/n Z× = Z/n Z ou 2Z/n Z.[8]

Encontrando raízes primitivas

[editar | editar código-fonte]

Nenhuma fórmula geral simples para calcular raízes primitivas módulo é conhecida.[9][10] No entanto, existem métodos para localizar uma raiz primitiva que são mais rápidos do que simplesmente tentar todos os candidatos. Se a ordem multiplicativa de um número módulo for igual a (a ordem de ), então é uma raiz primitiva. Na verdade, o inverso é verdadeiro: se é uma raiz primitiva módulo , então a ordem multiplicativa de é . Podemos usar isso para testar um candidato para ver se ele é primitivo.

Primeiro, calcule . Em seguida, determine os diferentes fatores primos de , digamos . Finalmente, calcule

usando um algoritmo rápido para exponenciação modular, como exponenciação binária. Um número para o qual esses resultados são todos diferentes de 1 é uma raiz primitiva.

O número de raízes primitivas módulo , se houver, é igual a[11]

uma vez que, em geral, um grupo cíclico com elementos tem geradores. Para o primo , isso é igual , e já que os geradores são muito comuns entre e, portanto, é relativamente fácil encontrar um.[12]

Se é uma raiz primitiva módulo , então também é uma raiz primitiva módulo todas as potências a menos que ; nesse caso, é.[13]

Se é uma raiz primitiva do módulo , então ou (o que for ímpar) é uma raiz primitiva do módulo .[13]

Encontrar raízes primitivas módulo também é equivalente a encontrar as raízes do ()-ésimo polinomial ciclotômico módulo .

Ordem de magnitude das raízes primitivas

[editar | editar código-fonte]

A raiz menos primitiva módulo (no intervalo ) é geralmente pequena.

Limites superiores

[editar | editar código-fonte]

Burgess (1962) provou[14] que para cada existe um tal que

Grosswald (1981) provou[14] que se , então .

Carella (2015) provou[15] que existe um tal que para todos os primos suficientemente grandes .

Shoup (1990, 1992) provou,[16] assumindo a hipótese generalizada de Riemann, que .

Limites inferiores

[editar | editar código-fonte]

Fridlander (1949) e Salié (1950) provaram[14] que existe uma constante positiva tal que para um número infinito de números primos .

Pode ser provado[14] de uma maneira elementar que para qualquer inteiro positivo existem infinitos primos tais que .

Uma raiz primitiva módulo é frequentemente usado em criptografia, incluindo o esquema de troca de chaves Diffie–Hellman. Os difusores de som têm sido baseados em conceitos da teoria dos números, como raízes primitivas e resíduos quadráticos.[17][18]

  1. «Archived copy». Consultado em 3 de julho de 2017. Arquivado do original em 3 de julho de 2017 
  2. Weisstein, Eric W. «Modulo Multiplication Group». MathWorld (em inglês) 
  3. Primitive root, Encyclopedia of Mathematics.
  4. Vinogradov 2003, § VI PRIMITIVE ROOTS AND INDICES, pp. 105–121.
  5. Vinogradov 2003, p. 106.
  6. Gauss & Clarke 1986, arts. 80.
  7. Gauss & Clarke 1986, arts. 81.
  8. Emmanuel Amiot, Music Through Fourier Space, p. 38 (Springer, CMS Series, 2016).
  9. von zur Gathen & Shparlinski 1998, pp. 15–24: "One of the most important unsolved problems in the theory of finite fields is designing a fast algorithm to construct primitive roots."
  10. Robbins 2006, p. 159: "There is no convenient formula for computing [the least primitive root]."
  11. (sequência A010554 na OEIS)
  12. Donald E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical Algorithms, 3rd edition, section 4.5.4, p. 391 (Addison–Wesley, 1998).
  13. a b Cohen 1993, p. 26.
  14. a b c d Ribenboim 1996, p. 24.
  15. Carella, N. A. (2015). «Least Prime Primitive Roots». International Journal of Mathematics and Computer Science. 10 (2): 185-194. arXiv:1709.01172Acessível livremente 
  16. Bach & Shallit 1996, p. 254.
  17. Walker, R. «The design and application of modular acoustic diffusing elements» (PDF). BBC Research Department. Consultado em 25 de março de 2019 
  18. Feldman, Eliot (julho de 1995). «A reflection grating that nullifies the specular reflection: A cone of silence». J. Acoust. Soc. Am. 98 (1): 623–634. Bibcode:1995ASAJ...98..623F. doi:10.1121/1.413656 

O Disquisitiones Arithmeticae foi traduzido do latim ciceroniano de Gauss para o inglês e o alemão. A edição alemã inclui todos os seus artigos sobre a teoria dos números: todas as provas de reciprocidade quadrática, a determinação do sinal da soma de Gauss, as investigações sobre a reciprocidade biquadrática e notas não publicadas.

Leitura adicional

[editar | editar código-fonte]

Ligações externas

[editar | editar código-fonte]